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

## 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$ predicate is obtained by formalizing this simulation.
The ternary relation $T_{1}(e,i,x)$ takes three natural numbers as arguments. $T_{1}(e,i,x)$ is true if $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_{1}$ first asks whether $x$ is the Gödel number of a finite sequence $\langle x_{j}\rangle$ of complete configurations of the Turing machine with index $e$, running a computation on input $i$.
* If so, $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}$ finally asks whether the sequence $\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)$ is true, otherwise, it is false.
The $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$ such that if $T_{1}(e,i,x)$ is true 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_{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},\ldots ,i_{k},x)$
is true if $x$ encodes a halting computation of the function with index $e$ on the inputs $i_{1},\ldots ,i_{k}$.
Like $T_{1}$, 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 $T$ and $U$. 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 $U$ such that a function $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ is computable if and only if there is a number $e$ such that for all $n_{1},\ldots ,n_{k}$ one has
    $f(n_{1},\ldots ,n_{k})\simeq U(\mu x\,T_{k}(e,n_{1},\ldots ,n_{k},x))$,
where μ is the μ operator ($\mu x\,\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 $U$, which is independent of the computable function $f$.

## 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{\mbox{ }}:{\mbox{ }}\exists xT_{1}(e,0,x)\}$
which is of the same Turing degree as the halting problem, is a $\Sigma _{1}^{0}$ complete unary relation (Soare 1987, pp. 28, 41). More generally, the set
    $K_{n+1}=\{\langle e,a_{1},\ldots ,a_{n}\rangle :\exists xT_{n}(e,a_{1},\ldots ,a_{n},x)\}$
is a $\Sigma _{1}^{0}$-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 $\Sigma _{1}^{0}$-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\subseteq \mathbb {N} ^{k+1}$ is $\Sigma _{n}^{0}$ complete then the set
    $\{\langle a_{1},\ldots ,a_{k}\rangle :\forall x(\langle a_{1},\ldots ,a_{k},x)\in A)\}$
is $\Pi _{n+1}^{0}$ complete.