Information Technology Reference
In-Depth Information
Dear Professor Church,
31 May 1936
An offprint which you kindly sent me recently of your paper in which you define 'calculable numbers',
and show that the Entscheidungsproblem for Hilbert logic is insoluble, had a rather painful interest
for a young man, A. M. Turing, here, who was just about to send in for publication a paper in which he
had used a definition of 'Computable numbers' for the same purpose. His treatment - which consists in
describing a machine which will grind out any computable sequence - is rather different from yours,
but seems to be of great merit, and I think it is of great importance that he should come and work with
you next year if that is at all possible. He is sending you the typescript of his paper for your criticisms. . . .
I should mention that Turing's work is entirely independent: he has been working without any supervi-
sion or criticism from anyone. This makes it all the more important that he should come into contact as
soon as possible with the leading workers on this line, so that he should not develop into a confirmed
solitary.
16
Turing read Church's paper in the summer and added an appendix to his paper that demonstrated
that his definition of 'computable' - meaning anything that could be computed by a Turing machine - was
equivalent to what Church had called “effectively calculable” - meaning anything that could be described
by a formula using the lambda calculus. When Turing's paper was published in January 1937, Church gen-
erously reviewed it very positively in the well-known
Journal of Symbolic Logic
. He also used the description
“Turing machine” in print for the first time, writing that “a human calculator, provided with pencil and
paper and explicit instructions, can be regarded as a type of Turing machine.”
17
Search WWH ::
Custom Search