Make “mechanical” observable

Turing begins with real numbers whose binary expansions can be written by finite means. He postpones the defence of his definition until Section 9, allowing the formal model to become familiar first. When the defence arrives, it does not appeal to electronics. It examines a person calculating on paper and asks what distinctions and actions must be available at one moment of a mechanical computation.

The written record may be indefinitely extensible, but the calculator’s immediate awareness is bounded. Only finitely many symbols can be reliably distinguished. Only a bounded portion of the record can be observed at once. The internal “state of mind” relevant to continuing the procedure must fall into finitely many distinguishable conditions. If two mental conditions make no difference to any subsequent move, the procedure need not treat them as different states. If they do make a difference, the difference must be recoverable by a finite instruction.

Turing’s initial machine makes this analysis literal. The tape is divided into squares, each bearing one symbol from a finite alphabet. Exactly one square is scanned. A finite set of m-configurations supplies the control state. The pair formed by current m-configuration and scanned symbol determines what the machine may do: print or erase a symbol, move one square and adopt another m-configuration.

Why begin with computable numbers?

The paper’s chosen object is a real number written as an infinite binary decimal. This may appear narrower than the modern idea of a programme taking an input and returning an output. Turing chooses it because the essential difficulty can be displayed without a heavy theory of data types. A circle-free machine gradually commits itself to an observable stream of 0s and 1s. Each new figure is a finite event, even though the completed infinite sequence is never present at one finite time.

This choice also forces a useful separation between the machine’s rough work and its mathematical output. Marks used for addressing, copying or comparison need not be figures in the computed sequence. A machine can therefore use an expanding working record while emitting a sparse result. Turing’s definition extracts the figure subsequence from the whole tape history. That extraction is why a machine which remains active but ceases to print figures is circular for his purpose.

A computable sequence is generated by a circle-free machine. A computable number is, with an integer adjustment allowed, the real represented by that binary sequence. Turing later extends the framework to functions and predicates. The companion keeps returning to sequences because they make the output obligation visible: circle-freeness is not merely endless activity, but an unending supply of designated result symbols.

That list is deliberately atomic. A rule such as “find the next blank” is not a primitive. It must be compiled into repeated one-square moves and state changes. Nor is “compare these two remote blocks” primitive. A finite table must mark positions, shuttle between them and remember the comparison status through symbols or states. Skeleton tables later abbreviate such routines, but Turing insists that abbreviation does not add power. Each shorthand can be expanded into an ordinary finite table.

A transition table contains no forecast of the eventual answer. It need not know whether the run will finish, repeat or continue producing figures. It only specifies what follows now. This is why the model has no foresight. Global behaviour emerges from repeatedly applying local rules to a changing written configuration.

Compilation removes hidden cleverness

Natural-language instructions often conceal a large primitive. “Copy the block”, “return to the last marker” and “compare the two numerals” sound like single actions because a trained reader supplies a method. Turing’s skeleton tables permit such phrases only as abbreviations for finite networks of ordinary configurations. The expansion requirement is a safeguard. It prevents explanatory work from disappearing into the name of an operation.

Consider “find the next figure to the left”. A compiled routine needs a search state, a rule for each possible scanned symbol, repeated left moves, and a state change when 0 or 1 is found. If the tape alphabet includes markers, the table must specify their treatment too. The routine may be tedious, yet each obligation is inspectable. A critic can point to a missing case rather than argue about whether the word “find” contains insight.

This compilation discipline remains relevant to agentic systems. A diagram may label one box “reason about exceptions”, but that label is not yet a transition contract. Which observations are available, where earlier facts are recorded, what constitutes an exception and which next actions are permitted? Turing’s analysis does not say that every modern system must resemble a one-tape machine. It says that a mechanical claim earns clarity when its apparently intelligent verbs can be expanded into executable distinctions and local changes.

A table in motion

Turing distinguishes the machine’s complete configuration from its local configuration. A complete configuration records the entire non-blank tape, the scanned-square position and the current m-configuration. A local configuration is merely the m-configuration plus scanned symbol. The local pair determines one move; successive moves generate a history of complete configurations.

Turing’s computing machines print two distinguished kinds of symbol, 0 and 1, called figures. Other marks may serve as rough work. The computed sequence is the subsequence of figures printed during the run. A machine is circle-free if it continues to print infinitely many figures. It is circular if it prints only finitely many, whether because it stops, repeats a configuration or continues moving while producing only work symbols.

This historical vocabulary is easy to flatten into the modern halting problem. The relationship is close, and later theory unifies many such undecidable properties by reduction. Yet source fidelity requires the distinction. Turing’s direct classifier in Section 8 concerns whether a computing machine is circle-free. A later construction shows that no machine can decide whether an arbitrary machine ever prints a specified symbol. Saying only “Turing proved the halting problem” hides both targets and the route connecting them.

Three ways a run can fail its output contract

A machine can stop because no instruction applies. It can enter a recurring complete configuration, after which deterministic motion repeats the same future. Or it can continue through novel complete configurations while never again printing a figure. All three are circular, but the evidence available to an observer differs. A repeated complete configuration is a finite certificate of periodic future behaviour. A stopped configuration is directly visible. Mere delay in figure production supplies neither certificate.

This distinction explains why simulation alone cannot implement the required classifier. If a candidate is circle-free, continued simulation will eventually reveal each requested next figure. Positive evidence accumulates. If it is circular through an obvious halt or detected repeat, a finite negative certificate may appear. But a candidate which is currently silent may be preparing another figure after an enormous finite computation. “Not yet” never becomes “never” merely because more time has passed.

Dovetailing improves coverage, not decision. An enumerator can simulate the first candidate for one step, the first two for two steps, and so on, ensuring that no productive candidate is permanently starved of computation. This reveals prefixes from many circle-free machines. It still cannot place the candidates into a finished effective list of computable sequences because the nth row requires knowing which earlier descriptions will never qualify.

A common misconception places all intelligence in the tape. The tape records symbols, but its marks do nothing by themselves. Control lies in the transition table and current m-configuration. Conversely, placing all intelligence in the table also misleads. The same finite rules can act differently because the record and head position differ. Computation is the trajectory produced by control, record and local observation together.

Rules become data

To reason about all machines, Turing must make a machine table itself writable. He first converts any table to a standard form, numbers its m-configurations and rewrites each instruction using a small alphabet. A standard description is a string over symbols such as A, C, D, L, R and N. Replacing these symbols by digits yields a description number, or D.N.

This encoding does not claim that the decimal integer resembles the machine’s behaviour. It supplies a finite, mechanically parseable name. Different descriptions can compute the same sequence, but one well-formed description determines at most one automatic machine and hence at most one output sequence. Syntax has become admissible input.

Once descriptions are writable, Turing constructs a universal computing machine U. Supply U with the standard description of another machine M. U keeps a representation of M’s current complete configuration, finds the applicable instruction in the supplied description, updates the represented tape and repeats. The figures written by U match those of M.

Calling U a stored-program computer is a useful lineage claim if kept qualified. Both place instructions in an inspectable symbolic store, and both allow a fixed mechanism to realise many procedures. Turing’s 1936 construction is nonetheless a mathematical interpreter over encoded tables, not a specification of registers, random-access memory or the timing architecture of a later electronic machine.

What the universal machine must keep straight

U does not hand its physical tape directly to the simulated machine. It maintains symbolic descriptions of both the simulated table and a current complete configuration. For each simulated move it must locate the current m-configuration in the description, compare the encoded scanned symbol, find the matching instruction, alter the represented tape and record the new simulated state. The construction is lengthy because every act of interpretation is itself reduced to local table operations.

This creates two levels that should not be merged. At the object level, M scans one of its represented squares and changes state. At the interpreter level, U scans symbols that encode M’s state, tape and instructions. A mark which means “move right” within the description does not make U’s own head simply move right once. U must interpret that mark by updating the stored representation of M’s head position.

The separation anticipates a durable architecture: programme text, machine state and interpreter state are different objects even when they occupy one physical medium. It also prevents a casual claim that data and code are intrinsically identical. They are exchangeable roles under an interpreter and an encoding convention. Without the convention and the interpreting transition rules, the description ribbon is only a string of marks.

The diagonal needs a classifier

Machine descriptions are enumerable. List the natural numbers, reject those that are not well-formed description numbers and interpret the rest as machines. It is tempting to say that computable sequences are therefore effectively enumerable, place them in rows and flip the diagonal bit to produce a missing computable sequence. That conclusion is too quick.

A description can name a circular machine. To obtain the nth computable sequence, an enumerator must find the nth description of a circle-free machine. Merely running candidates in parallel does not decide when a machine that has produced no recent figure will never produce another. The diagonal construction requires an effective filter from descriptions to satisfactory numbers, Turing’s term for description numbers of circle-free machines.

Turing now assumes, for contradiction, that a machine D can inspect any standard description and mark it satisfactory or unsatisfactory. Combined with the universal machine, this classifier can locate successive satisfactory description numbers and compute selected diagonal figures. The construction yields a new circle-free machine H. Let K be H’s own description number.

The proof’s dependency chain

The contradiction uses more than a generic appeal to self-reference. First, machine tables must have finite standard descriptions. Second, these descriptions must be effectively enumerable as integers. Third, the hypothesised machine D must classify each candidate correctly and finish. Fourth, the universal simulation machinery must recover figures from every description D marks satisfactory. Finally, the constructed machine must itself have a standard description and therefore appear among the inputs D is required to judge.

Remove any link and the proof no longer reaches its target. If descriptions cannot be enumerated, the diagonal index is unavailable. If D may abstain, the constructed self-case need not receive the fatal verdict. If D is only usually correct, one contradictory case is compatible with its contract. If the constructed procedure is not itself a machine in the class, its description number need not be judged. The theorem prices a total, exact, closed-domain promise.

Turing calls description numbers of circle-free machines satisfactory. Under the assumption that D exists, a machine can inspect successive integers, discard malformed descriptions, use D to retain satisfactory ones and count them. When the count reaches a required position, universal simulation can wait for the needed figure of that retained machine. Circle-freeness guarantees that this wait eventually ends for each selected row.

The new output sequence is built by modifying diagonal figures. In a finite table, the idea is simple: take row n’s nth bit and choose the opposite. In Turing’s construction the bookkeeping is embedded in machines, description numbers and figure positions. The apparent diagonal paradox becomes an impossibility theorem only because the supposed classifier makes the required row selection effective.

The original printed proof contained a flaw in how one auxiliary machine was made to inspect itself. Turing added a correction describing a machine which, when given a standard description, determines whether the described machine ever prints a specified symbol. From such a device one could solve circle-freeness, so the earlier impossibility rules it out. Treating the correction as part of the source is essential. A polished textbook diagonal should not be silently substituted for the paper’s actual route.

When H’s construction reaches K, D must classify H. If D calls K satisfactory, the construction’s self-case prevents the required continuation. If D calls K unsatisfactory, it is wrong because H is circle-free by construction. Turing’s published argument needed correction in detail, and the appended correction repairs the self-application step. The load-bearing point survives: a total classifier over standard descriptions cannot remain consistent when its own described behaviour enters the domain.

Turing then derives a more operational result. There is no general machine which, given an arbitrary machine description, decides whether that machine ever prints a chosen symbol. The reduction arranges for symbol printing to signal the property under investigation. This theorem is closer to the modern family of machine-behaviour undecidability results, though the paper’s vocabulary and proof organisation should still be retained.

Recognisers, deciders and proof certificates

For some machine properties, finite positive evidence is available. If the question is whether a specified symbol ever appears, simulation recognises every yes-instance: when the symbol appears, the trace itself is a certificate. For a no-instance, simulation may continue for ever. A recogniser therefore differs from a decider. The latter must also halt with the right negative verdict on every input.

Static reasoning can settle additional cases. A ranking function may prove that a loop terminates. An invariant may prove that a symbol is unreachable. A finite-state abstraction may establish that all relevant configurations have been exhausted. These successes do not conflict with undecidability because each method covers a restricted family or returns “unknown” outside its proof conditions.

The engineering response is to expose that third status. A sound analyser may answer YES with a trace, NO with a proof certificate, and UNKNOWN when neither is found. Requiring it to replace UNKNOWN by a total exact verdict over arbitrary descriptions recreates the forbidden contract. Turing’s theorem supports explicit abstention more directly than it supports fatalism.

How much does the model earn?

A formal theorem about Turing machines does not by itself show that every intuitive calculation is machine-computable. Turing recognises this gap. Section 9 offers three kinds of support: a direct analysis of a human computor, comparison with another independently motivated definition and demonstrations that broad natural classes of familiar numbers are computable.

The direct analysis is the paper’s distinctive philosophical move. A human calculator can write only finitely many symbols at one moment, distinguish only finitely many relevant states and observe only a bounded number of squares. A complex operation can be divided into simple operations whose local changes are limited. With sufficient expansion of state, the next simple operation is determined by current state and observed symbols.

Why finitely many states are not a claim about vocabulary

A calculator may describe infinitely many mathematical situations in language. Turing’s finiteness claim concerns the immediately action-relevant distinctions of one mechanical routine. If two internal conditions lead to the same action for every possible scanned symbol and the same future control, the routine may merge them. If a distinction changes the next move, a finite instruction must make that distinction operationally available.

The argument also allows compound observation. A person may seem to take in several adjacent symbols at once. Turing notes that the number observed can be bounded, and a machine with a richer finite alphabet or expanded state can encode the compound view. What is excluded is an observation whose span grows without bound while remaining one primitive step. The boundary concerns uniform finite specification, not an insistence that biological vision literally sees one printed square.

Similarly, local rewriting is not tied to one physical pencil stroke. If a calculator can change a bounded cluster of symbols at once, the action can be decomposed into a finite sequence while the intended cluster and phase are retained in state. The simulation may be slower. Computability ignores that constant or finite slowdown because the question is whether a finite method exists, not whether it meets a practical deadline.

These transformations reveal the robustness of the model. Enlarging the alphabet, adding several tapes, scanning a fixed-width window or permitting bounded multi-symbol edits changes convenience and efficiency, but not the class of computable functions. A proposed escape therefore needs more than a richer finite interface. It must introduce an unbounded primitive, an oracle or another resource that cannot be compiled back into finite local control.

The comparison route points to Church’s lambda-definability and general recursiveness. Church’s 1936 paper independently proposed a formal boundary for effective calculability.² Turing’s appendix outlined equivalence, and his 1937 note supplied a fuller result linking machine computability and lambda-definability.³ Agreement between formalisms with different primitives is evidence that neither boundary is a mere notational accident.

Post’s 1936 formulation supplies another neighbouring model: a worker follows finite instructions while marking boxes.⁴ Post called the identification with effective calculability a working hypothesis, signalling appropriate caution. Equivalence results are mathematical. The claim that the shared class captures every ordinary mechanical procedure remains a thesis supported by analysis and convergence.

Enumerable does not mean decidable

Turing can enumerate well-formed machine descriptions because syntax is finite and mechanically checkable. He can also show that computable sequences form a countable class: each has at least one finite description. Neither fact supplies a decider for the semantic property of circle-freeness. Countability answers how many candidates there are in set-theoretic terms. Decidability asks whether one effective procedure classifies every candidate.

The distinction also explains Turing’s statement that not every definable number is computable. A finite mathematical phrase can identify a real number by referring to a noncomputable property. For example, a binary sequence may set its nth digit according to whether n is satisfactory. The phrase defines a unique sequence relative to the formal notion, but a machine producing its digits would decide satisfaction and contradict Section 8. Finite linguistic designation and finite mechanical generation are different achievements.

Nor should countability be turned into a probability argument. Almost every real number is noncomputable under ordinary measure because the computable reals are countable. That fact does not tell us that familiar constants are usually uncomputable, nor that a physically measured quantity presents an infinitely precise noncomputable real to an observer. Turing’s paper instead gives constructive coverage: algebraic numbers and many values defined by effective analytic processes fall within the computable class when suitable convergence information is available.

The practical question is therefore not whether an object has a short name, but whether its requested approximations can be generated with effective control of error. A specification such as “the least counterexample if one exists” may be linguistically compact while hiding an undecidable search. A numerical routine must say how each demanded digit or tolerance is eventually reached.

Gandy later asked a different question: which functions can discrete deterministic physical mechanisms compute? He proposed principles concerning bounded local information and causal propagation.⁵ That extension is important because Turing’s Section 9 starts from a human computor following a rule. Moving from an analysed clerk to every physically possible mechanism requires extra premises about matter, space, time and measurement.

The application to the Entscheidungsproblem comes last. Turing encodes claims about a machine’s configurations in the Hilbert functional calculus. If a general decision procedure for the calculus existed, it could decide a machine property already proved undecidable. The reduction therefore carries the negative result from machine behaviour to the proposed universal logical decision method.

This is stronger than observing that proof search sometimes takes a long time. A slow method might still decide every instance. Turing shows that no automatic method with the stated universal contract can exist. The lesson is about quantifiers and reductions, not pessimism about difficult calculations.

The reduction habit

A reduction does not argue that two problems look alike. It gives a mechanical transformation from any instance of one problem to an instance of another, preserving the answer in a known way. If a decider existed for the target problem, composing the transformation with that decider would solve the source problem. When the source is known undecidable, the target decider cannot exist.

Turing’s application encodes statements about machine configurations into formulas of the functional calculus. The formula is arranged so that provability tracks whether a designated machine event occurs. A decision procedure for the calculus would therefore answer the machine question. The contradiction travels through an explicit representation bridge rather than through the general observation that logic and machines are both symbolic.

This habit is valuable well beyond foundational logic. When a platform claims universal verification, ask whether an unrestricted programme-behaviour problem can be embedded in its input language. When a policy language claims guaranteed conflict detection, ask whether it permits recursive conditions rich enough to encode arbitrary computation. The relevant warning comes from the demonstrated transformation, not from attaching the word “undecidable” to every complicated system.

Reductions also prevent overextension in the other direction. If a workflow language is finite-state, acyclic or resource-bounded, an encoding of arbitrary machine behaviour may be impossible. Invoking Turing without checking expressiveness would then be theatre. The boundary must be earned by showing that the target accepts enough structure to carry the known hard problem and that the proposed verifier promises the corresponding exact verdict.

A tape machine you can interrupt

The studio below executes small deterministic machines one local transition at a time. The preset machines expose three different global outcomes: indefinite figure production, immediate stopping and endless motion after finite figure output. A finite step limit is an observation budget, not a proof that a machine is circular.

Recover the argument without rereading it

Use the cue LOOK: Local observation and action, Output distinguishes circle-free from circular, Own descriptions become input, Kink the total classifier at its self-case. The two O’s matter: one concerns the output contract; the other concerns description-level self-application.

What to carry forward

Turing’s machine remains useful because it is sparse enough to audit. Every operation is local; every retained distinction has a place in state or on tape; every program has a finite description. This makes universality constructive and the contradiction inspectable. Nothing important is hidden inside a word such as “reason”, “recognise” or “eventually”.

The paper also teaches restraint. Computable descriptions can be listed, but useful semantic subsets need not be decidable. Universal interpretation does not grant universal self-inspection. A timeout is not a theorem. A proof about automatic machines does not settle physical possibility or conscious capacity without another bridge.

The durable method is therefore diagnostic. Reduce an advertised procedure to its observations, state and transitions. Ask which part is finite, which record may grow, and where choice enters. Make descriptions available as inputs. Then inspect the universal quantifier. Turing’s result does not tell us that machines are weak. It tells us exactly how a strong machine claim can become too strong to satisfy.

References

1. Turing, A. M. (1936). “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society, s2-42(1), 230–265. doi:10.1112/plms/s2-42.1.230.
2. Church, A. (1936). “An Unsolvable Problem of Elementary Number Theory.” American Journal of Mathematics, 58(2), 345–363. doi:10.2307/2371045.
3. Turing, A. M. (1937). “Computability and λ-definability.” The Journal of Symbolic Logic, 2(4), 153–163. doi:10.2307/2268280.
4. Post, E. L. (1936). “Finite Combinatory Processes, Formulation 1.” The Journal of Symbolic Logic, 1(3), 103–105. doi:10.2307/2269031.
5. Gandy, R. (1980). “Church’s Thesis and Principles for Mechanisms.” In J. Barwise, H. J. Keisler and K. Kunen (eds.), The Kleene Symposium, 123–148. doi:10.1016/S0049-237X(08)71257-6.
6. Copeland, B. J. and Shagrir, O. (2007). “Physical Computation: How General are Gandy’s Principles for Mechanisms?” Minds and Machines, 17, 217–231. doi:10.1007/s11023-007-9058-2.