I present to your attention a translation of the first pages of Alan Turing’s article “ON COMPUTABLE NUMBERS WITH AN APPLICATION TO THE PROBLEM OF RESOLUTION” from 1936. The first chapters contain a description of computers, which later became the basis for modern computing.
The full translation of the article and explanation can be read in the book by American popularizer Charles Petzold, entitled “Reading Turing: A Journey through Turing’s Historical Article on Computability and Turing Machines” (ISBN 978-5-97060-231-7, 978-0-470-22905-7)
Original article:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf
ON COMPUTABLE NUMBERS WITH APPLICATION TO THE RESOLUTION PROBLEM
A. M. TURING
[Received May 28, 1936 – Read November 12, 1936]
“Computable” numbers can be briefly described as real numbers whose expressions as decimal fractions are calculable in a finite number of ways. Although at first glance this article treats numbers as computable, it is almost as easy to define and explore computable functions of an integer variable, a real variable, a computable variable, computable predicates, and the like. However, the fundamental problems associated with these computable objects are the same in each case. For a detailed consideration, I chose computable numbers as a computable object because the method of considering them is the least cumbersome. I hope to soon describe the relationship of computable numbers with computable functions and so on. At the same time, research will be carried out in the field of the theory of functions of a real variable expressed in terms of computable numbers. By my definition, a real number is computable if its decimal representation can be written by a machine.
In paragraphs 9 and 10 I give some arguments to show that computable numbers include all numbers that are naturally thought to be computable. In particular, I show that some large classes of numbers are computable. They include, for example, the real parts of all algebraic numbers, the real parts of the zeros of Bessel functions, the numbers π, e and others. However, computable numbers do not include all definable numbers, as evidenced by the following example of a definable number that is not computable.
Although the class of computable numbers is very large and in many respects similar to the class of real numbers, it is still enumerable. In §8 I consider certain arguments that would seem to argue to the contrary. When one of these arguments is correctly applied, conclusions are drawn that, at first glance, are similar to those of Gödel*. These results have extremely important applications. In particular, as shown below (§11), the resolution problem cannot have a solution.
In a recent article, Alonzo Church introduced the idea of “effective calculability,” which is equivalent to my idea of “computability” but has a completely different definition. Church also comes to similar conclusions regarding the problem of resolution. The proof of the equivalence of “computability” and “effectively calculable” is presented in the appendix to this article.
1. Computers
We have already said that computable numbers are those numbers whose decimal places are countable by finite means. A clearer definition is needed here. This article will make no real attempt to justify the definitions given here until we get to §9. For now, I will just note that the (logical) rationale (for this) is that human memory is, by necessity, limited.
Let us compare a person in the process of calculating a real number with a machine that is capable of fulfilling only a finite number of conditions q1, q2, …, qR; Let’s call these conditions “m-configurations”. This (that is, so defined) machine is equipped with a “tape” (analogous to paper). This belt passing through the machine is divided into sections. Let’s call them “squares”. Each such square can contain some kind of “symbol”. At any moment, there is only one such square, say the rth one, containing the symbol that is “in this machine.” Let’s call such a square a “scanned symbol”. A “scanned character” is the only character that the machine is, so to speak, “directly aware” of. However, by changing its m-configuration, the machine can effectively remember some of the characters it has “seen” (scanned) previously. The possible behavior of the machine at any moment is determined by the m-configuration qn and the scanned symbol***. Let’s call this pair of symbols qn, “configuration”. The configuration thus designated determines the possible behavior of a given machine. In some of these configurations in which the scanned square is blank (ie, does not contain a character), the machine writes a new character on the scanned square, and in other of these configurations it erases the scanned character. This machine is also capable of moving to scan another square, but in this way it can only move to the adjacent square to the right or left. In addition to any of these operations, the m-configuration of the machine can be changed. In this case, some of the written characters will form a sequence of digits, which is the decimal part of the real number being calculated. The rest of them will be nothing more than inaccurate marks in order to “help memory”. In this case, only the above-mentioned inaccurate marks can be erased.
I claim that the operations considered here include all those operations that are used in calculation. The rationale for this statement is easier to understand for the reader who has an understanding of machine theory. Therefore, in the next section I will continue to develop the theory in question, based on an understanding of the meaning of the terms “machine”, “tape”, “scanned”, etc.
*Gödel “On the Formally Undecidable Sentences of the Principia Mathematics (published by Whitehead and Russell in 1910, 1912 and 1913) and Related Systems, Part I,” Journal of Mathematics. Physics, monthly bulletin in German No. 38 (for 1931, pp. 173-198.
** Alonzo Church, “An Undecidable Problem in Elementary Number Theory,” American J. of Math., No. 58 (1936), pp. 345-363.
*** Alonzo Church, “A Note on the Resolution Problem,” J. of Symbolic Logic, No. 1 (1936), pp. 40-41
