Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Why is Kleene's T-predicate computable?

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

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.