Kleene's T predicate

From Wikipedia, the free encyclopedia

In computability theory, the T predicate, due to Kleene, is a particular ternary relation on natural numbers that is used to obtain a normal form for computable functions and to represent computability 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-m-n theorem, the original notation used by Kleene has become standard terminology for the concept.

[edit] Definition

The definition depends on a suitable Gödel numbering that assigns natural numbers to computable functions. 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 within arithmetic.

The ternary relation T1(e,i,x) holds 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. There is a corresponding function U such that if T(e,i,x) holds 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 T1 can only be used for functions that take one input. There are additional predicates for functions with multiple inputs; the relation

Tk(e, i1,...,ik,x)

holds if x encodes a halting computation of the function with index e on the inputs i1,...,ik.

[edit] Normal form theorem

The T predicate can be used to obtain Kleene's normal form theorem for computable functions (Soare 1987, p. 15). This states that a function f(n) is computable if and only if there is an e such that for all n

f(n) \simeq U( \mu x\, T(e,n,x)),

where μ is the μ operator and \simeq holds if both sides are undefined or if both are defined and they are equal.

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 : ∃ x T(e,0,x)},

which is of the same Turing degree as the halting problem, is \Sigma^0_1 complete (Soare 1987, pp. 28, 41). Thus, once a representation of the T predicate is obtained in a theory of arithmetic, a representation of a \Sigma^0_1-complete predicate can be obtained from it.

[edit] References

  • Stephen Kleene, 1943, "Recursive predicates and quantifiers", Transactions of the AMS v. 53 n. 1, pp. 41–73. Reprinted in The Undecidable, Martin Davis, ed., 1965, pp. 255–287.
  • Robert Soare, 1987, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer.