Talk:Kleene's T predicate

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)

arithmetic

This page is referenced from the halting problem article as part of the explanation of why the halting problem implies a limited form of Goedel's incompleteness theorem. There's a missing point that I think could use expansion, which is that the T predicate has to use both addition and multiplication in some essential way. Unless I'm missing something, it can't be written with addition alone, the signature of Presberger arithmetic, because that theory is decidable. I guess encoding the actions of a TM in arithmetic isn't terribly hard, but it seems worth showing or mentioning how it's done, and mentioning that very weak fragments of arithmetic (or similarly geometry or Abelian groups, etc.) aren't enough. There's a natural but bogus intuition that the halting problem makes the incompleteness theorem obvious, missing the subtlety that the T predicate requires a certain amount of arithmetic strength and that it actually has to be shown that addition and multiplication are enough. By the way, what does T stand for? In complexity theory the term "tableau" sometimes describes something like the x in the T relation described here, iirc. So I wondered if that term is originally from logic. 69.228.170.24 (talk) 07:12, 27 May 2010 (UTC)

RE where does "T" come from? I traced a first occurrence back to Kleene's 1936 paper General Recursive Functions of Natural Numbers, section 2 "The undecidability, in general, which systems of equations define recursive functions" (page 248 in The Undecidable). He just pops it on the page. The paragraph before it contains the words "number-theoretic" and later he concludes:

"The definability of a non-recursive class by use of quantifiers applied to a recurive relation gives the existence of undecidable number-theoretic propositions in certain formal logics from the consideration (somewhat different from that employed by Goedel) that otherwise the logics could be used to construct recursive definitions of the class." (p. 250)

This paper is expanded and reworked in his 1943 Recursive Predicates and Quantifiers. Here (as he also does in his 1952 text) Kleene begins with recursive predicates for which he uses the symbol "R". He then introduces "the metamathematical predicate ＄_n(Z,x₁,...,x_n, Y) [＄ here is actually the German Fraktur script for S that looks like a G] is carried by the correlation into a number-theoretic predicate S_n(z, x₁,...x_n,y), the definition of which we complete by taking it as false for values of z, y not both correlated to formal objects" (p. 261 in The Undecidable). After arithmetizing equations containing R and S_n, a paragraph later he then states: "In stating these results for reference, we shall go over from S_n to a new predicate T_n..." (p. 261), and later he introduces another number theoretic function U (page 266). Thus it seems that he starts with R for recursive, and goes through the alphabet to S, T, and U.

Did he inherit this symbolism from e.g. Goedel? Perhaps. In Goedel's 1934 lectures he states "Roman capitals, R, S, T, ... will stand for classes of, or relations among, natural numbers" (p. 42). So it would appear that Goedel is going alphabetically, too. For certain the use of both Fraktur symbols and their Roman equivalents appears in Kleene in the same context as it does in Goedel's work.

In his glossary of Symbols and Notations (page 538 in Kleene 1952) Kleene lists T_n at page 281, which directs us back to almost exactly the same derivation and definitions used in his 1943 that I've synopsized above (i.e. R to S_n to T_n).

I wish this were more definitive. Bill Wvbailey (talk) 14:11, 28 May 2010 (UTC)

arithmetical hierarchy

The sentence

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

makes it sound like the T predicate can generate complete sets of arbitrary height in the hierarchy, rather than just $\Sigma _{1}^{0}$ (fixed typo). Was that intended? 69.228.170.24 (talk) 22:26, 27 May 2010 (UTC)

It does work for higher levels. I'll work on that section tomorrow. — Carl (CBM · talk) 00:12, 28 May 2010 (UTC)

Thanks. I don't understand the new addition at first glance but I'll think about it some more. 69.228.170.24 (talk) 00:42, 29 May 2010 (UTC)

It's very dense, probably only useful as a reference right now. The thing is that the passage from a universal $\Sigma _{1}^{0}$ formula in 2 free variables to a universal $\Pi _{2}^{0}$ formula in one free variable is completely standard, and so on all the way up the hierarchy. So the only real work is to obtain, for each k > 0, a universal $\Sigma _{1}^{0}$ formula with k free variables. — Carl (CBM · talk) 01:41, 29 May 2010 (UTC)

Definition of T-predicate

Kleene 1967:243 adopts this definition (I quote; in particular note the capital M re "Moment x"):

". . . we get a positive integer which describes the machine table and thence the pattern of behavior of the machine; call this number the index of the machine.[Here he adds in footnote 173 that "We have chosen this particular method of indexing, in expositions since 1956a, as being easy to explain. . . Some other methods have been more commonly used in the literature. But work done in Smullyan 1961 (not quite in the present connection) establisheds that the present system is no harder to use.)

"Now let T(i, a, x) stand for the following:

"i is the index of a Turing machine (call it "Machine M_i) which, when applied to a as argument, will at Moment x (but not earlier) have completed the computation of a value (call that value "φi(a)").

"This predicate (i.e. propostional function T(i, a, x) is "decidable"."(p. 243)

On page 233 he defines "moments of time" (lower-case) as "

"We number moments of time for the operation of the machine as 0, 1, 2, . . .. At any given mmoment, the machine sahll be in one of k + 1 states, which we number 0, 1, . . ., k."

In an example on page 237, his "Moment" heads a column of numbers, and these are clearly instants in time at which the machine is in a "configuration" e.g. at Moment 4, the machine/tape configuration is as follows:

4 0 1 1⁵ 0 1 0 0.

The article seems to indicate that x is actually a sequence, or concatenation:

". . . 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."

What am I misunderstanding here? Are there different sorts of Kleene T predicates? Thanks, BillWvbailey (talk) 19:45, 20 January 2011 (UTC)

Interesting. The T predicate described here is the one Kleene used in Introduction to Metamathematics, 1952. The one in Kleene 1967 is not Kleene's T predicate, he just used the letter T again.

The reason that the T predicate needs to quantify over computation histories, rather than the number of steps, is so that you can extract the return value at the end. The normal form theorem (Kleene 1952 p. 288) says that, for every computable function φ, there is an e such that

$(\forall x)(\phi (x)=U(\mu y.T_{1}(e,x,y)))$

The point there is that the μ operator is really searching for a computation history, and then the U function can decode the output value from it. Note that U takes only one argument, it does not get e as an input: so if the y was just a number of steps, the U function would have no way to tell what the output value should be from the information it is given. — Carl (CBM · talk) 21:09, 22 January 2011 (UTC)