Kleene's T predicate explained

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.^[1]

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

predicate is obtained by formalizing this simulation.

T_1(e,i,x)

takes three natural numbers as arguments.

T_1(e,i,x)

is true if

encodes a computation history of the computable function with index

when run with input

, and the program halts as the last step of this computation history. That is,

T₁

first asks whether

is the Gödel number of a finite sequence

\langlex_j\rangle

of complete configurations of the Turing machine with index

, running a computation on input

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

\langlex_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)

is true, otherwise, it is false.

The

T₁

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

such that if

T_1(e,i,x)

is true then

U(x)

returns the output of the function with index

on input

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

T_k(e,i_1,\ldots,i_k,x)

is true if

encodes a halting computation of the function with index

on the inputs

i_1,\ldots,i_k

T₁

, all functions

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

and

. Examples of such arithmetical theories include Robinson arithmetic and stronger theories such as Peano arithmetic.

Normal form theorem

The

T_k

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

such that a function

f:N^k → N

is computable if and only if there is a number

such that for all

n_1,\ldots,n_k

one has

f(n_1,\ldots,n_k)\simeqU(\muxT_k(e,n_1,\ldots,n_k,x))

,where μ is the μ operator (

\mux\phi(x)

is the smallest natural number for which

\phi(x)

is true) and

\simeq

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

, which is independent of the computable function

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

K=\{e:\existsxT_1(e,0,x)\}

which is of the same Turing degree as the halting problem, is a

	0
\Sigma
	1

complete unary relation (Soare 1987, pp. 28, 41). More generally, the set

K_n+1=\{\langlee,a_1,\ldots,a_n\rangle:\existsxT_n(e,a_1,\ldots,a_n,x)\}

is a

	0
\Sigma
	1

-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

	0
\Sigma
	1

-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

A\subseteqN^k+1

	0
\Sigma
	n

complete then the set

\{\langlea_1,\ldots,a_k\rangle:\forallx(\langlea_1,\ldots,a_k,x)\inA)\}

	0
\Pi
	n+1

complete.

Notes

The predicate described here was presented in (Kleene 1943) and (Kleene 1952), and this is what is usually called "Kleene's T predicate". (Kleene 1967) uses the letter T to describe a different predicate related to computable functions, but which cannot be used to obtain Kleene's normal form theorem.

References

Peter Hinman, 2005, Fundamentals of Mathematical Logic, A K Peters.
10.1090/S0002-9947-1943-0007371-8 . Recursive predicates and quantifiers . Stephen Cole Kleene . Transactions of the American Mathematical Society . 53 . 1 . 41 - 73 . Jan 1943 . free . Reprinted in The Undecidable, Martin Davis, ed., 1965, pp. 255 - 287.
-, 1952, Introduction to Metamathematics, North-Holland. Reprinted by Ishi press, 2009, .
-, 1967. Mathematical Logic, John Wiley. Reprinted by Dover, 2001, .
Robert I. Soare, 1987, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer.