Unbounded power, and its exact edge

q₀bbb ⇒ bq₀bb ⇒ bbq₀b ⇒ bbbq₀□ ⇒ bbb□q_reject. Three b's skipped, then the blank triggers rejection — correctly, since no a exists anywhere.

δ(q₀,b)=(q_accept,b,R); δ(q₀,a)=(q₀,a,R); δ(q₀,□)=(q_reject,□,R). Identical structure, symbols swapped.

δ(q₀,a)=(q₀,a,R) (keep scanning through a's); δ(q₀,b)=(q_reject,b,R) (any b at all fails it); δ(q₀,□)=(q_accept,□,R) (reaching the end cleanly means every symbol seen was an a).

q₀□ (the head starts on a blank immediately, nothing was ever input) ⇒ □q_accept via δ(q₀,□)=(q_accept,□,R). The empty string vacuously satisfies "every symbol is an a" (there are no symbols to violate it) — correctly accepted.

Not wrong, just less direct — as long as it still correctly reaches q_accept for every string containing an a and q_reject for every string that doesn't, it recognises the identical language. Halting as early as possible is convenient, never required for correctness.

No — by the standard convention, the tape is unbounded only to the right; if the head is already at the leftmost cell, an L move either has no effect (stays put) or is simply disallowed by design, depending on the exact formalisation used. None of this chapter's examples ever need to test this edge case, since none of them move left at all.

A DFA's δ̂ and a PDA's run are both defined relative to consuming the input string — once every symbol is read, the computation is, by definition, over; there's a fixed, finite number of moves (at most the input's length, times some branching for a PDA) before a verdict must be read off. A Turing machine's moves aren't tied to input consumption at all — the head can sit on the same region rewriting it indefinitely, with no input left to run out of, so nothing in the definition guarantees the process ever reaches a halting state at all.

3 rounds. Each round marks exactly one of each symbol; after round 3, all 9 symbols are marked (3 a's, 3 b's, 3 c's), all three types exhausted simultaneously → accept.

No. Scanning left to right: a,a (fine, still in the "a" region), then c (moves into the "c" region) then b — a b appearing after a c has already been seen violates a*b*c* order. Rejected before Phase 2 ever begins.

Same shape, one fewer symbol type: Phase 1 checks a*b*; Phase 2 repeats "mark leftmost unmarked a, mark leftmost unmarked b" per round, accepting when both are exhausted together and rejecting if one runs out first. Strictly simpler than L_3eq's version — two things to keep in step instead of three.

Yes — extend Phase 1's shape check to a*b*c*d*, and Phase 2 to mark one of each of the four types per round, rejecting the moment any type runs out while others remain. Nothing about the technique is specific to exactly three symbol types.

Yes, just as correctly — what actually matters is comparing the final counts marked of each type, not the order in which the marking happens. Marking "one of each per round" and "all of one type, then all of the next" both end up needing to check that every symbol got marked and none were left over; either organisation works, they're just different bookkeeping strategies for the identical underlying comparison.

No. Phase 1 always finishes in one bounded pass. Phase 2's rounds each either mark exactly one of each type (strictly reducing the number of unmarked symbols by 3) or immediately halt (accept or reject) — since the tape is finite, the number of possible rounds is bounded, so the machine always halts. This will matter directly in Section 7.3.

A PDA processes input in one left-to-right sweep, and its only memory is a stack read from the top — there's no way to "return to the start" of the input once past it, and no way to mark an arbitrary earlier position for a future pass to find, since the input isn't even stored anywhere the PDA can revisit; it's consumed as it's read. The tape's defining feature — a persistent, revisitable record the head can walk back over — has no analogue in a PDA's architecture at all, which is exactly why this algorithm needed a genuinely different machine, not just a cleverer stack discipline.

Yes. Any DFA already halts on every input (Chapter 2's δ̂ is total and finite), and a DFA can be simulated directly by a TM that halts exactly when the DFA would — decidability inherited for free.

Yes — Section 5.4's CYK algorithm decides membership for any CNF (hence any) context-free grammar in finite time, for every input, always halting. Every CFL is therefore decidable.

Yes — this is purely a syntactic property of the machine's own description (count the states listed), checkable by direct inspection with no simulation of M's behaviour required at all, and any direct-inspection check like this always halts.

Simulate M on w directly. If M halts and accepts, the simulator halts and accepts too. If M rejects, so does the simulator. The only gap: if M loops forever on w, the simulator loops forever too — never rejecting, only ever "not yet." That's exactly the recognisable-but-possibly-not-decidable shape.

Decidability only claims some TM decides L_3eq — which this chapter did in fact construct, but the claim "L_3eq ∈ R" would have been equally true before Section 7.2 was ever written. Existence of a deciding machine doesn't depend on anyone having found or written it.

L is decidable — directly from this section's stated theorem (L decidable ⇔ L and complement(L) both recognisable). Run both recognisers in parallel on the same input; exactly one of them is guaranteed to eventually accept, and whichever does gives the correct yes/no answer in finite time.

With only one recogniser (for L itself), a "no" answer has no source: if w ∉ L, L's recogniser might simply loop forever, and there is no second process to eventually report "reject" instead. The parallel-race trick specifically needs two processes, each guaranteed to halt on one side of the yes/no divide, so that whichever side w actually falls on, some process eventually finishes. One recogniser alone only ever covers the "yes" side of that guarantee.

Yes, for every w. Problem 7.2.6 showed that machine halts on every input, regardless of whether it accepts or rejects — halting is all HALT_TM asks about, and it holds universally here.

D halts (and accepts). D is built to do the opposite of H's prediction — if H predicts non-halting, D deliberately halts instead.

No — agreeing removes the contradiction entirely. If D matches whatever H predicts, then running D on ⟨D⟩ simply confirms H's prediction rather than falsifying it; there's no case where D's actual behaviour and H's stated answer disagree. The deliberate disagreement is the entire mechanism; without it, H's hypothetical existence is never challenged.

Both ask a global behavioural question about a machine ("does it halt on this input," "does it accept anything at all") that would require somehow anticipating the machine's entire, possibly infinite, behaviour in advance — exactly the kind of self-referential question the diagonalization technique is built to break.

The theorem is about the non-existence of one universal algorithm, not about every individual case being unknowable. Countless specific programs are easily proven to halt (or not) by direct argument — a simple loop with a fixed bound obviously halts. What's impossible is a single procedure that correctly settles every program, with no exceptions, uniformly.

Self-reference is exactly the mechanism that produces the contradiction: D's behaviour on ⟨D⟩ needs to be defined in terms of H's prediction about that same behaviour, so that whatever H says gets immediately tested against the very case it was asked about. Asking about a different machine entirely would let D's actual behaviour and H's prediction simply agree with no tension, since nothing would force D's own actions to depend on the answer being given about D.

Every earlier limit in this book (L_eq needing more than finite memory, {ww^R} needing nondeterminism to avoid a stack's one-directional access) was resolved by handing the machine more or differently-shaped resources — a bigger state set, a stack, a tape. HALT_TM is undecidable no matter how much memory, of any shape, a machine is given; a Turing machine already has unbounded, arbitrarily-shaped memory (the tape), and the problem persists regardless. The limit here isn't about resources at all — it's a logical limit, arising from self-reference itself, the same kind of wall Cantor's argument (Chapter 1) hit when counting infinities. No machine, however generously equipped, escapes a contradiction built specifically to disagree with it.

Q, Σ, Γ, δ, q₀, q_accept, q_reject.

State q₃, head pointing at the first symbol after the state marker — here, "b." The tape reads "abc."

Accept, reject, or loop forever (never halting at all).

Not regular (Chapters 1, 2, 3 — three independent proofs). Not context-free (Chapter 5, the CFL Pumping Lemma). Decidable (this chapter — Section 7.2's machine halts on everything, correctly).

Recognisable: some TM halts-and-accepts on every string in the language (may loop on strings outside it). Decidable: some TM halts on every input whatsoever, always correctly accepting or rejecting.

Recognisable: yes (simulate and accept if it halts). Decidable: no (Section 7.4's diagonalization proof).

D loops forever — deliberately doing the opposite of H's prediction, which is precisely what manufactures the contradiction.

No compiler can reliably detect every infinite loop before running a program — real tools instead flag only the easy, recognisable cases and stay silent (rather than wrongly certain) on the rest.

True — NTM = DTM in power (Section 7.2's hero preview), restoring the Chapter 2 pattern (NFA=DFA) that Chapter 6 broke for pushdown automata (NPDA≠DPDA). The stack's restricted access, not nondeterminism itself, was what caused Chapter 6's gap.

Chapter 1 counted: uncountably many languages, only countably many machines, so most languages have no machine at all — a non-constructive existence argument naming no specific example. This chapter built one exact, named language (HALT_TM) and proved, by explicit self-referential construction, that it specifically has no deciding machine — a constructive proof pointing at one concrete case. Two different techniques (counting; diagonalization/self-reference), the same underlying wall.