Turing’s Tape and the Decision Procedure That Cannot Exist

Finite rules, with room to keep working

Turing’s machine has a finite control, a tape divided into squares, and a head that inspects one square at a time. An instruction consults the current state and scanned symbol, then specifies a local action and the next state. The tape supplies expandable workspace. It does not imply that infinitely many symbols have already been read, or that an infinite calculation finishes in one step. After finitely many moves, only finitely much work has happened.

For a small example, consider generating the binary expansion of one seventh. Long division keeps a remainder: doubling 1 gives a first digit 0 and remainder 2; doubling 2 gives another 0 and remainder 4; doubling 4 gives digit 1 and remainder 1 after subtracting 7. The process repeats, producing 0.001001001…. Only three repeating remainder states are needed. This describes a finite procedure for every requested digit; it makes no claim that all infinite sequences admit such a procedure.

A program can also be data

A machine’s finite instruction table can be encoded as a string or number. Another machine can inspect that description and simulate its individual moves. Turing’s universal machine exploits this possibility: its fixed rules interpret descriptions of many different machines. Changing the encoded input can therefore change the calculation without rebuilding the simulator’s own rules.

There is a crucial limit to what simulation provides. If a simulated program prints a digit, the simulator can eventually reproduce that event. If the program runs silently forever, watching longer never supplies a certificate that nothing will happen tomorrow. Universal execution and universal prediction are different tasks. Encoding instructions does not add a command that can skip an arbitrarily long or nonterminating computation while always preserving the right answer.

Imagine a simulator that has watched a billion silent steps. One candidate program may print at the next step; another may never print. The length of the observation alone separates neither case. Sometimes inspecting the instructions gives an answer, and special classes of programs admit systematic analysis. Those successes do not turn elapsed waiting time into a general proof of future silence.

What “circle-free” meant in the original paper

Turing first studied machines producing infinite sequences of designated output figures. A circle-free machine produces infinitely many such figures. A circular machine produces only finitely many. This terminology does not match the modern division between programs that halt and programs that run forever. A machine might keep moving and writing scratch symbols indefinitely while never producing another output figure; it is circular in Turing’s sense even though it never stops.

The distinction also prevents a tempting misuse of diagonal reasoning. Finite machine descriptions can be listed. It does not follow that we can effectively select exactly those descriptions that produce infinite sequences, then wait successfully for every required digit. Some candidates will stall forever. A diagonal construction that assumes those waits always finish has hidden a decision procedure inside its setup. Turing’s argument exposes why that purported selection procedure cannot exist. Countability alone does not provide an effective list containing only productive programs.

Turning a supposed decider against itself

A modern halting argument makes the obstruction easy to see, though it is not Turing’s literal circle-free formulation. Suppose a program H always finishes and correctly answers whether any supplied program P will halt on input x. Build D so that, on input P, it asks H about P running on its own description. If H predicts halting, D deliberately loops forever. If H predicts endless running, D immediately halts.

Now give D its own description. A prediction that D halts makes D loop; the opposite prediction makes D halt. Either answer defeats H’s specification. The contradiction uses an alleged total, universally correct decision method. It does not say that every termination question is difficult, or that testing is useless. A program containing a visibly bounded loop can be analyzed directly. What fails is a single algorithm guaranteed to settle the question for every program and input.

Why the Entscheidungsproblem was a stronger promise

The Entscheidungsproblem asks for a uniform decision procedure for first-order logic: given a formula, determine in finite time whether it is logically valid. Turing connected machine behavior to formulas so that a successful logical decider would answer a machine question already shown undecidable. Such a connection is a reduction. It transfers an impossibility result by showing how a solution to the second task would solve the first.

Searching through formal derivations provides a useful contrast. For a valid first-order sentence, a suitable exhaustive proof search eventually finds a derivation. For an invalid sentence, that same search can continue forever. A decision procedure must finish in both cases. The gap between eventual success on positive cases and a guaranteed answer on every case is exactly where the impossible promise enters. This concerns the full input class of first-order logic; restricted logical fragments can have terminating decision procedures.

The correction is part of the result’s history

The original reduction contained formal errors, identified with help from Paul Bernays. Turing’s three-page correction repairs the encoding of machine behavior in formulas. It also addresses how computable real numbers are represented: an effective rule producing shrinking rational intervals need not uniformly yield the prescribed binary digit representation under a fixed convention for terminating expansions. Representation choices matter when a procedure must produce a specific answer from supplied data.

The correction gives a different association between sequences and real numbers while preserving the class of computable reals. Its offprint in the King’s College archive bears a 1937 volume label, while the publisher’s Crossref deposit indexes the journal article as 1938. These are distinct bibliographic records, so a precise publication day should not be inferred from either year alone. The mathematical point survives that bookkeeping: the corrected reduction supports undecidability, while the representation discussion distinguishes existence of a computing machine from a uniform method for obtaining its description.

Different formalisms reach the same boundary

In his December 1937 paper on computability and lambda-definability, Turing connected his machines with other precise accounts of effective calculation, including lambda-definable and general recursive functions. Equivalence between formal models is a mathematical result: descriptions can be translated so that the same functions are computed. Identifying this common class with every intuitively effective method is the additional claim usually called the Church–Turing thesis.

Neither claim supplies a performance guarantee. A computable procedure might need unreasonable time or memory, and a universal simulator might introduce substantial overhead. Undecidability goes further than poor efficiency: it excludes the requested universally correct terminating algorithm altogether. The tape model remains useful because it lets these differences be stated exactly. It gives computation a precise mathematical scope while leaving room for specialized methods, stronger assumptions, and answers to many individual questions.

This distinction also changes what counts as progress on a decision problem. Faster hardware can shorten a computation that eventually finishes. It cannot satisfy a specification that demands an impossible answer on every input. A restricted input class, a promise about the program, or permission to return an inconclusive result can instead create a different, achievable task.