Kleene's T predicate

Short description: Concept in computability theory

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.

Definition

Example call of T₁. The 1st argument gives the source code (in C rather than as a Gödel number e) of a computable function, viz. the Collatz function f. The 2nd argument gives the natural number i to which f is to be applied. The 3rd argument gives a sequence x of computation steps simulating the evaluation of f on i (as an equation chain rather than a Gödel sequence number). The predicate call evaluates to true since x is actually the correct computation sequence for the call f(5), and ends with an expression not involving f anymore. Function U, applied to the sequence x, will return its final expression, viz. 1.

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 [math]\displaystyle{ T }[/math] predicate is obtained by formalizing this simulation.

The ternary relation [math]\displaystyle{ T_1(e,i,x) }[/math] takes three natural numbers as arguments. [math]\displaystyle{ T_1(e,i,x) }[/math] is true if [math]\displaystyle{ x }[/math] encodes a computation history of the computable function with index [math]\displaystyle{ e }[/math] when run with input [math]\displaystyle{ i }[/math], and the program halts as the last step of this computation history. That is,

• [math]\displaystyle{ T_1 }[/math] first asks whether [math]\displaystyle{ x }[/math] is the Gödel number of a finite sequence [math]\displaystyle{ \langle x_{j} \rangle }[/math] of complete configurations of the Turing machine with index [math]\displaystyle{ e }[/math], running a computation on input [math]\displaystyle{ i }[/math].
• If so, [math]\displaystyle{ T_1 }[/math] 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, [math]\displaystyle{ T_1 }[/math] finally asks whether the sequence [math]\displaystyle{ \langle x_{j} \rangle }[/math] ends with the machine in a halting state.

If all three of these questions have a positive answer, then [math]\displaystyle{ T_1(e,i,x) }[/math] is true, otherwise, it is false.

The [math]\displaystyle{ T_1 }[/math] 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 [math]\displaystyle{ U }[/math] such that if [math]\displaystyle{ T_1(e,i,x) }[/math] is true then [math]\displaystyle{ U(x) }[/math] returns the output of the function with index [math]\displaystyle{ e }[/math] on input [math]\displaystyle{ i }[/math].

Because Kleene's formalism attaches a number of inputs to each function, the predicate [math]\displaystyle{ T_1 }[/math] can only be used for functions that take one input. There are additional predicates for functions with multiple inputs; the relation

[math]\displaystyle{ T_k(e, i_1, \ldots, i_k, x) }[/math]

is true if [math]\displaystyle{ x }[/math] encodes a halting computation of the function with index [math]\displaystyle{ e }[/math] on the inputs [math]\displaystyle{ i_1,\ldots,i_k }[/math].

Like [math]\displaystyle{ T_1 }[/math], all functions [math]\displaystyle{ T_k }[/math] are primitive recursive. Because of this, any theory of arithmetic that is able to represent every primitive recursive function is able to represent [math]\displaystyle{ T }[/math] and [math]\displaystyle{ U }[/math]. Examples of such arithmetical theories include Robinson arithmetic and stronger theories such as Peano arithmetic.

Normal form theorem

The [math]\displaystyle{ T_k }[/math] predicates can be used to obtain Kleene's normal form theorem for computable functions (Soare 1987, p. 15; Kleene 1943, p. 52—53). This states there exists a fixed primitive recursive function [math]\displaystyle{ U }[/math] such that a function [math]\displaystyle{ f:\mathbb{N}^{k}\rightarrow\mathbb{N} }[/math] is computable if and only if there is a number [math]\displaystyle{ e }[/math] such that for all [math]\displaystyle{ n_1,\ldots,n_k }[/math] one has

[math]\displaystyle{ f(n_1,\ldots,n_k) \simeq U( \mu x\, T_k(e,n_1,\ldots,n_k,x)) }[/math],

where μ is the μ operator ([math]\displaystyle{ \mu x\, \phi(x) }[/math] is the smallest natural number for which [math]\displaystyle{ \phi(x) }[/math] is true) and [math]\displaystyle{ \simeq }[/math] is true if both sides are undefined or if both are defined and they are equal. By the theorem, the definition of every general recursive function f can be rewritten into a normal form such that the μ operator is used only once, viz. immediately below the topmost [math]\displaystyle{ U }[/math], which is independent of the computable function [math]\displaystyle{ f }[/math].

Arithmetical hierarchy

In addition to encoding computability, the T predicate can be used to generate complete sets in the arithmetical hierarchy. In particular, the set

[math]\displaystyle{ K = \{ e \mbox{ } : \mbox{ } \exists x T_1(e,0,x) \} }[/math]

which is of the same Turing degree as the halting problem, is a [math]\displaystyle{ \Sigma^0_1 }[/math] complete unary relation (Soare 1987, pp. 28, 41). More generally, the set

[math]\displaystyle{ K_{n+1} = \{ \langle e, a_1, \ldots, a_n\rangle : \exists x T_n(e, a_1, \ldots, a_n, x)\} }[/math]

is a [math]\displaystyle{ \Sigma^0_1 }[/math]-complete (n+1)-ary predicate. Thus, once a representation of the T_n predicate is obtained in a theory of arithmetic, a representation of a [math]\displaystyle{ \Sigma^0_1 }[/math]-complete predicate can be obtained from it.

This construction can be extended higher in the arithmetical hierarchy, as in Post's theorem (compare Hinman 2005, p. 397). For example, if a set [math]\displaystyle{ A \subseteq \mathbb{N}^{k+1} }[/math] is [math]\displaystyle{ \Sigma^0_{n} }[/math] complete then the set

[math]\displaystyle{ \{ \langle a_1, \ldots, a_k\rangle : \forall x ( \langle a_1, \ldots, a_k, x) \in A)\} }[/math]

is [math]\displaystyle{ \Pi^0_{n+1} }[/math] complete.

References

• Peter Hinman, 2005, Fundamentals of Mathematical Logic, A K Peters. ISBN 978-1-56881-262-5
• Stephen Cole Kleene (Jan 1943). "Recursive predicates and quantifiers". Transactions of the American Mathematical Society 53 (1): 41–73. doi:10.1090/S0002-9947-1943-0007371-8. https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf.  Reprinted in The Undecidable, Martin Davis, ed., 1965, pp. 255–287.
• —, 1952, Introduction to Metamathematics, North-Holland. Reprinted by Ishi press, 2009, ISBN 0-923891-57-9.
• —, 1967. Mathematical Logic, John Wiley. Reprinted by Dover, 2001, ISBN 0-486-42533-9.
• Robert I. Soare, 1987, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer. ISBN 0-387-15299-7