Kleene's T predicate  From Wikipedia, the free encyclopedia Jump
to: navigation, search  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
smn theorem, the original notation used by Kleene has become
standard terminology for the concept.[1]   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 sim