Kleene's T predicate

In computability theory, the T predicate, first studied by mathematician Stephen Cole Kleene, is a particular set of triples of natural numbers that is used to represent computable functions within formal theories of arithmetic. Informally, the T predicate tells whether a particular computer program will halt when run with a particular input, and the corresponding U function is used to obtain the results of the computation if the program does halt. As with the s_mn theorem, the original notation used by Kleene has become standard terminology for the concept.

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

...
Wikipedia