A counterexample to your claim: Ackermann(m,m) is a computable function, hence computable by a universal Turing machine. Yet it is designed to be not primitive recursive.
And indeed Kleene’s normal form theorem requires one application of the μ-Operator. Which introduces unbounded search.
Yes, but the U() and the T() are primitive recursive. Unbounded search is necessary to get the encoding of the program, but not to execute it, that’s why I said “if an angel gives you the encoding”.
The normal form theorem indeed says that any partial recursive function is equivalent to two primitive recursive functions / relations, namely U and T, and one application of unbounded search.
The ternary relation T1(e,i,x) takes three natural numbers as arguments. The triples of numbers (e,i,x) that belong to the relation (the ones for which T1(e,i,x) is true) are defined to be exactly the triples in which x encodes a computation history of the computable function with index e when run with input i, and the program halts as the last step of this computation history.
In other words: If someone gives you an encoding of a program, an encoding of its input and a trace of its run, you can check with a primitive recursive function whether you have been lied to.
Oh! This point had evaded me: I thought x encoded the program and the input, not just the entire history. So U, instead of executing, just locates the last thing written on tape according to x and repeat it. Well, I’m disappointed… at U and at myself.
A counterexample to your claim: Ackermann(m,m) is a computable function, hence computable by a universal Turing machine. Yet it is designed to be not primitive recursive.
And indeed Kleene’s normal form theorem requires one application of the μ-Operator. Which introduces unbounded search.
Yes, but the U() and the T() are primitive recursive. Unbounded search is necessary to get the encoding of the program, but not to execute it, that’s why I said “if an angel gives you the encoding”.
The normal form theorem indeed says that any partial recursive function is equivalent to two primitive recursive functions / relations, namely U and T, and one application of unbounded search.
Quoting https://en.wikipedia.org/wiki/Kleene%27s_T_predicate:
In other words: If someone gives you an encoding of a program, an encoding of its input and a trace of its run, you can check with a primitive recursive function whether you have been lied to.
Oh! This point had evaded me: I thought x encoded the program and the input, not just the entire history.
So U, instead of executing, just locates the last thing written on tape according to x and repeat it.
Well, I’m disappointed… at U and at myself.