Turing's proof

Turing's proof is the groundbreaking demonstration by British mathematician Alan Turing that the Entscheidungsproblem—the challenge posed by David Hilbert and Wilhelm Ackermann in 1928 to devise a general algorithm for determining whether any given first-order logical statement is provable—is undecidable, meaning no such algorithm can exist for all cases.^[1] Presented in Turing's seminal 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem," received by the Proceedings of the London Mathematical Society on May 28, 1936, and published in 1937, the proof introduced the Turing machine, an abstract model of computation consisting of an infinite tape divided into cells, a read-write head, and a finite table of instructions governing state transitions based on the current symbol and configuration.^[1] Through this device, Turing formalized computable numbers as real numbers whose decimal expansions can be generated algorithmically in finite steps, establishing a precise boundary between computable and non-computable functions.^[1] The core of the proof hinges on showing the undecidability of the printing problem: given a Turing machine and a symbol (such as "0"), there is no general procedure to determine whether the machine will ever print that symbol during its computation on a blank tape.^[1] Turing employed a diagonalization argument, akin to Cantor's method for uncountable infinities, to construct a Turing machine that enumerates all possible computable sequences but produces a sequence differing from each in at least one position, proving the existence of non-computable numbers and sequences.^[1] He then reduced the Entscheidungsproblem to this printing problem by encoding logical proofs as Turing machine computations, demonstrating that if a decision procedure for the printing problem existed, it could solve the Entscheidungsproblem, leading to a contradiction since the former is impossible.^[1] This reduction also implied the undecidability of the halting problem, whether a given Turing machine halts on a specific input, which became a cornerstone example of an unsolvable problem in computation theory.^[1] Beyond resolving Hilbert's question negatively—independently of Alonzo Church's lambda calculus approach earlier in 1936—Turing's proof founded modern computability theory by clarifying the intrinsic limits of mechanical computation and inspiring the development of digital computers.^[1] It underscored that while many mathematical problems are solvable, a fundamental subset defies algorithmic resolution, influencing fields from theoretical computer science to philosophy of mind.^[1] The work's emphasis on universal machines capable of simulating any other further prefigured concepts in complexity theory and artificial intelligence.^[1]

Background

Historical Context of the Entscheidungsproblem

The Entscheidungsproblem, German for "decision problem," was formally articulated by David Hilbert and Wilhelm Ackermann in their 1928 monograph Grundzüge der theoretischen Logik. It posed the question of whether there exists a mechanical procedure—or algorithm—that could determine, for any well-formed statement in the language of first-order predicate logic, whether that statement is provable from a given set of axioms within a formal system.^[2] This formulation built on earlier work in mathematical logic, emphasizing the need for a systematic method to resolve questions of provability without relying on intuition or infinite processes.^[2] The problem was deeply intertwined with Hilbert's broader foundational program, which sought to secure mathematics against paradoxes and inconsistencies by fully axiomatizing it in finite terms and proving the consistency of these axiomatic systems using only finitary reasoning.^[3] Originating from Hilbert's addresses in the 1920s, including his 1926 paper "Über das Unendliche," the program envisioned mathematics as a concrete, combinatorial activity amenable to rigorous verification, with the Entscheidungsproblem serving as a key tool for automating checks on theoremhood and thereby supporting consistency proofs. Solving it affirmatively would have reinforced the idea that mathematics could be mechanized and its reliability guaranteed through explicit, step-by-step methods.^[3] In 1936, Alonzo Church provided an independent negative resolution to the Entscheidungsproblem, demonstrating its undecidability by extending his lambda calculus framework to show that no general algorithm exists for determining the provability of sentences in classical first-order logic.^[4] Church's result, outlined in "A Note on the Entscheidungsproblem" and building on his earlier work on effective calculability, appeared in the Journal of Symbolic Logic (volume 1, number 1, pages 40–41), predating the full publication of related efforts.^[4] Shortly thereafter, Alan Turing submitted his paper "On Computable Numbers, with an Application to the Entscheidungsproblem" on 28 May 1936 to the Proceedings of the London Mathematical Society, where it was read on 12 November and published in two installments on 30 November and 23 December 1936 (series 2, volume 42, pages 230–265).^[5] Turing's analysis, while overlapping with Church's in conclusion, introduced a novel computability model that would prove influential beyond the immediate context of the decision problem.^[5]

Turing's 1936 Paper and Approach

In his seminal 1936 paper, Alan Turing motivated the need for a precise formalization of the concept of "computable" numbers by highlighting paradoxes that emerge when attempting to define computability directly in terms of real numbers, such as those akin to Richard's paradox involving diagonal arguments on decimal expansions.^[5] To avoid these issues, Turing proposed modeling computation as a simple mechanical process performed by a human "computor" operating under finite rules, thereby capturing the intuitive notion of effective calculability without reliance on ambiguous real-number manipulations.^[5] This approach addressed the broader challenge of the Entscheidungsproblem posed by David Hilbert, by demonstrating that no general algorithm exists to decide the truth of mathematical statements in first-order logic.^[5] Turing introduced the Turing machine as an abstract device designed to simulate this human computation process.^[5] The machine consists of an infinite tape divided into cells, a reading/writing head that moves along the tape, and a finite set of internal states (or "configurations") that dictate actions based on the symbol scanned.^[5] Through this model, any computable real number could be generated as a sequence of digits produced by the machine's operations, providing a clear criterion for computability tied to finite mechanical steps.^[5] The paper's structure unfolds systematically across its sections. Sections 1 through 5 establish the foundational concepts, including the definition of computing machines, examples of their operation, and the enumeration of computable sequences.^[5] Sections 6 and 7 detail the universal computing machine, capable of simulating any other Turing machine given its description as input.^[5] Sections 8 and 9 apply the diagonal process to prove the existence of non-computable numbers and delineate the scope of computable ones, while section 10 provides examples of broad classes of computable numbers, such as those defined by algebraic equations or continued fractions.^[5] Finally, section 11 extends these results to the undecidability of the Entscheidungsproblem.^[5] Historically, Turing's machine model was soon recognized as equivalent to other contemporary formalisms of computation, such as the recursive functions developed by Kurt Gödel, Stephen Kleene, and Alonzo Church, with Kleene demonstrating this equivalence in 1936 by showing that partial recursive functions precisely match the functions computable by Turing machines.^[6]

Formal Foundations

Turing Machines and Configurations

In his 1936 paper, Alan Turing introduced a formal model of computation known as a "computing machine" to capture the intuitive notion of algorithmic processes. This machine consists of an infinite tape divided into squares, each of which can bear a single symbol from a finite alphabet, typically including 0, 1, and a blank symbol. A read-write head scans one square at a time, allowing the machine to erase or print symbols on the scanned square and then move the head one step to the left or right. The machine operates in one of a finite number of states, termed m-configurations, with a designated initial m-configuration from which computation begins; halting occurs when the machine enters a final state or follows a specific instruction to stop.^[5] The behavior of the machine is determined by a transition table, also called a table of behavior, which specifies, for each combination of current m-configuration and scanned symbol, the action to take—such as printing a particular symbol (denoted P followed by the symbol), erasing the scanned symbol (E), moving right (R) or left (L)—along with the next m-configuration to enter. M-configurations represent the internal "state of mind" of the machine, analogous to the finite steps in a human computation, while a complete configuration provides a full snapshot of the machine's status at any moment, encompassing the current m-configuration, the position of the scanned square, and the entire contents of the tape (which may be partially blank). These complete configurations evolve step by step according to the transition table, forming a sequence that describes the computation's progress.^[5] Turing distinguished between machines that enter a "circle," a sequence where a complete configuration repeats, leading the machine to halt or produce only finitely many symbols, and "circle-free" machines, which never repeat a configuration and thus continue indefinitely, printing an infinite sequence of symbols without looping. Circle-free machines are particularly significant for defining computable real numbers as the outputs generated on the tape. For instance, a simple machine might start in m-configuration q_1 with a blank tape, print a 1 on the scanned square (P1), move right (R), enter m-configuration q_2, and then halt, resulting in a tape bearing a single 1. Another example is an erasing machine that, upon scanning a 0 or 1 in certain m-configurations, erases the symbol (E) and moves accordingly, effectively clearing portions of the tape.^[5]

Computable Numbers and Real Numbers

In Turing's framework, a real number is computable if there exists a Turing machine capable of producing its infinite expansion—typically in decimal or binary form—through a successive approximation process, where the machine outputs digits one at a time in a non-terminating computation.^[5] This process relies on the machine entering a series of configurations that generate the digits sequentially, allowing the number to be approximated arbitrarily closely by finite initial segments of the expansion.^[5] Computable numbers thus encompass familiar constants like \pi or e, whose digits can be algorithmically generated without bound, but exclude those requiring infinite or non-algorithmic choice at each step.^[5] Turing distinguishes computable numbers from broader computable sequences and functions by grounding them in the output of circle-free Turing machines, which perform infinite computations to produce unending digit sequences.^[5] A computable sequence is one generated by such a machine as a list of symbols (e.g., digits), whereas computable functions map inputs to outputs via finite or infinite processes, but for numbers, the focus is on the specific infinite sequence defining the decimal places.^[5] Finite computations suffice for rational numbers with terminating expansions, but irrational computable numbers demand ongoing, non-halting machine activity to reveal all digits.^[5] To demonstrate that not all real numbers are computable, Turing employs a diagonalization argument, enumerating all computable reals as \alpha_1, \alpha_2, \dots, where each \alpha_n is the output of the nth Turing machine.^[5] He then constructs a new real number \beta that differs from \alpha_n in its nth digit for every n, ensuring \beta cannot match any computable number and thus is uncomputable.^[5] This diagonal number \beta is formed simply: if d_n denotes the nth digit of \alpha_n, then the nth digit of \beta is $1 - d_n if d_n = 0, and 0 otherwise (adjusting for binary or decimal bases to avoid representational ambiguities).^[5] The diagonalization can be expressed as:

\beta = 0.d_1' d_2' d_3' \dots

where (d_n' = \begin{cases} 1 & \text{if } d_n = 0 \ 0 & \text{otherwise} \end{cases}) This construction guarantees \beta \neq \alpha_n for all n, proving the existence of uncomputable reals within the continuum.^[5]

Undecidability Proofs

First Proof: Circle-Free Machines

Turing's first proof demonstrates the undecidability of determining whether a given Turing machine is "circle-free," meaning it produces an infinite sequence of symbols on its tape without ever repeating a complete configuration, thereby computing an infinite decimal expansion of a real number.^[5] A machine is circular if it eventually writes only a finite number of symbols of the first kind (0s and 1s used for the expansion) and then loops without further expansion.^[5] The problem is to decide, given the standard description (S.D.) of a machine, whether it is circle-free or circular.^[5] Assume, for contradiction, that a machine D exists which can determine this: it takes the S.D. of any machine as input and marks it with "s" if circle-free or "u" if circular.^[5] Using D alongside the universal machine U (which simulates any machine given its S.D.), Turing constructs a machine J that enumerates the computable numbers.^[5] Machine J operates in sections, processing description numbers (D.N.s) from 1 onward: for each N, it uses D to check if N describes a circle-free machine; if so, it computes the first R(N) figures of the N-th computable number's expansion, where R(N) is defined recursively as 1 plus the sum of previous expansions' lengths, and appends them to its output sequence β'.^[5] If N is circular, J skips it and proceeds.^[5] This J is designed to be circle-free, as it continues processing indefinitely, producing an infinite sequence.^[5] Let K be the D.N. of J itself. When J reaches its K-th section, it applies D to K. If D marks K with "s" (circle-free), then J must compute and output the first R(K) figures of its own expansion β', including the R(K)-th figure.^[5] However, at that point, J has not yet computed that figure, leading to a contradiction: it cannot output a figure it has not yet determined, implying J must be circular, which contradicts the "s" verdict.^[5] Conversely, if D marks K with "u" (circular), J skips the section but continues operating circle-free, again contradicting the verdict.^[5] Thus, no such D can exist, proving the undecidability of circle-freeness.^[5] This result extends to a broader reductio ad absurdum for the computability of real numbers. If a decider for circle-freeness existed, then J could enumerate all computable real numbers by including expansions only from circle-free machines, effectively listing every computable real.^[5] One could then construct a real number whose decimal expansion differs from the n-th computable real in the n-th position (via diagonalization), yielding a non-computable real.^[5] But if all reals were computable, this diagonal real would also be computable and appear in the list, leading to a contradiction.^[5] Therefore, not all real numbers are computable, and the set of computable numbers is countable.^[5] As an illustrative example, consider a machine that takes its own S.D. as input: if the decider D predicts it is circle-free (will halt or expand infinitely), the machine instead enters a non-expanding loop (becomes circular); if D predicts circular, it expands infinitely.^[5] This self-referential construction mirrors the diagonal contradiction in J's behavior.^[5]

Second Proof: Printing a Specific Symbol

In Turing's second proof of undecidability, he establishes that there exists no general computing machine capable of determining, for an arbitrary Turing machine M and a specific symbol S (such as 0), whether M ever prints S during its computation starting from a blank tape. This property captures a fundamental limitation on mechanical decision procedures for machine behaviors, building on the formal model of computation introduced earlier in his work. The proof proceeds by reducing the printing problem to the circle-free problem proved undecidable in the previous section.^[5] To prove this, Turing employs a reductio ad absurdum argument. Assume, for contradiction, that such a deciding machine E exists: given the standard description (S.D.) of M and the symbol S, E determines whether M prints S at some point. Using E, Turing constructs auxiliary machines H_i for each i, where H_i simulates M but replaces the i-th occurrence of S (e.g., 0) with a special marker symbol. A further machine X combines these with E and a generator of descriptions to test whether M prints S infinitely often by successively querying E on whether H_i prints the marker (indicating at least i prints of S by M). If E always affirms for increasing i, M prints S infinitely often, relating directly to whether M is circle-free in producing infinite expansions.^[5] This construction implies that E would allow deciding circle-freeness (e.g., infinite printing of digits), contradicting the undecidability result from the first proof. Therefore, no such E can exist.^[5] This result aligns with the modern perspective encapsulated in Rice's theorem, which generalizes that any non-trivial semantic property of the functions computed by Turing machines—such as whether the output ever includes a particular symbol—is undecidable. In this context, the property of "ever printing a specific symbol" is non-trivial, as it holds for some machines (e.g., one that immediately prints 0) but not others (e.g., one that prints only 1s forever). For a concrete illustration, consider a machine M intended to compute a real number's expansion using 0s and 1s. The machines H_i would allow E to probe how many 0s M prints; if E enables determining infinite 0s (circle-free), it contradicts the prior undecidability, underscoring how the proof exploits the linkage between finite and infinite printing behaviors.^[5]

Third Proof: Application to the Entscheidungsproblem

Turing demonstrated the undecidability of the Entscheidungsproblem by reducing it to the previously established undecidability of determining whether a Turing machine prints a specific symbol.^[5] Specifically, he showed that if there existed an algorithm to decide, for any formula in the first-order functional calculus with equality (system K), whether it is provable, then one could construct a Turing machine to enumerate all possible proofs in canonical order and check membership, thereby deciding provability for assertions encoding machine behaviors.^[5] Central to this reduction is the encoding of Turing machine computations into logical formulas. Any computable function, including the simulation of logical proofs or validations, can be represented as a Turing machine computation, allowing machine states, tape configurations, and transitions to be formalized using predicates for positions, symbols, and moves within system K.^[5] For a given Turing machine M starting on a blank tape, Turing constructed the formula Un(M), which asserts that M eventually prints the symbol 0 (S₁) in some complete configuration.^[5] Lemma I states that if 0 appears on the tape in some complete configuration of M, then Un(M) is provable in K, as the finite computation leading to that configuration can be axiomatized and derived as a proof.^[5] Lemma II asserts the converse: if Un(M) is provable, then 0 must appear in some complete configuration of M, relying on the soundness of the logical system.^[5] Thus, the provability of Un(M) is equivalent to whether M prints 0, reducing the printing problem to logical provability.^[5] Assuming a decider for the Entscheidungsproblem exists, one could systematically test the provability of Un(M) for any M; if provable, M prints 0 (and is thus circle-free in the relevant sense); if not, it does not. This would yield an algorithm to decide the printing problem for all machines, contradicting the undecidability result from Section 8 of the paper.^[5] Therefore, no such general decision procedure for provability in first-order logic exists.^[5] As an illustrative example, consider encoding a specific halting computation as a formula in K: the assertion Un(M) for a machine M designed to halt only if it prints 0 after a sequence mimicking a non-halting loop otherwise. If Un(M) were provable, the machine halts by printing 0; deciding its provability would resolve the halting, but since halting is undecidable, no algorithm can determine this provability uniformly.^[5] A technical flaw in the original encoding of system K was identified by Paul Bernays, prompting Turing to issue a correction in 1937 that refined the logical formalism while preserving the undecidability result; this also clarified that provability in K is semi-decidable, as a Turing machine can enumerate all theorems but cannot confirm non-provability in finite time.^[7]

Complications and Analysis

Technical Errors and Corrections

Turing's 1936 paper contained several technical errors and ambiguities, particularly in the definition of the universal machine described in Section 6, where the encoding of machine descriptions onto the tape was presented in a terse and idiosyncratic manner that left some aspects unclear, such as the precise handling of state transitions and symbol substitutions during simulation. These ambiguities complicated the construction's verification but did not undermine the overall concept of universality. Additionally, the third proof, which applied the earlier undecidability results to the Entscheidungsproblem, flawedly assumed full decidability for certain machine behaviors; specifically, it treated the non-printing of a particular symbol as conclusive evidence that the machine would never print it, overlooking the possibility of infinite loops (or "circlings") that prevent termination without printing. This error conflated decidable properties—where both affirmative and negative cases can be confirmed—with semi-decidable ones, where only the affirmative case (e.g., printing the symbol) is verifiable in finite time. Paul Bernays identified this issue in 1937, prompting Turing to issue a correction acknowledging the oversight and clarifying that the proof establishes semi-decidability for the relevant predicates, thereby preserving the undecidability of the full Entscheidungsproblem. Martin Davis, in his 1965 edition of seminal papers on undecidability, provided a detailed analysis of Turing's work, including clarifications to the notation for machine configurations—such as correcting inconsistent use of italics for state symbols—and identifying several minor technical slips in the exposition, ranging from imprecise definitions of moves to errors in example computations.^[8] These notes emphasized the paper's outline-like structure, which prioritized conceptual innovation over rigorous detail, while confirming that the core arguments remained sound after adjustments. Davis's editorial interventions helped standardize Turing's formalism for later researchers, bridging gaps in the original text without altering its foundational results. Emil Post, in a 1947 appendix to his paper on recursive unsolvability, offered a thorough critique of Turing's circle-free and printing theorems, reworking both to eliminate errors arising from Turing's "conventions" (restrictions on machine behavior to avoid ambiguities). Post demonstrated that these conventions rendered the sets of valid description numbers non-recursively enumerable, complicating the undecidability proofs, and provided error-free versions using simpler (0,1)- or state-transition conventions that preserved the theorems' conclusions. He praised Turing's innovative approach but highlighted its terse style as a source of the issues, noting that the proofs' intuitive form required such reworkings for formal precision. Despite these corrections, the errors did not invalidate the central results on computability and undecidability, as the flaws were localized and resolvable; however, they initially hindered clear understanding and dissemination of the paper among contemporaries.

Interpretive Challenges and Modern Views

One significant interpretive challenge in Turing's 1936 paper arises from its use of obscure notation rooted in 1930s mathematical conventions, such as the "standard description" (S.D.), which encodes machine behaviors using a limited alphabet of symbols like A, C, D, L, R, and N, without modern diagrammatic aids or pseudocode.^[9]^[5] This notation, while precise for its era, demands substantial effort to unpack, as it lacks explicit step-by-step algorithms and instead relies on implicit descriptions of machine transitions via quintuples.^[9] Additionally, the paper assumes a high level of reader familiarity with real analysis, including concepts like continued fractions and the uncomputability of certain real numbers, which were not yet standardized in computability contexts, leading to potential ambiguities in how Turing's machines approximate infinite sequences.^[9] In modern interpretations, Turing's undecidability proofs are widely recognized as equivalent to the halting problem, where no Turing machine can determine for arbitrary inputs whether another machine will halt, a result achieved through diagonalization similar to Cantor's argument on uncountable reals.^[9] This equivalence underscores the paper's foundational role in computability theory, with links to Gödel's incompleteness theorems established via oracle machines, which extend Turing machines to handle undecidable queries and reveal parallels between formal systems' limitations and computational ones.^[9] Central to these views is the Church-Turing thesis, which posits that Turing machines capture all forms of effective computation, a conjecture supported by the independent formulations of λ-calculus and recursive functions around the same period, though it remains unproven.^[9] As of 2025, Turing's core proof remains unchanged, but its implications have extended to quantum computing limits, where even quantum Turing machines cannot resolve undecidable problems like the halting problem, reinforcing the physical Church-Turing thesis that no physical process exceeds classical computational bounds in principle.^[10] In artificial intelligence, the undecidability results imply no general algorithm exists to verify that all machine learning models halt on given inputs, complicating safety alignments in large language models and generative AI systems.^[11] Turing's work also profoundly influenced complexity theory, providing the universal Turing machine model that underpins distinctions like P versus NP, where polynomial-time solvability questions trace roots to the efficiency limits exposed in his 1936 analysis.^[9] Furthermore, it informs digital physics, viewing the universe as a vast computation governed by Turing-like rules, though hypercomputation proposals beyond these limits remain speculative.^[9]

Supporting Materials

Glossary of Turing's Terms

In his 1936 paper, Alan Turing introduced a precise vocabulary to formalize the model of computation via abstract machines, ensuring unambiguous descriptions of processes that generate infinite sequences approximating real numbers.^[5] Complete configuration: A snapshot of the machine's state at any moment, comprising the current m-configuration (internal state), the position of the scanned square on the tape, and the infinite sequence of symbols appearing on the tape to the left and right of the scanned square. This term emphasizes completeness to eliminate any ambiguity in predicting the machine's subsequent behavior, as partial descriptions might overlook essential historical details from prior operations.^[5] (p. 232) Computing machine: An abstract device, also termed an "automatic machine," consisting of an infinite tape divided into squares, a scanning head that reads and writes symbols (initially blanks, 0, or 1), and a finite set of internal states (m-configurations) dictating transitions based on the scanned symbol, including possible movements left or right. The term derives from its role in "computing" infinite decimal expansions of real numbers through successive prints of figures on the tape.^[5] (pp. 231–232) Figure: Any single symbol from the alphabet {0, 1} that the computing machine prints on the tape squares to form the computed sequence. This basic unit, chosen for its simplicity in representing binary expansions, underpins the generation of computable real numbers as limits of such sequences.^[5] (p. 231) Circular: A property of a computing machine that prints only a finite number of figures (0s and 1s) during its operation, after which it either halts or repeats configurations without producing further output. The term evokes a closed loop or cycle in the machine's behavior, contrasting with productive computation of infinite sequences.^[5] (p. 233) Circle-free: A computing machine that generates an infinite sequence of figures without ever halting or entering a repetitive cycle that prevents further printing. Etymologically linked to avoiding "circles" (loops), this designates machines capable of simulating continuous computation, essential for defining computable real numbers whose expansions require unending processes.^[5] (p. 233) S.D (standard description): A canonical, linear encoding of a computing machine's transition table as a finite sequence over the alphabet {D, A, C, L, R, N, ;}, obtained by replacing each state q_i with 'D' followed by i 'A's, each symbol s_j with 'D' followed by j 'C's, inserting the movement instruction (L for left, R for right, N for none), and separating the encoded quintuples with ';'. This standardized format, introduced to facilitate enumeration and simulation of machines, transforms the irregular table into a uniform string interpretable as a real number's description.^[5] (p. 240) Un(α): A formula in the normal system N asserting that the computing machine with standard description α prints the symbol 0 (S₁) in at least one complete configuration. Its provability corresponds to the machine ever printing 0, used in the formal encoding of assertions about machine behavior to support the reduction to the Entscheidungsproblem.^[5] (p. 260) β': A specially constructed sequence derived diagonally from an enumeration of all computable sequences, where the nth figure of β' is chosen to differ from the nth figure of the nth computable sequence. This modified variant, primed to highlight alteration, demonstrates the existence of a non-computable real number by evading any complete listing.^[5] (p. 247) D (diagonal process): A method for constructing a real number whose binary expansion differs in the nth position from the nth number in any purported enumeration of computable numbers, proving the enumeration incomplete. Named after the diagonal argument technique originally from Cantor's work on uncountability, it is adapted here to show the uncomputability of the full set of real numbers.^[5] (p. 246) H (halting decider): A hypothetical universal machine that, given the standard description of any computing machine α and an initial configuration, determines whether α is circle-free (i.e., runs indefinitely without halting). The letter H likely abbreviates "halting" or "history," central to the undecidability proof by assuming its existence and deriving a contradiction.^[5] (p. 247) R (printing decider): A proposed machine that, supplied with the standard description of a computing machine and a specific figure (symbol), decides whether that machine ever prints the given figure during its operation. Denoted R for its focus on "printing" or "result," it forms the basis of the second undecidability proof by revealing inconsistencies in decision procedures.^[5] (p. 248) N (normal system): A formal system encoding mathematical logic (propositions, assertions like Un(α)) into sequences manipulable by a computing machine, enabling the simulation of deduction within the machine model. The term "normal" suggests a standardized, normalized representation for logical expressions, facilitating the reduction of the Entscheidungsproblem to machine computability.^[5] (p. 252)

Key Notation and Examples

Turing employed a precise notation to describe the behavior of his abstract computing machines, distinguishing between states, symbols, and complete configurations of the machine. States, representing the machine's internal conditions, are typically denoted by Greek letters such as q_1 for the initial state or other identifiers like b or c. Symbols on the tape are represented numerically, with 0 and 1 as basic figures, blanks as none or a special symbol, and additional marks like x or other letters for auxiliary purposes. Configurations, which capture the full snapshot of the machine—including its current state, the scanned symbol under the head, and the sequence of symbols on the tape—are conventionally rendered in italics, as emphasized in analyses by Martin Davis.^[5] A simple example of such a configuration is q_1 0110, indicating that the machine is in the initial state q_1, with its head scanning the first 0, and the tape extending to the right as 0110 (with blanks assumed to the left and further right unless specified). This notation allows tracking the machine's evolution step by step; for instance, if the machine in state q_1 scanning 0 prints a 1 and moves right to state q_2, the next configuration becomes q_2 1110. Such representations facilitate the simulation of machine operations without ambiguity.^[5] In the context of the undecidability proofs, Turing's notation illuminates key constructions like the diagonal argument for non-computable numbers. Here, computable real numbers are enumerated as infinite binary sequences produced by machines, say the n-th machine yields digits d_{n1}, d_{n2}, \dots. The diagonal number is then formed as a sequence \delta where \delta_n = 1 - d_{nn} for each position n, ensuring \delta differs from every computable sequence at the n-th position and thus cannot be computed by any machine. This diagonalization directly ties the notation to the proof of uncomputability.^[5] For illustrating circles—closed loops in the machine's state transitions that cause finite repetition—Turing provides examples of machines entering cyclic behavior on specific tape patterns. Consider a machine configured to process a tape showing "aba" (with the head on the central 'b'), where transitions lead back to an identical configuration after altering symbols in a repeating manner, such as replacing parts of "aba" while returning the head and state to the start, forming a circle that prevents infinite computation. This looping pattern underscores the distinction between circular (non-halting on some inputs) and circle-free machines, central to defining computable processes.^[5] In an addendum published in 1937, Turing issued corrections to Section 9 of the original paper concerning the extent of computable real numbers. He revised the association between computable sequences and reals to address ambiguities, such as cases where limits of computable sequences might not be computable (e.g., the Euler constant). The updated scheme maps a computable sequence starting with figure i, followed by n 1's, a 0, and further figures c_r (r ≥ 1), to the real number (2i - 1) n + \sum_{r=1}^\infty (2 c_r - 1) 2^{-r}, ensuring all intuitively computable numbers are captured while preserving the theory's validity despite some representations becoming non-unique.^[12]