Motivation
Finite automata, pushdown automata and bounded-tape machines each impose a limit on memory, and each limit excludes some languages. A Turing machine removes the limit: it has an unbounded tape on which it can read and write. The question changes accordingly. Instead of asking which languages fit a memory bound, we ask which languages can be decided by any mechanical procedure at all, and we find that there are definite, provable limits that do not come from a lack of resources.
We state the machine model precisely, prove the central theorems about recognition and decision, and place the language classes of the earlier chapters in one chain. A fully explicit transition table is given only for a small example machine; the universal machine is described at the level of its algorithm, with the routine subroutines assumed implementable. We make no claims beyond classical computability.
Definitions
Definition 5.1.1
(Turing machine and configurations)
A deterministic Turing machine is with finite state set , input alphabet , tape alphabet where the blank , and a transition function . The tape is unbounded to the right and starts as the input word followed by blanks; the head starts on the first cell. A move left from the first cell leaves the head there. A configuration is a string with and , meaning that the tape holds followed by blanks, the state is , and the head scans the first symbol of (a blank if is empty). The relation means results from one move.
The machine accepts if starting from it reaches a configuration in , rejects if it reaches one in , and otherwise loops, that is, runs forever. Write for the set of accepted words.
Definition 5.1.2
(Recognizer, decider, decidable, recognizable)
A language is Turing-recognizable if for some machine ; then need only accept the words of , and may loop on others. A language is decidable if for some machine that halts (accepts or rejects) on every input; such an is a decider.
Definition 5.1.3
(Encodings and mapping reductions)
Fix a computable injective way to write a machine and word as strings and over , such that it is decidable whether a string is a valid encoding. A mapping reduction from to , written , is a total computable function with for all . Define , , (self-acceptance), and .
Theorems
Theorem 5.1.4
(Universal simulation)
There is a Turing machine such that, on input , it accepts iff accepts , rejects iff rejects , and loops iff loops on . Hence and are Turing-recognizable.
Theorem 5.1.5
(Decidable means recognizable with recognizable complement)
A language is decidable if and only if both and are Turing-recognizable.
Theorem 5.1.6
(Self-acceptance and halting are undecidable)
is not decidable. Consequently , and are not decidable, and the complement of is not Turing-recognizable.
Theorem 5.1.7
(Direction of a reduction)
Let by . If is decidable then is decidable; if is recognizable then is recognizable. Equivalently, if is undecidable then is undecidable. The relation is transitive.
Theorem 5.1.8
(Rice's theorem)
Let be a set of Turing-recognizable languages over such that some recognizable language lies in and some recognizable language does not. Then is undecidable.
Theorem 5.1.9
(A chain of language classes)
Over a fixed alphabet with at least three symbols, , where CSL is the class generated by noncontracting grammars, DEC is the decidable languages and REC the Turing-recognizable languages. Every inclusion is strict. The inclusion is proved here using the Chomsky normal form theorem proved in the companion normal-form chapter.
Proof sketch or proof idea
Proof
(A universal machine by step-by-step simulation)
The machine keeps on its tape an encoding of the current configuration of next to the encoded transition table . A simulated step finds the state and scanned symbol in the configuration, looks up the matching entry of in , and rewrites the configuration. These subroutines (searching, comparing strings, copying, shifting) are routine, and we do not give their states. By induction on , after simulated steps the configuration on the tape encodes of on . If is in state then accepts; if in then it rejects; if never halts then runs forever. For , first copy to form and then run .
Proof
(Dovetailing decides a language whose complement is recognizable)
If is decidable, a decider for is a recognizer, and exchanging its accept and reject states gives a decider, hence a recognizer, for the complement. Conversely let recognize and recognize its complement. On input run and in alternation, one step of , then one step of , and so on, on separate tape tracks. This interleaving is called dovetailing. Exactly one of and is true, so exactly one of the machines accepts , and it does so after finitely many steps; the other never accepts. If accepts, accept; if accepts, reject. This halts on every input and decides . Running the two machines one after the other, instead, would fail, because the first may loop.
Proof
(Diagonalization against a decider for self-acceptance)
Suppose a decider decides . Build : on input , if is not a valid encoding of a machine then reject; otherwise run on and accept iff rejects. halts on every input. Let . Then accepts iff rejects iff iff does not accept , a contradiction. So no decider exists. The same argument is a diagonal one: the language of differs, at the input , from the language of each machine whenever is correct.
Proof X-ray
What the diagonal argument really uses
Three ingredients are needed, and each can be located in the text. First, an effective encoding: every machine is a string, so can be given its own description as input. Second, the hypothetical decider must be a machine, so that built from it is a machine whose behavior on is defined. Third, flips the answer of and halts on every input. The contradiction arises only at the single input . The argument does not say that no machine can recognize , which the universal machine does.
Proof
(Undecidability spreads along reductions)
Every reduction below also maps malformed source encodings to a fixed nonmember of its target, making the preprocessing total on all strings. Reduce by , and send strings that are not valid encodings to a fixed string outside . So is undecidable by the theorem on the direction of reductions. Next : map to , where on input simulates on , accepts if accepts, and enters an infinite loop if rejects. Then halts on iff accepts . Finally : map to , where ignores its input, writes on the tape and runs ; halts on the empty input iff halts on . The complement of cannot be recognizable, because is recognizable by the universal machine, and if both were recognizable the complement theorem would make decidable.
Proof
(Reductions transfer decidability backwards)
Let reduce to . If has a decider , then on input compute and run on it: this decides , since and is total. The recognizer case is the same, using a recognizer for . The contrapositive gives the undecidability statement. For transitivity, if reduces to and reduces to , then is total, computable and reduces to .
Proof
(Halting reduces to every nontrivial property)
On a malformed source encoding, output a fixed machine whose language is outside the property under consideration. First show is undecidable (done above). Suppose first . Choose a machine with . Define , where on input first simulates on ; if accepts , then runs on and accepts iff accepts; if does not accept (it rejects or loops), never accepts. Then if accepts , and otherwise. So reduces to the language , which is therefore undecidable. If , apply the argument to the class of recognizable languages not in , which is nontrivial and does not contain ; the set of valid encodings is decidable and is the complement of within it, so is undecidable too.
Proof X-ray
Why the source can be acceptance
The wrapper is built from the machine that nontriviality supplies, together with and . Its two outcomes, and , split exactly according to whether accepts . A rejecting and a looping both leave accepting nothing, which is harmless because treats them alike. The assumption is what makes the two outcomes answer differently; the complement step only restores it. The map is computable because is written down, never run.
Proof
(The chain of inclusions and why each is strict)
: a DFA gives a grammar with a variable per state, rules and for accepting . : under the normal form hypothesis the normal-form grammar for has rules and , which are noncontracting; if , add a fresh start with . is the decidability of membership from the context-sensitive chapter. is immediate. is trivial.
For strictness: is context-free but not regular. is context-sensitive but not context-free. For , use the same fixed alphabet , with three distinct symbols for the earlier witnesses. Noncontracting grammars over , with variable names from a fixed countable list, are finite objects, so they can be enumerated computably as ; every context-sensitive language over is some up to renaming variables. Enumerate as and let . is decidable: given , find with , construct and decide membership by the length lemma, handling the empty word by checking its permitted empty start rule. But for every , since lies in exactly one of them. For the witness is . For , machines are finite strings and hence countably many, while subsets of are uncountably many by Cantor's argument.
Counterexample mode
Reducing in the wrong direction proves nothing
Claim (false): to prove that is undecidable, it suffices to reduce to some decidable language, or to reduce some decidable language to . Take the decidable language . The constant function sending every input to a fixed non-halting pair is a mapping reduction of to , yet this tells us nothing about whether is decidable. Likewise reducing to a decidable language would show that is decidable, which is false. Repair: to show a target undecidable, reduce a known undecidable language to , and the computable map must satisfy in both directions.
Concept lensAlgorithmic
Dovetailing as scheduling of searches
A recognizer is a search that succeeds in finitely many steps when the answer is yes and may never finish when the answer is no. A decider combines two such searches, one for membership and one for non-membership, and runs them in alternation so that whichever succeeds is noticed. Interleaving is not an optimization; it is the only way to avoid being stuck in the search that will never end.
Worked examples
Worked example 5.1.10
(A decider for with n at least 1)
All unlisted state-symbol pairs go to the reject state, preserving the scanned symbol; any mentioned move without a write preserves the symbol. This makes the transition function total.
Let the machine have tape symbols and transitions: in reading , write , move right, go to ; in reading , go to moving right; in reading anything else, reject. In , skip and to the right; reading , write , move left, go to ; reading reject. In , skip and to the left; reading , move right and go to . In skip to the right, accept on , reject on or . On input : accept. Each pass of pairs one with one ; the machine reaches exactly when all 's are used, and then it accepts only if no remains.
Worked example 5.1.11
(The diagonal pattern on a toy table)
Suppose four machines and four inputs give the acceptance table (1 means accept, 0 means not accept) with rows , , , . The diagonal is ; flipping it gives . The flipped row differs from row in column for each , so it appears nowhere in the table. The real proof applies this to the infinite table of all machines against all machine encodings, where the flipped diagonal is the language of , and where the hypothetical decider is what makes the flipped diagonal computable.
Worked example 5.1.12
(Using Rice's theorem, and when it does not apply)
Let . The language is recognizable and in , and is recognizable and not in , so is undecidable. In contrast, " has at most five states" concerns the description of , not the language : two machines with the same language may differ in size. Rice's theorem does not apply, and in fact the question is decidable by reading . Similarly, " accepts within ten steps" is decidable by simulation for ten steps.
Common mistakes
Common mistake
(Waiting on a recognizer does not reveal non-membership)
Do not confuse a recognizer with a decider. A recognizer may fail to halt on words outside the language, so running it and waiting does not reveal non-membership.
Common mistake
(Undecidable does not mean unanalyzable)
Do not say that the halting problem shows some particular machine “cannot be analyzed”: for a fixed machine and fixed input, the question has a definite yes or no answer, and a trivial machine outputting that answer exists. Undecidability concerns one uniform procedure for all instances.
Common mistake
(Rice's theorem is about languages, not descriptions)
Do not apply Rice's theorem to properties of the machine's description or running time.
Summary
Turing machines have configurations, and a universal machine simulates any machine from its description. A language is decidable exactly when it and its complement are recognizable, shown by dovetailing. The diagonal argument shows self-acceptance undecidable, and reductions transfer this to acceptance, halting and halting on empty input. Rice's theorem makes every nontrivial property of the recognized language undecidable. The classes regular, context-free, context-sensitive, decidable and recognizable form a strict chain, with the first three links resting on the earlier chapters.
Exercises
Exercise 5.1.13
(Prove that the decidable languages are closed under complement and intersection, and that the recognizable languages are closed under union and intersection.)
CoreProof
Solution(3)
- 1
Deciders: complement and intersection
If decides , exchanging accept and reject decides the complement. For two deciders, run both and accept iff both accept; both halt.
- 2
Recognizers: intersection
For recognizers , run and then and accept iff both accept. If , both stages end in acceptance. If is outside either language, the corresponding stage never accepts, so is correctly never accepted.
Because: A recognizer never accepts a word outside its language, whether or not it halts.
- 3
Recognizers: union by dovetailing
∎Dovetail the two machines and accept as soon as either accepts. Running them one after another would be wrong, because the first may loop on a word accepted by the second.
Exercise 5.1.14
(Prove that and imply , and that implies .)
CoreProof
Solution(3)
- 1
Compose the two maps
Let and be total computable with and . Then .
- 2
Check that the composite is a reduction
The function is total and computable, so .
Because: Composing total computable functions gives a total computable function.
- 3
Use the same map for complements
∎Negating the equivalence gives , so the same reduces to .
Quick check
(Show that is undecidable.)
Which property of languages does this describe, and is it nontrivial?
Solution · Answer
Let be the set of recognizable languages that are infinite. is recognizable and infinite, so it belongs to , and is recognizable but not infinite. So is nontrivial and Rice's theorem applies.
Quick check
(Trace the machine of the first worked example on the input and state the result.)
Each pass pairs one with one .
Solution · Answer
. In reading the machine rejects. The word has more 's than 's, so rejection is correct.