Kleene's T Predicate - Definition

Definition

The definition depends on a suitable Gödel numbering that assigns natural numbers to computable functions. This numbering must be sufficiently effective that, given an index of a computable function and an input to the function, it is possible to effectively simulate the computation of the function on that input. The T predicate is obtained by formalizing this simulation.

The ternary relation T₁(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 T₁(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. That is, T₁ first asks whether x is the Gödel number of a finite sequence 〈x_j〉 of complete configurations of the Turing machine with index e, running a computation on input i. If so, T₁ then asks if this sequence begins with the starting state of the computation and each successive element of the sequence corresponds to a single step of the Turing machine. If it does, T₁ finally asks whether the sequence 〈x_j〉 ends with the machine in a halting state. If all three of these questions have a positive answer, then T₁(e,i,x) holds (is true). Otherwise, T₁(e,i,x) does not hold (is false).

There is a corresponding function U such that if T(e,i,x) holds then U(x) returns the output of the function with index e on input i.

Because Kleene's formalism attaches a number of inputs to each function, the predicate T₁ can only be used for functions that take one input. There are additional predicates for functions with multiple inputs; the relation

,

holds if x encodes a halting computation of the function with index e on the inputs i₁,...,i_k.