Talk:Kleene's T predicate

From Wikipedia, the free encyclopedia

[edit] Notion of T-predicate

This "predicate function" evaluates to { T, F }? { 1, 0 }? Is it a representing function? Thanks, Bill Wvbailey 17:29, 7 November 2007 (UTC)

The T predicate is a definable relation on the natural numbers (or, in some settings, it's the formula that defines that relation). It is not itself a function, although it would be possible to talk about the representing function of the T predicate.

In the study of arithmetic, it's common lingo to use the word function for something that returns a natural number, and a predicate for something that expresses a property that a number or tuple of numbers may possess. In this case, the property of e, i, and x is that x is a code for the entire computation history of program e on input i. The U function, on the other hand, returns the natural number computed by {e}(i), by decoding x and reading the output from the computation history. The only input to the U function is x. — Carl (CBM · talk) 17:51, 7 November 2007 (UTC)