The computability of Kleene's $T$-predicate

Question

Why is Kleene's T-predicate computable?

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

Answer 1

@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.

Answer 2

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.