[FOM] Kleene's T predicate

[Martin Davis]

Trying to find a connection with Turing is hopelessly anachronistic. The
first version of the T predicate was introduced in Kleene's paper "General
Recursive Functions of Natural Numbers" Mathematische Annalen vol.
112(1936) 727-742.
A footnote reads: "Presented to the American Mathematical Society,
September 1935." The paper refers to works by Ackermann, Péter, Gödel, and
Skolem, but not Turing. The formalism to which Kleene applies Gödel
arithmetization in this paper is an equation calculus. Because it enables
derivation of the values from recursion equations going beyond "primitive"
(so named by Kleene in this paper) recursions, as for example the defining
equations of Ackermann's function, Kleene spoke of "general recursive
functions". The main result of this paper is that every general recursive
function h can be written in the form:
                    h(x) =  f(min y [g(x,y])
where f and g are primitive recursive. This Kleene Normal Form Theorem
turned proving the equivalence of different formulations of computability
into a routine chore.

What we think of as Kleene's T predicate was introduced in his "Recursive
Predicates and Quantifiers," Transactions of the American Mathematical
Society, vol. 53(1943)  41-73. What was called T in the 1936 paper is now
called S, and T is defined from S by choosing the least of the values of
one of the variables satisfying the predicate. This is to deal with the
non-determinism of the equation calculus.

In my anthology "The Undecidable" (available in a Dover reprint) are
included both of these papers as well as notes taken by Kleene and Rosser
(then graduate students) on Gödel's lectures in 1934 at which the idea of a
formalism for general recursive functions was first mentioned.

I had the idea that if one applied Kleene's methods to the Turing machine
formalism there was no indeterminancy to deal with so the development could
proceed more simply and smoothly. This is what led to my book
"Computability and Unsolvability" published in 1958, but also available as
a Dover reprint. I used the letter T as a tribute to Kleene.  It never
occurred to me to consider that it was also Turing's initial.

Martin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160523/cd7e071c/attachment-0001.html>