# The computability of Kleene's $T$-predicate

Why is Kleene's T-predicate computable?

how to argue this using turing computability? would that be useful or writing it as some function

-
In effect, Kleene's $T$-predicate is the arithmetical version of a universal Turing machine. That should tell you how to construct it. –  Zhen Lin Feb 22 '13 at 9:00

@user58512's answer is basically spot on, but to amplify just a little bit. As said, $T(e,x,n)$ outputs (a code for) the result of running $n$ steps of the Turing program numbered $e$ on input $x$. Plainly this is computable. Here's how.

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, assuming a normal Gödel-numbering of Turing programs), we don't need open-ended searches to decode $e$.

Now 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 computable, and computable without open-ended searches. So it will be primitive recursive (for the primitive recursive functions are those which are computable without open-ended searches).

However, if you want to write down an explicit primitive recursive definition of $T$, that will depend on the details of how you set up the Turing machines, how you Gödel number them, etc. It is no great fun to hack through the details.

-

Kleene's T predicate isn't just computable, it's primitive recursive which is much stronger.

For $e$ the "Godel number" of a computable function, $T(e,x,n)$ computes $n$ steps of running the function $e$ encodes on input $x$. In particular it gives a list of every step of computation so far.

To compute $T$ all you need to do is a simple recursion on $n$, performing one step of a Turing machine each time.

-