Proof of Kleene's T predicate being primitive recursive

Question

As I am looking over Kleene's T predicate, I was unable to find why Kleene's T predicate is primitive recursive. Can anyone show why?

(I know what primitive recursive is.)

Answer 1

$T(e,x,n)$ outputs (a code for) the result of running $n$ steps of the Turing program numbered $e$ on input $x$.

Think about how we would compute the value of $T$ for particular arguments $e, x, n$.

First we'll need to extract from the code number $e$ the tuples that are the Turing program $\Pi$ (if there is one: assume waste cases are dealt with sensibly). Note that, assuming a normal Gödel-numbering of Turing programs, we won't need to set off on open-ended searches in order to decode $e$.

Now we need to run $\Pi$ for $n$ steps on input $x$. Again, there won't be open-ended searches involved in running $\Pi$ (for any searches will be bounded by the number of tuples in the Turing program).

So: $T(e,x,n)$ is evidently computable, and -- the key point here -- is computable without open-ended searches.

So we now know that $T$ must be not just computable but primitive recursive -- for the primitive recursive functions are exactly those which are computable without open-ended searches (i.e. can be computed using "for" loops, without needing to invoke "do until" loops).

However, that's quick-and-dirty. If you want to do things the hard way, and write down an explicit primitive recursive definition of $T$, the details will obviously depend on how you set up the Turing machines, how you Gödel number their programs, how you code up the state of their tapes, etc, etc. It is no great fun to hack through such details, but there are textbooks which work through various versions. For example, look at Ch. 5 of N. J. Cutland's wonderful classic Computability: An introduction to recursive function theory (CUP, 1980).