ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM

By A. M. Turing

Received 28 May, 1936 — Read 12 November, 1936

Proceedings of the London Mathematical Society, s2-42 (1937), pp. 230–265

Part 1: Sections 1–8 — Computing Machines through the Diagonal Argument

The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions of an integral variable or a real or computable variable, computable predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the relations of the computable numbers, functions, and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers. According to my definition, a number is computable if its decimal can be written down by a machine.†

Key idea: A "computable number" is one whose decimal expansion can be produced by a mechanical, step-by-step process. This is Turing's central definition — simple but world-changing.

In §§ 9, 10 I give some arguments with the intention of showing that the computable numbers include all numbers which could naturally be regarded as computable. In particular, I show that certain large classes of numbers are computable. They include, for instance, the real parts of all algebraic numbers, the real parts of the zeros of the Bessel functions, the numbers π, e, etc. The computable numbers do not, however, include all definable numbers, and an example is given of a definable number which is not computable.

Although the class of computable numbers is so great, and in many ways similar to the class of real numbers, it is nevertheless enumerable. In § 8 I examine certain arguments which would seem to prove the contrary. By the correct application of one of these arguments, conclusions are reached which are superficially similar to those of Gödel†. These results have valuable applications. In particular, it is shown (§ 11) that the Hilbertian Entscheidungsproblem can have no solution.

The punchline: The computable numbers are enumerable (you can list all possible machines), but there's no general process for deciding if a given machine is "satisfactory." This leads to the unsolvability of the Entscheidungsproblem — the decision problem Hilbert posed.

In a recent paper Alonzo Church† has introduced an idea of "effective calculability", which is equivalent to my "computability", but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem‡. The proof of equivalence between "computability" and "effective calculability" is outlined in an appendix to the present paper.

† Gödel, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte Math. Phys., 38 (1931), 173–198.

† Alonzo Church, "An unsolvable problem of elementary number theory", American J. of Math., 58 (1936), 345–363.

‡ Alonzo Church, "A note on the Entscheidungsproblem", J. of Symbolic Logic, 1 (1936), 40–41.

1. Computing machines.

We have said that the computable numbers are those whose decimals are calculable by finite means. This requires rather more explicit definition. No real attempt will be made to justify the definitions given until we reach § 9. For the present I shall only say that the justification lies in the fact that the human memory is necessarily limited.

The thought experiment begins. Turing asks: what does a human "computer" (a person performing calculations) actually do? He strips the process to its absolute minimum.

We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q₁, q₂, ..., q_R which will be called "m-configurations". The machine is supplied with a "tape" (the analogue of paper) running through it, and divided into sections (called "squares") each capable of bearing a "symbol". At any moment there is just one square, say the r-th, bearing the symbol 𝔖(r) which is "in the machine". We may call this square the "scanned square". The symbol on the scanned square may be called the "scanned symbol". The "scanned symbol" is the only one of which the machine is, so to speak, "directly aware". However, by altering its m-configuration the machine can effectively remember some of the symbols which it has "seen" (scanned) previously. The possible behaviour of the machine at any moment is determined by the m-configuration q_n and the scanned symbol 𝔖(r). This pair q_n, 𝔖(r) will be called the "configuration": thus the configuration determines the possible behaviour of the machine. In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes down a new symbol on the scanned square: in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the m-configuration may be changed. Some of the symbols written down will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to "assist the memory". It will only be these rough notes which will be liable to erasure.

This is the Turing machine. Five components: (1) a tape divided into squares, (2) a head that reads one square at a time, (3) a finite set of internal states (m-configurations), (4) a table of rules, (5) the ability to write, erase, and move left or right. That's it — and it captures all of computation.

It is my contention that these operations include all those which are used in the computation of a number. The defence of this contention will be easier when the theory of the machines is familiar to the reader. In the next section I therefore proceed with the development of the theory and assume that it is understood what is meant by "machine", "tape", "scanned", etc.

2. Definitions.

Automatic machines.

If at each stage the motion of a machine (in the sense of § 1) is completely determined by the configuration, we shall call the machine an "automatic machine" (or a-machine).

For some purposes we might use machines (choice machines or c-machines) whose motion is only partially determined by the configuration (hence the use of the word "possible" in § 1). When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems. In this paper I deal only with automatic machines, and will therefore often omit the prefix a-.

a-machines vs c-machines: An a-machine runs on its own — every step is determined by its rules. A c-machine sometimes needs a human to make a choice. Modern computers are a-machines. Interactive programs (which wait for user input) are closer to c-machines.

Computing machines.

If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols of the first kind which are printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.

Circular and circle-free machines.

If a computing machine never writes down more than a finite number of symbols of the first kind, it will be called circular. Otherwise it is said to be circle-free.

A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind. The significance of the term "circular" will be explained in § 8.

Computable sequences and numbers.

A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle-free machine.

We shall avoid confusion by speaking more often of computable sequences than of computable numbers.

3. Examples of computing machines.

I. A machine can be constructed to compute the sequence 010101.... The machine is to have the four m-configurations "𝔟", "𝔠", "𝔢", "𝔣" and is capable of printing "0" and "1". The behaviour of the machine is described in the following table in which "R" means the machine moves so that it scans the square immediately on the right of the one it was scanning previously. Similarly for "L". "E" means the scanned symbol is erased and "P" stands for "prints". This table (and all succeeding tables of the same kind) is to be understood to mean that for a configuration described in the first two columns the operations in the third column are carried out successively, and the machine then goes over into the m-configuration described in the last column. When the second column is left blank, it is understood that the behaviour of the third and fourth columns applies for any symbol and for no symbol.

Configuration		Behaviour
m-config.	symbol	operations	final m-config.
𝔟	None	P0, R	𝔠
𝔠	None	R	𝔢
𝔢	None	P1, R	𝔣
𝔣	None	R	𝔟

Try it! The machine below runs this exact table. Press Step to advance one step at a time, or Run to watch it go. The blue-highlighted cell is the tape head. F-squares (slightly blue) hold the output figures; E-squares (dark) are scratch space.

If (contrary to the description in § 1) we allow the letters L, R to appear more than once in the operations column we can simplify the table considerably.

m-config.	symbol	operations	final m-config.
𝔟	None	P0	𝔟
𝔟	0	R, R, P1	𝔟
𝔟	1	R, R, P0	𝔟

II. As a slightly more difficult example we can construct a machine to compute the sequence 001011011101111.... The machine is to be capable of five m-configurations, viz. "𝔬", "𝔮", "𝔭", "𝔣", "𝔟" and of printing "ə", "x", "0", "1". The first three symbols on the tape will be "əə0"; the other figures follow on alternate squares. On the intermediate squares we never print anything but "x". These letters serve to "keep the place" for us and are erased when we have finished with them. We also arrange that in the sequence of figures on alternate squares there shall be no blanks.

m-config.	symbol	operations	final m-config.
𝔟		Pə, R, Pə, R, P0, R, R, P0, L, L	𝔬
𝔬	1	R, Px, L, L, L	𝔬
𝔬	0		𝔮
𝔮	Any	R, R	𝔮
𝔮	None	P1, L	𝔭
𝔭	x	E, R	𝔮
𝔭	ə	R	𝔣
𝔭	None	L, L	𝔭
𝔣	Any	R, R	𝔣
𝔣	None	P0, L, L	𝔬

Much more interesting. This machine uses scratch marks (x) on E-squares to count how many 1s to print in each run. Watch how the tape fills up — the pattern of increasing runs of 1s emerges from a simple set of rules.

To illustrate the working of this machine a table is given below of the first few complete configurations. These complete configurations are described by writing down the sequence of symbols which are on the tape, with the m-configuration written below the scanned symbol. The successive complete configurations are separated by colons.

4. Abbreviated tables.

There are certain types of process used by nearly all machines, and these, in some machines, are used in many connections. These processes include copying down sequences of symbols, comparing sequences, erasing all symbols of a given form, etc. Where such processes are concerned we can abbreviate the tables for the m-configurations considerably by the use of "skeleton tables". In skeleton tables there appear capital German and small Greek letters. These are of the nature of "variables". By replacing each capital German letter throughout by an m-configuration and each small Greek letter by a symbol, we obtain the table for an m-configuration.

Subroutines before subroutines existed. Turing invents the idea of reusable code — skeleton tables are essentially functions or macros. The capital German letters are parameters. This is 1936, decades before any programming language.

The skeleton tables are to be regarded as nothing but abbreviations: they are not essential. So long as the reader understands how to obtain the complete tables from the skeleton tables, there is no need to give any exact definitions in this connection.

Let us consider an example:

Key skeleton tables Turing defines: f(𝔈, 𝔅, a) — find the leftmost symbol a; e(𝔈, 𝔅, a) — erase all symbols a; pe(𝔈, a, β) — print β at end of sequence; ce(𝔈, 𝔅, a) — copy all symbols marked a to the end; re(𝔈, 𝔅, a, β) — replace all a by β; cr(𝔈, 𝔅, a) — copy without erasing; cp(𝔈, 𝔄, 𝔈, a, β) — compare sequences marked a and β. These compose into increasingly powerful operations — the whole universal machine is built from these primitives.

If we were to replace 𝔈 throughout by 𝔮 (say), 𝔅 by 𝔯, and a by x, we should have a complete table for the m-configuration 𝔣(𝔮, 𝔯, x). 𝔣 is called an "m-configuration function" or "m-function".

The only expressions which are admissible for substitution in an m-function are the m-configurations and symbols of the machine. These have to be enumerated more or less explicitly: they may include expressions such as 𝔭(e, x); indeed they must if there are any m-functions used at all. If we did not insist on this explicit enumeration, but simply stated that the machine had certain m-configurations (enumerated) and all m-configurations obtainable by substitution of m-configurations in certain m-functions, we should usually get an infinity of m-configurations.

5. Enumeration of computable sequences.

A computable sequence γ is determined by a description of a machine which computes γ. Thus the sequence 001011011101111... is determined by the table on p. 234, and, in fact, any computable sequence is capable of being described in terms of such a table.

It will be useful to put these tables into a kind of standard form. In the first place let us suppose that the table is given in the same form as the first table, for example, I on p. 233. That is to say, that the entry in the operations column is always of one of the forms E : E, R : E, L : Pa : Pa, R : Pa, L : R : L : or no entry at all. The table can always be put into this form by introducing more m-configurations. Now let us give numbers to the m-configurations, calling them q₁, ..., q_R, as in § 1. The initial m-configuration is always to be called q₁. We also give numbers to the symbols S₁, ..., S_m and, in particular, blank = S₀, 0 = S₁, 1 = S₂.

Encoding machines as numbers. This is the crucial move. Every machine can be written in a standard form, which can be expressed as a string of letters (the "standard description"), which can be converted to a number (the "description number"). This means machines are data — a machine can be fed to another machine.

From each line of form (N₁) let us form an expression q_i S_j S_k L q_m; from each line of form (N₂) we form an expression q_i S_j S_k R q_m; and from each line of form (N₃) we form an expression q_i S_j S_k N q_m.

Let us write down all expressions so formed from the table for the machine and separate them by semi-colons. In this way we obtain a complete description of the machine. In this description we shall replace q_i by the letter "D" followed by the letter "A" repeated i times, and S_j by "D" followed by "C" repeated the appropriate number of times. This new description of the machine may be called the standard description (S.D.). It is made up entirely from the letters "A", "C", "D", "L", "R", "N", and from ";".

If finally we replace "A" by "1", "C" by "2", "D" by "3", "L" by "4", "R" by "5", "N" by "6", and ";" by "7" we shall have a description of the machine in the form of an arabic numeral. The integer represented by this numeral may be called a description number (D.N) of the machine. The D.N determine the S.D and the structure of the machine uniquely. The machine whose D.N is n may be described as ℳ(n).

The idea that changed everything. Every possible Turing machine corresponds to a number. Every number either is or isn't a valid machine description. This means we can enumerate all possible machines by listing the integers 1, 2, 3, ... and checking each one — making the computable sequences enumerable. It also means a machine's instructions can be written on its own tape.

To each computable sequence there corresponds at least one description number, while to no description number does there correspond more than one computable sequence. The computable sequences and numbers are therefore enumerable.

Let us find a description number for the machine I of § 3. When we rename the m-configurations its table becomes:

q_i	S_j	operations	final
q₁	S₀	PS₁, R	q₂
q₂	S₀	PS₀, R	q₃
q₃	S₀	PS₂, R	q₄
q₄	S₀	PS₀, R	q₁

Our first standard form would be

q₁ S₀ S₁ R q₂; q₂ S₀ S₀ R q₃; q₃ S₀ S₂ R q₄; q₄ S₀ S₀ R q₁;

The standard description is

DADDCRDAA ; DAADDCRDAAA ; DAAADDCCRDAAAA ; DAAAADDCRDAA ;

A description number is

31332531173113353111731113322531111731111335317

A number which is a description number of a circle-free machine will be called a satisfactory number. In § 8 it is shown that there can be no general process for determining whether a given number is satisfactory or not.

6. The universal computing machine.

It is possible to invent a single machine which can be used to compute any computable sequence. If this machine 𝔘 is supplied with a tape on the beginning of which is written the S.D of some computing machine ℳ, then 𝔘 will compute the same sequence as ℳ. In this section I explain in outline the behaviour of the machine. The next section is devoted to giving the complete table for 𝔘.

The universal machine. This is arguably the single most important idea in the paper — and one of the most important in all of science. A single machine that can simulate any machine, given its description. This is the theoretical foundation of the general-purpose computer. Every laptop, phone, and server is a physical realization of this idea.

Let us first suppose that we have a machine ℳ′ which will write down on the F-squares the successive complete configurations of ℳ. These might be expressed in the same form as on p. 235, using the second description (C), with all symbols on one line. Or, better, we could transform this description (as in § 5) by replacing each m-configuration by "D" followed by "A" repeated the appropriate number of times, and by replacing each symbol by "D" followed by "C" repeated the appropriate number of times. The numbers of letters "A" and "C" are to agree with the numbers chosen in § 5, so that, in particular, "0" is replaced by "DC", and the blanks by "D". These substitutions are to be made after the complete configurations have been put together, as in (C). Difficulties arise if we do the substitution first. In each complete configuration the blanks would all have to be replaced by "D", so that the complete configuration would not be expressed as a finite sequence of symbols.

If in the description of the machine II of § 3 we replace "ə" by "DAA", "𝔮" by "DAAA", then the sequence (C) becomes:

DA : DCCCDCCCDA ADCDDC : DCCCDCCCDA AADCDDC : ...

It is not difficult to see that if ℳ can be constructed, then so can ℳ′. The manner of operation of ℳ′ could be made to depend on having the rules of operation (i.e., the S.D) of ℳ written somewhere within itself (i.e. within ℳ′); each step could be carried out by referring to these rules. We have only to regard the rules as being capable of being taken out and exchanged for others and we have something very akin to the universal machine.

Software. Read that last sentence again: "rules capable of being taken out and exchanged for others." Turing has just invented the concept of a stored program. The machine's behaviour is determined by data on its tape — change the data, change the behaviour. This is the deep reason why one laptop can run a word processor, a game, a web browser, an AI.

One thing is lacking: at present the machine ℳ′ prints no figures. We may correct this by printing between each successive pair of complete configurations the figures which appear in the new configuration but not in the old. Then (C₁) becomes

DDA : 0 : 0 : DCCCDCCCDA ADCDDC : DCCC...

It is not altogether obvious that the E-squares leave enough room for the necessary "rough work", but this is, in fact, the case.

7. Detailed description of the universal machine.

A table is given below of the behaviour of this universal machine. The m-configurations of which the machine is capable are all those occurring in the first and last columns of the table, together with all those which occur when we write out the unabbreviated tables of those which appear in the table in the form of m-functions.

The first program ever written. Section 7 contains the complete instruction table for the universal machine — effectively the first computer program in history, written 9 years before ENIAC. It uses the skeleton tables from §4 as subroutines. The key stages: (1) 𝔟 — initial setup, writes ::DA on the tape; (2) anf — marks the last complete configuration with y; (3) fom — finds the last unmarked semicolon in the S.D.; (4) fmp — compares the current configuration with the instruction being examined; (5) sim — executes the matching instruction; (6) mf — marks out the complete configuration into sections; (7) sh — examines and executes each instruction.

When 𝔘 is ready to start work the tape running through it bears on it the symbol ə on an F-square and again ə on the next E-square; after this, on F-squares only, comes the S.D of the machine followed by a double colon "::" (a single symbol, on an F-square). The S.D consists of a number of instructions, separated by semi-colons.

Each instruction consists of five consecutive parts

(i) "D" followed by a sequence of letters "A". This describes the relevant m-configuration.

(ii) "D" followed by a sequence of letters "C". This describes the scanned symbol.

(iii) "D" followed by another sequence of letters "C". This describes the symbol into which the scanned symbol is to be changed.

(iv) "L", "R", or "N", describing whether to move to left, right, or not at all.

(v) "D" followed by a sequence of letters "A". This describes the final m-configuration.

The machine 𝔘 is to be capable of printing "A", "C", "D", "0", "1", "u", "v", "w", "x", "y", "z". The S.D is formed from ";" , "A", "C", "D", "L", "R", "N".

8. Application of the diagonal process.

It may be thought that arguments which prove that the real numbers are not enumerable would also prove that the computable numbers and sequences cannot be enumerable*. It might, for instance, be thought that the limit of a sequence of computable numbers must be computable. This is clearly only true if the sequence of computable numbers is defined by some rule.

* Cf. Hobson, Theory of functions of a real variable (2nd ed., 1921), 87, 88.

The crux of the whole paper. Turing now confronts the apparent paradox: Cantor showed the reals are uncountable via the diagonal argument. But Turing just showed the computable sequences are countable (§5). Doesn't the same diagonal argument apply? The resolution is subtle and profound.

Or we might apply the diagonal process. "If the computable sequences are enumerable, let α_n be the n-th computable sequence, and let φ_n(m) be the m-th figure in α_n. Let β be the sequence with 1−φ_n(n) as its n-th figure. Since β is computable, there exists a number K such that 1−φ_n(n) = φ_K(n) all n. Putting n = K, we have 1 = 2φ_K(K), i.e. 1 is even. This is impossible. The computable sequences are therefore not enumerable".

The fallacy in this argument lies in the assumption that β is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps.

The halting problem, in embryo. The diagonal argument fails because we cannot mechanically determine which machines are circle-free (i.e., which actually produce infinite sequences vs. getting stuck). If we could, we could build β, and reach a contradiction. Since contradictions are impossible, no such determination process can exist. This is equivalent to what we now call the undecidability of the halting problem.

In fact, by applying the diagonal process argument correctly, we can show that there cannot be any such general process.

The simplest and most direct proof of this is by showing that, if this general process exists, then there is a machine which computes β. This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that "there must be something wrong". The proof which I shall give has not this disadvantage, and gives a certain insight into the significance of the idea "circle-free". It depends not on constructing β, but on constructing β′, whose n-th figure is φ_n(n).

Let us suppose that there is such a process; that is to say, that we can invent a machine 𝔇 which, when supplied with the S.D of any computing machine ℳ, will test this S.D and if ℳ is circular will mark the S.D with the symbol "u" and if it is circle-free will mark it with "s". By combining the machines 𝔇 and 𝔘 we could construct a machine ℍ to compute the sequence β′. We may suppose that it uses the E-squares beyond all symbols on F-squares, and that when it has reached its verdict all the rough work done by 𝔇 is erased.

The structure of the proof: Assume a "halting oracle" 𝔇 exists. Combine it with the universal machine 𝔘 to build ℍ, which computes β′ (the diagonal sequence). But then ask: what happens when ℍ encounters its own description number? Both possible answers ("s" and "u") lead to contradictions. Therefore 𝔇 cannot exist.

The machine ℍ has its motion divided into sections. In the first N−1 sections, among other things, the integers 1, 2, ..., N−1 have been written down and tested by the machine 𝔇. A certain number, say R(N−1), of them have been found to be the D.N's of circle-free machines. In the N-th section the machine 𝔇 tests the number N. If N is satisfactory, i.e., if it is the D.N of a circle-free machine, then R(N) = 1+R(N−1) and the first R(N) figures of the sequence of which a D.N is N are calculated. The R(N)-th figure of this sequence is written down as one of the figures of the sequence β′ computed by ℍ. If N is not satisfactory, then R(N) = R(N−1) and the machine goes on to the (N+1)-th section of its motion.

From the construction of ℍ we can see that ℍ is circle-free. Each section of the motion of ℍ comes to an end after a finite number of steps. For, by our assumption about 𝔇, the decision as to whether N is satisfactory is reached in a finite number of steps. If N is not satisfactory, then the N-th section is finished. If N is satisfactory, this means that the machine ℳ(N) whose D.N is N is circle-free, and therefore its R(N)-th figure can be calculated in a finite number of steps. When this figure has been calculated and written down as the R(N)-th figure of β′, the N-th section is finished. Hence ℍ is circle-free.

Now let K be the D.N of ℍ. What does ℍ do in the K-th section of its motion? It must test whether K is satisfactory, giving a verdict "s" or "u". Since K is the D.N of ℍ and since ℍ is circle-free, the verdict cannot be "u". On the other hand the verdict cannot be "s". For if it were, then in the K-th section of its motion ℍ would be bound to compute the first R(K−1)+1 = R(K) figures of the sequence computed by the machine with K as its D.N and to write down the R(K)-th as a figure of the sequence computed by ℍ. The computation of the first R(K)−1 figures would be carried out all right, but the instructions for calculating the R(K)-th would amount to "calculate the first R(K) figures computed by ℍ and write down the R(K)-th". This R(K)-th figure would never be found. I.e., ℍ is circular, contrary to what we have found in the last paragraph. Thus both verdicts are impossible and we conclude that there can be no machine 𝔇.

Q.E.D. This is one of the most beautiful proofs in mathematics. The machine ℍ, when examining its own description number, enters an infinite regress: to compute its R(K)-th output, it needs to simulate itself computing its R(K)-th output, which requires simulating itself again, ad infinitum. The assumption that 𝔇 exists leads to contradiction. Therefore: there is no general process for determining whether a given machine will halt.

We can show further that there can be no machine 𝔈 which, when supplied with the S.D of an arbitrary machine ℳ, will determine whether ℳ ever prints a given symbol (0 say).

Similarly there is a general process for determining whether a given machine ℳ prints 1 infinitely often. By a combination of these processes we have a process for determining whether ℳ prints an infinity of figures, i.e. we have a process for determining whether ℳ is circle-free. There can therefore be no machine 𝔈.

The expression "there is a general process for determining ..." has been used throughout this section as equivalent to "there is a machine which will determine ...". This usage can be justified if and only if we can justify our definition of "computable". For each of these "general process" problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n) [e.g. G(n) might mean "n is satisfactory" or "n is the Gödel representation of a provable formula"], and this is equivalent to computing a number whose n-th figure is 1 if G(n) is true and 0 if it is false.

End of Part 1. Turing has established: (1) a precise model of computation, (2) that all machines can be enumerated, (3) that a universal machine exists, and (4) that certain questions about machines are undecidable. In Part 2 (§§ 9–11), he applies this to show the Entscheidungsproblem — Hilbert's question of whether all mathematical truths are mechanically decidable — has a negative answer.