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 smn theorem, the original notation used by Kleene has become standard terminology for the concept.
Definition
The definition depends on a suitable Gödel numbering that assigns natural numbers to computable functions (given as Turing machines). 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 {\displaystyle T} predicate is obtained by formalizing this simulation. The ternary relation T 1 ( e , i , x ) {\displaystyle T_{1}(e,i,x)} takes three natural numbers as arguments. T 1 ( e , i , x ) {\displaystyle T_{1}(e,i,x)} is true if x {\displaystyle x} encodes a computation history of the computable function with index e {\displaystyle e} when run with input i {\displaystyle i} , and the program halts as the last step of this computation history. That is,
T 1 {\displaystyle T_{1}} first asks whether x {\displaystyle x} is the Gödel number of a finite sequence ⟨ x j ⟩ {\displaystyle \langle x_{j}\rangle } of complete configurations of the Turing machine with index e {\displaystyle e} , running a computation on input i {\displaystyle i} . If so, T 1 {\displaystyle T_{1}} 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 1 {\displaystyle T_{1}} finally asks whether the sequence ⟨ x j ⟩ {\displaystyle \langle x_{j}\rangle } ends with the machine in a halting state. If all three of these questions have a positive answer, then T 1 ( e , i , x ) {\displaystyle T_{1}(e,i,x)} is true, otherwise, it is false. The T 1 {\displaystyle T_{1}} predicate is primitive recursive in the sense that there is a primitive recursive function that, given inputs for the predicate, correctly determines the truth value of the predicate on those inputs. There is a corresponding primitive recursive function U {\displaystyle U} such that if T 1 ( e , i , x ) {\displaystyle T_{1}(e,i,x)} is true then U ( x ) {\displaystyle U(x)} returns the output of the function with index e {\displaystyle e} on input i {\displaystyle i} . Because Kleene's formalism attaches a number of inputs to each function, the predicate T 1 {\displaystyle T_{1}} can only be used for functions that take one input. There are additional predicates for functions with multiple inputs; the relation
T k ( e , i 1 , … , i k , x ) {\displaystyle T_{k}(e,i_{1},\ldots ,i_{k},x)}
is true if x {\displaystyle x} encodes a halting computation of the function with index e {\displaystyle e} on the inputs i 1 , … , i k {\displaystyle i_{1},\ldots ,i_{k}} . Like T 1 {\displaystyle T_{1}} , all functions T k {\displaystyle T_{k}} are primitive recursive. Because of this, any theory of arithmetic that is able to represent every primitive recursive function is able to represent T {\displaystyle T} and U {\displaystyle U} . Examples of such arithmetical theories include Robinson arithmetic and stronger theories such as Peano arithmetic.
… excerpt ends here. Continue reading the full article.
