Turing machines and undecidability

Turing machine model

Definition. A deterministic Turing machine has a finite control, a read/write head, and an unbounded tape divided into cells over a finite tape alphabet containing a blank. A transition reads the current symbol, writes a symbol, changes state, and moves left or right (sometimes staying put by convention). The input is initially written on the tape.

Example. A machine can scan right over a unary input, replace the final 1 with a blank, then halt to decrement a positive unary number.

Exam point. A TM can revisit and overwrite input; unlike a DFA, it has unbounded work memory.

Solved examples

Example 1 — configuration trace. A machine starts at the leftmost 1 in 111, scans right over 1s, and enters qf on blank. Show configurations.

1. Write a configuration as tape contents with the state immediately before the scanned symbol.
2. Initial: q0 111□.
3. After scanning each 1 and moving right: 1q0 11□, then 11q0 1□, then 111q0□.
4. On blank enter qf: 111qf□.
5. The machine halts after three right moves and one final transition.

Example 2 — reject by infinite loop. A machine has no transition for symbol 0 in state q1. If it reads 0 in q1, what happens?

1. Under a common formal definition, the computation halts with no accepting state.
2. Therefore the input is rejected.
3. Some texts distinguish explicit reject states from undefined transitions, but both reject.
4. It does not count as acceptance.

Recognizers and deciders

Definition. A recognizer accepts every string in its language, but on strings outside it may reject or loop forever. A decider halts on every input and accepts exactly the language members. Every decidable language is recognizable; the converse is false.

Behavior on input	In L	Not in L
Decider	halt and accept	halt and reject
Recognizer	halt and accept	reject or loop

Example. A program that searches forever for a proof accepts theorem encodings when it finds one, but may not halt on non-theorems.

Exam point. “Does not accept” includes both rejection and divergence; “rejects” means the computation halts without acceptance.

Solved examples

Example 1 — halting within a bound. Let L contain pairs (M,w) where M accepts w within 20 steps. Decide membership.

1. Simulate M on w for at most 20 transitions.
2. If M accepts during that simulation, accept.
3. Otherwise reject after the bound, whether M rejects or would run longer.
4. This is decidable because the simulation has a fixed finite limit.

Example 2 — unbounded simulation. A machine simulates M on w and accepts if M accepts. What can it do if M loops?

1. The simulator continues forever.
2. It never incorrectly accepts a nonmember.
3. It is a recognizer for the acceptance problem, not a decider.
4. Nonmembership need not be reported in finite time.

Variants and simulation power

Definition. Multi-tape, nondeterministic, stay-put, and two-way-infinite-tape variants recognize the same class of languages as the standard single-tape deterministic TM, though time efficiency can change. A standard machine can encode several simulated tapes on one tape with delimiters and head markers.

Example. A two-tape machine's contents can be stored as delimited tracks on one tape, with marked positions for both simulated heads.

Exam point. Equivalent computability power does not imply equal running time.

Solved examples

Example 1 — nondeterministic recognition. A nondeterministic TM guesses a certificate and verifies it in finite time on each branch. When does it accept?

1. A computation is a sequence of nondeterministic choices.
2. Acceptance occurs if at least one branch reaches accept.
3. If every branch rejects or loops, it does not accept.
4. The machine recognizes the language represented by existence of an accepting branch.

Example 2 — stay-put simulation. Replace a stay-put transition (q,a)→(r,b,S) using only left/right moves.

1. Write b and move right into a new intermediate state.
2. Move left without changing the symbol read on that right cell, entering r.
3. The head returns to the original cell.
4. The simulated net effect is a stay-put move.

Enumerators and countability

Definition. An enumerator is a Turing machine with an output device that prints strings in a language, possibly with repetitions and in any order. A language is Turing-recognizable exactly when some enumerator lists its strings.

Example. A recognizer can be run on all strings in dovetailing order, printing a string whenever its run accepts.

Exam point. Dovetailing prevents one nonterminating computation from blocking all later candidates.

Solved examples

Example 1 — dovetailing. Enumerate all binary strings and simulate recognizer R on each.

1. At stage 1, run one step on the first candidate.
2. At stage 2, run two steps on the first two candidates; increase the finite diagonal each stage.
3. Every fixed candidate eventually receives arbitrarily many simulation steps.
4. Every accepted string is eventually printed.

Example 2 — finite language. Give an enumerator for {00,101}.

1. Print 00.
2. Print 101, then halt or continue idle.
3. The output set is exactly the language.

The universal Turing machine

Definition. A universal TM U receives an encoding ⟨M,w⟩, simulates the encoded machine M on input w, and reproduces its behavior. Machine descriptions and input strings can be represented as finite strings over a fixed encoding alphabet.

Example. A software interpreter is a practical analogue: program code plus data determines the simulated computation.

Exam point. Self-reference and universal simulation are central to undecidability proofs.

Solved examples

Example 1 — simulation outcome. If M accepts w after 7 steps, what does U do on ⟨M,w⟩?

1. U decodes M and w.
2. It simulates each transition of M.
3. After seven simulated steps, it enters its accepting simulation outcome.
4. U accepts if its specification is to recognize the acceptance language.

Decidable languages and closure

Definition. A language is decidable if some TM halts on every input and answers membership correctly. Decidable languages are closed under complement, union, intersection, concatenation, and Kleene star using finite simulations and dovetailing where needed.

Operation	Decidable closed?	Main idea
Complement	yes	swap accept and reject of a decider
Union/intersection	yes	run both deciders and combine answers
Concatenation	yes	test finitely many splits of the input
Star	yes	test finitely many segmentations of a finite input

Example. To decide L∩M, run deciders for both; accept exactly if both accept.

Exam point. For recognizers, complement closure does not hold in general.

Solved examples

Example 1 — concatenation decision. Given a finite input w of length n, decide whether w∈L·M when L and M are decidable.

1. There are n+1 split positions: w=xy.
2. For each split, run both deciders on x and y.
3. Accept if any split has x∈L and y∈M; otherwise reject after all splits.
4. The algorithm halts because it checks finitely many splits and each test halts.

Example 2 — star decision. Decide membership in L* when L is decidable.

1. A string of length n has finitely many ways to divide into consecutive pieces (at most 2^(n-1) for n>0).
2. Test whether all pieces in a segmentation belong to L.
3. Accept if one segmentation succeeds; ε is accepted using zero pieces.
4. Finite exhaustive search gives a decider.

Recognizable languages and complement

Definition. If both L and its complement are recognizable, then L is decidable: dovetail the two recognizers and accept or reject when either one accepts. Conversely, every decidable language and its complement are recognizable.

Example. Run recognizers R_L and R_notL one step at a time in alternation; exactly one must eventually accept if both recognize complements.

Exam point. A single recognizer for L cannot generally be complemented by swapping accept and reject because it may loop.

Solved examples

Example 1 — derive decidability. Suppose L and complement(L) each have recognizers. Describe a decider.

1. On input w, run one step of the L recognizer.
2. Run one step of the complement recognizer; continue alternating steps.
3. If L recognizer accepts, accept; if complement recognizer accepts, reject.
4. Exactly one recognizer eventually accepts, so the algorithm halts.
5. Thus L is decidable.

Undecidability and the acceptance problem

Definition. The acceptance problem A_TM={⟨M,w⟩: M accepts w} is recognizable but undecidable. A universal machine recognizes it; a diagonal argument shows no decider can correctly answer all encoded machine-input pairs.