Kleene's T Predicate - Definition

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.

The ternary relation T1(e,i,x) takes three natural numbers as arguments. The triples of numbers (e,i,x) that belong to the relation (the ones for which T1(e,i,x) is true) are defined to be exactly the triples in which 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, T1 first asks whether x is the Gödel number of a finite sequence 〈xj〉 of complete configurations of the Turing machine with index e, running a computation on input i. If so, T1 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, T1 finally asks whether the sequence 〈xj〉 ends with the machine in a halting state. If all three of these questions have a positive answer, then T1(e,i,x) holds (is true). Otherwise, T1(e,i,x) does not hold (is false).

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

,

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

Read more about this topic:  Kleene's T Predicate

Famous quotes containing the word definition:

    “No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
    —Florence Nightingale (1820–1910)

    “According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
    —Ana Castillo (b. 1953)

    “I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
    —Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)