L4.1 · The Turing machine

Chapter recap

A TM has a finite control and an unbounded read/write tape; δ(q, X) = (p, Y, L/R). IDs α q β track runs. On each input it accepts, rejects (or gets stuck), or loops forever. Design patterns: cross off symbols per pass (aⁿbⁿcⁿ in O(n²)), copy by carrying one symbol in the state, unary/binary arithmetic.

Merged rule card

From 4.1.1 The Turing machine: tape, head, states, halting

TM (Q, Σ, Γ, δ, q₀, □, F), δ : Q × Γ → Q × Γ × {L,R} (partial).
ID α q β (head on first of β). Outcomes: accept, reject (or stuck), loop.
Tape: read/write anywhere, unbounded. L(M) = accepted strings.

From 4.1.2 Designing Turing machines

Cross-off: mark X/Y/Z per pass, walk back; O(n²) for aⁿbⁿcⁿ.
Copy: carry one symbol in the state, append, return.
Unary +: replace separator, erase one 1. Binary +1: trailing 1s → 0, first 0/□ → 1.
TM computes f: halts with f(w) on the tape.

Practice questions

MCQ
Which is NOT a possible TM outcome?
1. accept
2. reject
3. loop
4. both accept and loop on the same input
MSQ
Which can a single-tape TM accept?
1. aⁿbⁿcⁿ
2. ww
3. a^{prime}
4. every CFL
NAT
Unary addition TM on 111 0 11 leaves how many 1s?
Write your answer before opening the key.
MCQ
A TM is stuck (no move defined) in a non-accepting state. It:
1. accepts
2. rejects (halts)
3. loops
4. restarts
MCQ
Next ID after a q b c with δ(q, b) = (p, X, R)?
1. a X p c
2. a p X c
3. p a X c
4. a X c p
MCQ
Compared with a PDA, a TM can:
1. only read input once
2. read and write anywhere on its tape
3. use only the top of memory
4. never loop

Answer key

Reveal answers when you’re ready

D — Deterministic: one outcome per input.
- A: Possible.
- B: Possible.
- C: Possible.
ABCD — TMs handle all of these.
5 — 3 + 2.
B — Halting without acceptance.
- A: Not accepting.
- C: It halted.
- D: No.
A — Write X, move right onto c.
- B: The head moved right, so p sits before c, not before X.
- C: The state is written where the head is, not at the start.
- D: The head is on c, not beyond it.
B — Free movement and writing.
- A: It can re-read.
- C: That is the stack.
- D: It can loop.