Kleene's T predicate#Normal form theorem

File:KleeneT collatz5.gif rather than as a Gödel number e) of a computable function, viz. the Collatz function f. The {{background color|#ffe0e0|2nd argument}} gives the natural number i to which f is to be applied. The {{background color|#e0ffe0|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 $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 $\backslash langle\; x\_\{j\}\; \backslash 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 $\backslash langle\; x\_\{j\}\; \backslash 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,\; \backslash ldots,\; i\_k,\; x)$

is true if $x$ encodes a halting computation of the function with index $e$ on the inputs $i\_1,\backslash 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.

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:\backslash mathbb\{N\}^\{k\}\backslash rightarrow\backslash mathbb\{N\}$ is computable if and only if there is a number $e$ such that for all $n\_1,\backslash ldots,n\_k$ one has

:$f(n\_1,\backslash ldots,n\_k)\; \backslash simeq\; U(\; \backslash mu\; x\backslash ,\; T\_k(e,n\_1,\backslash ldots,n\_k,x))$,

where μ is the μ operator ($\backslash mu\; x\backslash ,\; \backslash phi(x)$ is the smallest natural number for which $\backslash phi(x)$ is true) and $\backslash 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$.

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

:$K\; =\; \backslash \{\; e\; \backslash mbox\{\; \}\; :\; \backslash mbox\{\; \}\; \backslash exists\; x\; T\_1(e,0,x)\; \backslash \}$

which is of the same Turing degree as the halting problem, is a $\backslash Sigma^0\_1$ complete unary relation (Soare 1987, pp. 28, 41). More generally, the set

:$K\_\{n+1\}\; =\; \backslash \{\; \backslash langle\; e,\; a\_1,\; \backslash ldots,\; a\_n\backslash rangle\; :\; \backslash exists\; x\; T\_n(e,\; a\_1,\; \backslash ldots,\; a\_n,\; x)\backslash \}$

is a $\backslash Sigma^0\_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 $\backslash Sigma^0\_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\; \backslash subseteq\; \backslash mathbb\{N\}^\{k+1\}$ is $\backslash Sigma^0\_\{n\}$ complete then the set

:$\backslash \{\; \backslash langle\; a\_1,\; \backslash ldots,\; a\_k\backslash rangle\; :\; \backslash forall\; x\; (\; \backslash langle\; a\_1,\; \backslash ldots,\; a\_k,\; x)\; \backslash in\; A)\backslash \}$

is $\backslash Pi^0\_\{n+1\}$ complete.

• Peter Hinman, 2005, Fundamentals of Mathematical Logic, A K Peters. {{isbn|978-1-56881-262-5}}
• {{cite journal | doi=10.1090/S0002-9947-1943-0007371-8 | url=https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf | author=Stephen Cole Kleene | title=Recursive predicates and quantifiers | journal=Transactions of the American Mathematical Society | volume=53 | number=1 | pages=41–73 | date=Jan 1943 | doi-access=free }} 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}}

Category:Computability theory