Designing Turing machines

1. What does δ(q, X) = (p, Y, L) do?
   Stuck? Peek at 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.

   Read lesson 4.1.1

2. Why is aⁿbⁿcⁿ not a CFL?
   Stuck? Peek at 3.4.3 Pumping lemma for CFLs

   • L CFL ⇒ ∃p ∀z ∈ L, |z| ≥ p: z = uvwxy, |vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L ∀i ≥ 0. p = 2ᵏ (CNF, k variables).
   • Non-CFL: aⁿbⁿcⁿ, ww, aⁿbᵐcⁿdᵐ, #a=#b=#c, a^{n²}, a^{prime}, aⁱbʲcᵏ (i<j<k).
   • Unary CFL ⇒ regular. Complement of ww is a CFL.

   Read lesson 3.4.3

3. How does a DFA track divisibility by k?
   Stuck? Peek at 1.1.3 DFA design patterns

   Language (|w| = k pattern)	Minimal states
   starts with w	k + 2
   contains w / ends with w	k + 1
   |x| ≡ r mod n	n
   |x| = k, |x| ≤ k	k + 2
   |x| ≥ k	k + 1
   #a mod m and/or #b mod n	m·n (typical)
   binary value ≡ 0 mod k, k odd	k
   binary ÷ 2ʲ	j + 1
   k-th symbol from start fixed	k + 2

   Divisibility update: r ← (base·r + digit) mod k.

   Read lesson 1.1.3

TM design is programming with a pencil: mark what you have used, walk back, repeat. Three patterns cover GATE: crossing off (matching counts), copying (shuttling symbols across), and arithmetic on unary or binary numbers.

How many passes over the tape does the cross-off TM for aⁿbⁿcⁿ make on a³b³c³?

Prediction check

Three marking passes (one per a), each walking right then back, plus a final check pass. Each pass costs O(n) moves, so O(n²) in total.

Pattern 1 — crossing off

Mark one symbol of each kind per pass with a new tape symbol (X, Y, Z); walk back to the leftmost unmarked symbol; repeat; finally check nothing unmarked remains. Works for aⁿbⁿcⁿ, aⁿbⁿ, #a = #b = #c, ww (cross off matching symbols in the two halves after finding the middle).

Pattern 2 — copying

To turn w into w#w: repeatedly mark the leftmost unmarked symbol of w (remember it in the state — finitely many symbols, so finitely many “carrying” states), walk to the end, write it, walk back. Finally restore the marks. The state carries one symbol at a time — finite memory is enough for the carrying; the tape stores the rest.

Pattern 3 — unary arithmetic

Numbers as 1ⁿ. Addition 1ᵐ01ⁿ → 1ᵐ⁺ⁿ: replace the separator 0 by 1, go to the end, erase one 1. Multiplication: for each 1 of the first number, copy the second number to the output (copying inside a loop). Binary increment: go to the right end, flip trailing 1s to 0, the first 0 (or blank) to 1.

TMs as function computers

A TM computes f if, started on w, it halts with f(w) on the tape. Functions computed by TMs that halt on every input are the (total) computable functions.

Putting it together

• Cross-off, copy and arithmetic patterns cover TM design questions.
• Extra tape symbols are the TM’s scratch marks.
• A TM computes a function by halting with the answer on its tape.

aⁿbⁿcⁿ cross-off, one pass:
 [a] a b b c c   →   X a [b] b c c   →   X a Y b [c] c   →   X a Y b Z c   (walk back to X, step right)
 when q0 sees Y: scan right over Y Z; blank ⇒ accept; any a/b/c left ⇒ reject.

Would more tapes, more heads, or guessing make TMs stronger? No — the next lesson shows every reasonable variant has the same power, and introduces a weaker cousin with a bounded tape.

1. MCQ

   Running time of the cross-off TM for aⁿbⁿcⁿ:

   1. O(n)
   2. O(n log n)
   3. O(n²)
   4. O(2ⁿ)
2. MSQ

   Which languages can the cross-off idea handle?

   1. aⁿbⁿcⁿ
   2. #a = #b = #c
   3. aⁿbⁿ
   4. any finite language
3. NAT

   tmInc on input 0111: how many 1s are in the output?

   Write your answer before opening the key.

4. MCQ

   In the copying TM, where is the symbol being carried remembered?

   1. on a stack
   2. in the state
   3. in a second tape
   4. nowhere

• crossing-off technique
• copying technique
• unary arithmetic TM
• computable function

1. How does a TM accept aⁿbⁿcⁿ?
   Reveal answer

   Cross off one a, one b, one c per pass; accept if all are marked.
2. Where does a copying TM remember the carried symbol?
   Reveal answer

   In its finite state.
3. Time of the one-tape cross-off TM for aⁿbⁿcⁿ?
   Reveal answer

   O(n²).