Motivation
Cantor's argument constructs an object absent from a proposed list. Computability adds a new demand: can a list or construction be carried out by a finite, effective procedure? There are only countably many finite programs, but that cardinality observation alone does not prove that a particular decision problem is impossible. For halting, a sharper diagonal argument makes a supposed decision procedure contradict its own prediction.
The conclusion concerns algorithms required to work on every legal input. It does not say that every particular program's behavior is unknowable. We can prove that a displayed loop never halts and that a displayed finite computation does halt. What fails is one terminating method that always answers correctly for all programs and inputs.
Definitions
Definition 5.1.1
(Turing machines and computable functions)
Fix a deterministic Turing-machine model with a finite state set, a finite tape alphabet containing a blank symbol, a tape indexed by the integers, one head, and a finite transition table. A nonterminal step reads the scanned symbol, writes a symbol, moves the head one cell left or right, and changes state. Input is a finite binary word on an otherwise blank tape. A designated terminal state halts the computation. A fixed effective convention encodes natural-number inputs and outputs by finite words.
A machine computes a partial function : when it halts with a valid output, that output is the value; a nonhalting computation has no value. We can arrange the output convention so that any halting computation returns a natural number. A function is total computable if one such machine halts with its value on every input. “Partial” concerns undefined inputs; it does not allow an algorithm to choose an arbitrary value at a nonhalting input.
Finite descriptions can be effectively listed as ; assign malformed descriptions a fixed never-halting machine. Let be the partial function computed by . There is a universal simulator: given , it decodes the finite table and simulates successive configurations of . A configuration has a state, a head position and finitely many nonblank cells, so each finite step is an effective operation on finite strings. This supplies a machine computing the partial function . Universality does not promise that the simulation terminates.
Definition 5.1.2
(Decidable and semidecidable sets, many-one reductions)
A set is decidable if its characteristic function is total computable. It is semidecidable (computably enumerable) if some program halts exactly on its members. A recognizer that sometimes halts and rejects can be changed to loop on rejection, giving this convention. A many-one reduction is a total computable function with exactly when .
Theorem/proposition
Theorem 5.1.3
(The diagonal halting set)
The diagonal halting set
is semidecidable and not decidable.
Theorem 5.1.4
(Complementary semidecision)
A set is decidable exactly when both it and its complement are semidecidable. In particular is not semidecidable.
Theorem 5.1.5
(Transfer by reduction)
If and is decidable, then is decidable. If is semidecidable, then is semidecidable. Thus reducing a known undecidable to proves that is undecidable.
Theorem 5.1.6
(Rice's theorem for partial functions)
Let be a nontrivial property of partial computable functions: some such function has the property and another does not. The index set is undecidable. The property must depend on the computed partial function, not on the spelling or running time of a particular program.
Proof sketch or proof idea
Proof
(A diagonal program defeats any halting decider)
To semidecide , simulate and halt when it halts. Suppose a total program decided , outputting for membership and otherwise. Build a program that on input computes , loops forever if the answer is , and halts if the answer is . Let be its description index. If , then does not halt, contradicting . If , then halts, contradicting . Both alternatives fail. A finite program can contain a call to under the supposition that exists, so legitimately occurs in the program list.
Proof X-ray
The exact dependency in the diagonal contradiction
The contradiction assumes that is both correct and total. Totality ensures that reaches its branch on every input, so the answer predicted by really determines whether halts. Correctness then fails in either branch when the input is 's own code. If were merely a halting recognizer, its possible divergence would prevent this branching argument and there would be no contradiction with universal simulation.
The proof also uses effective self-application: an index is a natural number, so a program description can be supplied as ordinary numerical input. It does not require a program to inspect a mystical self-reference or decide its own index while running. Once the finite description of exists under the hypothesis, it has an index , and the mathematical proof considers the input . Keeping this outside reasoning distinct from the program's actual instructions makes the diagonal step precise. It removes worries about spurious self-reference, and it also explains why the same construction rules out a universal evaluator that is total on every listed program.
Proof
(Dovetailing two semideciders)
A decider supplies semideciders for either answer by looping on the unwanted answer. Conversely, run one step of the semidecider for and one step of that for its complement, alternating forever until one halts. Exactly one must eventually halt; return its corresponding answer. This dovetailing does not run the first program to completion before starting the second. Applied to , it shows that its complement cannot be semidecidable, or would be decidable.
Proof
(Compose with the total reduction)
Compute , which always finishes, and then run the decision or semidecision procedure for on that output. The membership equivalence proves correctness. The totality of is essential: an undefined preprocessing step would not give a decider even if were trivial.
Proof
(A wrapper that runs only after halts)
For Rice's theorem, let be the nowhere-defined partial function. First suppose , and choose one fixed computable partial function . From an input index , effectively write a program that, on input , first simulates and, only if this halts, runs a fixed program for . Inserting the numeral for into this fixed wrapper is an effective syntactic operation; the map is total computable. If , then computes ; if , it computes . A decision of its semantic property would decide , impossible. If , apply the argument to the complementary property, which is nontrivial and excludes . A decider for a set would also decide its complement, finishing the proof.
Counterexample mode
Rice needs a property of the computed function
Claim: every nontrivial property of program indices has an undecidable index set. Take
It is nontrivial. A machine with only a start state and the terminal state, which in the start state rewrites the scanned symbol and moves right forever, belongs to and computes . Adding eleven unreachable states gives a machine that still computes but lies outside , so is not determined by . Yet is decidable: given , decode the description (a malformed one denotes the fixed never-halting machine, whose state count is known) and count states; this finite parsing always terminates.
Rice's proof breaks because its reduction needs membership of to depend only on whether computes or . For it depends on the size of the wrapper, which has nothing to do with whether halts. The repaired hypothesis is extensionality: must imply , which says exactly that for a property of partial functions.
Worked examples
Worked example 5.1.7
(Bounded halting is decidable)
Given , simulate at most steps and inspect whether a terminal state has been reached, counting the initial configuration consistently as time zero. This is a finite decision procedure. Unbounded halting asks whether some time works, without a supplied bound. A semidecider can search successive times, but when no time works the search never certifies failure.
Concept lensStructural
Semidecidable sets as projections of decidable relations
Bounded halting gives a second description of semidecidability. A set is semidecidable exactly when for some decidable relation . If a program halts exactly on , take to mean that halts on within steps. Conversely, given , test in turn and halt at the first success. One unbounded existential quantifier in front of a decidable relation is exactly the search a semidecider performs.
Worked example 5.1.8
(Reducing to a fixed input)
Let . Given , write a program that ignores its input and simulates . Its code is effectively computable and satisfies exactly when . Hence is undecidable. The proof does not need to solve the simulated computation while constructing the wrapper.
Worked example 5.1.9
(Semantic and syntactic questions)
“Does this description contain at most ten states?” is decidable by parsing the finite description. “Does this program compute the constant-zero total function?” is a nontrivial property of its partial function, and is undecidable by Rice. “Does this program halt on every input?” is also such a property. Rice alone does not classify whether an undecidable property is semidecidable; it proves only the absence of a decider.
Worked example 5.1.10
(Why cardinality is weaker than halting diagonalization)
Subsets of are uncountable, while programs are countable, so some subsets are not decidable. This does not identify . The self-input diagonal proof does. It also explains why there cannot be an effective enumeration of all total computable functions with a total computable evaluator : then would be a total computable function different from every listed one. All partial computable functions do admit a universal partial evaluator; its possible divergence is exactly what blocks that contradiction.
Worked example 5.1.11
(Recognition and enumeration are equivalent)
The phrase “computably enumerable” has an operational interpretation. If a program halts exactly on , then at stage simulate inputs for steps and print any input seen to halt. Repetitions are allowed. Every printed number lies in , and if halts after steps, every stage at least detects it. Thus all and only members are eventually printed. The empty set is handled by a process that prints nothing.
Conversely, suppose a computable ongoing process prints exactly the members of , perhaps with repetitions and pauses. On input , simulate the process until it prints , and then halt. This semidecides membership. It need not know whether a silent process has finished or will print another item later. For an infinite computably enumerable set, a strictly increasing enumeration would be stronger: searching until the output reaches or passes would decide membership, because an increasing infinite sequence is unbounded in . Therefore an undecidable computably enumerable set such as cannot have an effective increasing enumeration. The order in which a list arrives carries computational information, even when repetition does not change the underlying set.
Parameters and self-reference
Several arguments above started from an index and wrote down the code of a new program with built into it. That step is used so often that it deserves a precise statement, and once isolated it yields a fixed-point theorem about programs.
Write when both sides are undefined, or both are defined and equal. A partial function of two arguments receives the single input under a fixed computable bijection .
Theorem 5.1.12
(Parameter theorem (s-m-n))
For every partial computable function there is a total computable function such that for all .
Proof
(Hard-wire the parameter)
Fix a machine computing on paired inputs. For a given , let be the machine that, on input , first writes the binary word of to the left of its input, then computes from the two words, and then runs on the result. Only the first stage depends on . It is a chain of one new state for each bit of , each writing its bit and moving left, followed by a fixed return to the start of the word. The other stages use fixed transition tables. Producing the table of from is therefore a uniform, terminating manipulation of finite strings, and , the index of , is total computable. By construction halts exactly when halts, and with the same output.
The wrapper in the proof of Rice's theorem, the reduction of to , and the reduction of every semidecidable set to are all instances: in each case one writes a single two-argument program and lets fix the first argument.
Theorem 5.1.13
(Kleene's recursion theorem)
For every total computable function there is an index with as partial functions.
Proof
(A diagonal that is evaluated instead of negated)
Let : run , and if it halts with value , run program on input . This is partial computable, so the parameter theorem gives a total computable with when is defined, while is nowhere defined when is undefined. The composite is total computable, so for some index . Since is total, is defined, and therefore
Thus is the required index.
Proof X-ray
Where the halting proof negated, this proof evaluates
Both proofs feed an index to itself. The halting argument builds a program that does the opposite of what a supposed decider predicts, and the contradiction shows that the decider cannot exist. Here nothing is negated: simply behaves like whatever program names. Applying before the self-application, and then choosing , makes the programs and compute the same partial function. Totality of is used exactly once, to guarantee that is defined. The theorem does not claim ; two different indices are allowed to compute the same function, and in general they do.
Worked example 5.1.14
(A program that outputs its own index)
Let be an index of the program that ignores its input and outputs . The parameter theorem, applied to , shows that is total computable. The recursion theorem gives with , which is the constant function with value . So program outputs its own index on every input. Self-reference of this kind is a theorem about a fixed effective numbering, not an extra feature of the machine model; this is also why letting a constructed program "use its own code" is legitimate in proofs.
Theorem 5.1.15
(Totality is neither semidecidable nor co-semidecidable)
Let . Neither nor is semidecidable.
Proof
(Two reductions from the halting set)
First, the parameter theorem gives a total computable such that, on input , program simulates and outputs if the simulation halts. Then is total when and nowhere defined when . So reduces to . If were semidecidable, so would be , which is false.
Second, let be total computable such that, on input , program simulates for steps, loops forever if the simulation has halted within those steps, and outputs otherwise. If , every input yields , so . If and halts after steps, then program diverges on every . So reduces to , and is not semidecidable either.
Rice's theorem gives only that is undecidable. The two reductions say more: does not even reduce to , since every set many-one reducible to the semidecidable set is semidecidable.
Common mistakes
Common mistake
(Silence is not rejection)
A semidecider's silence is not a negative answer. A finite timeout only proves “not halted yet”.
Common mistake
(Reduce from the known hard problem)
In a reduction, send instances of the known hard problem to instances of the new problem. Reversing that arrow does not establish hardness.
Common mistake
(The halting theorem concerns a model, not computing speed)
The Church–Turing thesis connects the informal idea of effective calculation to formal models; it is not proved just by defining one model. The halting theorem is a precise theorem about that model. Nor does undecidability mean that extra computation speed alone helps: the contradiction applies to every decider expressible in the same effective framework. We make no claim here about physically realizable hypercomputation.
Allowing machines to query a fixed set relativizes every argument here and produces a strictly harder halting problem.
A path to generalization
Machines that may consult a fixed set
Allowing machines to query a fixed set relativizes every argument here and produces a strictly harder halting problem.
Allow a machine, in one step, to ask whether a number belongs to a fixed set , an oracle. Programs remain finite descriptions, the universal simulator still exists, and the diagonal proof goes through unchanged: the halting set for machines with oracle is semidecidable relative to but not decidable relative to . Taking gives a halting problem that even a machine able to consult cannot decide.
Summary
Finite machine descriptions make universal simulation possible. Self-input diagonalization shows that halting has no total decider. Dovetailing separates decision from semidecision, and effective reductions transfer the obstruction. Rice's theorem extends it to every nontrivial property of the computed partial function. The parameter theorem formalizes hard-wiring an index into a program, Kleene's recursion theorem turns it into a fixed point for every effective program transformation, and totality is neither semidecidable nor co-semidecidable.
Exercises
Quick check
(Prove that the union and intersection of two semidecidable sets are semidecidable. Explain why complementation behaves differently.)
Solution · Answer
For a union, alternate one step of each semidecider and halt when either halts. For an intersection, dovetail both and halt once both have halted, storing whether each has done so. Nonmembers cause the appropriate condition never to occur. Complementation fails in general because is semidecidable but its complement is not.
Quick check
(Prove the two-input halting set is semidecidable and undecidable, using a fixed computable pairing of natural numbers.)
Solution · Answer
The universal simulator semidecides . The total computable map reduces to , so a decider for would decide . Pair encoding changes only the input format and is computably reversible.
Quick check
(Show that the property “the partial function's domain is empty” is undecidable, and decide whether its complement is semidecidable.)
Solution · Answer
Emptiness is a nontrivial semantic property, so Rice applies. Its complement, nonempty domain, is semidecidable: at stage , simulate inputs for steps, and halt if any simulation halts. If some input eventually halts, a sufficiently large stage detects it. Emptiness itself cannot be semidecidable, by complementary semidecision and undecidability.
Quick check
(A student proposes to decide halting by running a program until it halts or repeats a configuration. Explain why the test works for a deterministic machine with finitely many possible configurations, but not for arbitrary Turing machines.)
Solution · Answer
Determinism makes a repeated configuration enter a permanent cycle. With a finite configuration set, every nonhalting run eventually repeats by the pigeonhole principle, giving a finite exhaustive test. An unbounded tape allows infinitely many configurations. A program can move right forever, writing a mark in each fresh cell, and never repeat a configuration; the proposed procedure then also runs forever. Finiteness of states alone is not finiteness of configurations.
Quick check
(Derive Rice's theorem from the recursion theorem: if were decidable for a nontrivial property , construct a total computable that contradicts the recursion theorem.)
Solution · Answer
Choose and , and let for and for . A decider for makes total computable, so some satisfies . Membership in depends only on the computed function. If , then and , so ; if , then and , so . Both cases are contradictory.
Quick check
(Show that there is an index with for every .)
Solution · Answer
Apply the parameter theorem to to obtain a total computable with . The recursion theorem gives with , so for every . Take .
Quick check
(Let . Show that neither nor its complement is semidecidable, reusing the two reductions in the proof for .)
Solution · Answer
The map sends to a program with empty, hence finite, domain and to a total program, whose domain is infinite. So reduces to , and is not semidecidable. The map sends to a total program and , with halting time , to a program with domain . So reduces to , and the complement is not semidecidable either.