The Turing machine: tape, head, states, halting

1. Classify { aⁿbⁿcⁿ }.
   Stuck? Peek at 3.4.4 Drill: regular, DCFL, CFL or not CFL?

   • Ladder: bounded → regular; one comparison, no guess → DCFL; one comparison with a guess → CFL; two comparisons / crossing / copy / squares → not CFL.
   • “or” of comparisons → CFL not DCFL; “and” → not CFL.
   • Always check finiteness and collapses (unions that become a*b*).

   Read lesson 3.4.4

2. What is an instantaneous description of a PDA?
   Stuck? Peek at 3.3.1 Stack primer and the push-down automaton

   • PDA (Q, Σ, Γ, δ, q₀, Z₀, F); δ(q, a|ε, X) ⊆ Q × Γ*; label a, X/γ (γ = ε pop, X keep, YX push).
   • ID (q, w, γ), top first; ⊢ one move, ⊢* many.
   • Nondeterministic by default; ε-moves still see the stack.

   Read lesson 3.3.1

3. What are the three possible outcomes of a computation?
   Stuck? Peek at 0.1.1 What “computation” means

   • Machine: reads a finite input symbol by symbol, changes mode, ends with yes (accept) / no (reject) — or may never end.
   • Decision problem: a question whose answer is yes or no for every input.
   • Machines differ by memory: finite modes → pile of plates → endless notebook → beyond all machines.
   • Finite memory works iff the fact you must carry stays bounded (even/odd, remainder, “seen x?”). Unbounded counts/comparisons break it.

   Read lesson 0.1.1

Imagine a clerk with a pencil, an eraser and an endless strip of squared paper. They look at one square at a time, may overwrite it, move one square left or right, and follow a finite rulebook. In 1936 Alan Turing argued that anything a person can compute by rote can be done this way. That clerk is the Turing machine (TM) — the model behind every computer, and the machine whose limits Phase 5 explores.

A PDA could only touch the top of its stack. What two abilities does a tape add that a stack lacks?

Prediction check

The head can move back over what was written (read anywhere, not only the top), and it can overwrite any cell. The input itself sits on the tape and can be marked, erased, re-read many times.

The machine

A TM has a finite set of states, an infinite tape of cells (initially the input followed by blanks □), and a head on the first input cell. Each step: read the symbol under the head; based on (state, symbol) write a symbol, move L or R, and change state.

Formal definition

The standard (deterministic) TM has at most one move per (state, symbol). Many books (and GATE) use a single accept state q_acc and a reject state q_rej instead of F. The machine halts when it enters an accepting/rejecting state, or when no move is defined (treated as reject).

Instantaneous descriptions

Example: X q1 bc means tape “Xbc”, state q1, head on b. A move δ(q1, b) = (q2, Y, R) gives X Y q2 c.

Three outcomes

• Accept: reaches an accepting state.
• Reject: reaches the reject state or gets stuck (no move).
• Loop: runs forever, never halting.

L(M) = strings M accepts. Strings outside L(M) are either rejected or looped on — and an observer watching a long run cannot always tell which is happening. That gap is the heart of Phase 5.

Putting it together

• A TM reads, writes and moves on an unbounded tape under a finite rulebook.
• IDs α q β record configurations.
• On any input it accepts, rejects, or loops — and looping is not rejecting.

tape:   … □ □ [a] b  c  □ □ …          finite control
                 ▲                      ┌────────┐
                head ───────────────────┤ state q│   δ(q, a) = (p, X, R)
                                        └────────┘   write X, move right, go to p

Now design TMs: crossing off symbols, copying strings, doing arithmetic in unary.

1. MCQ

   In a standard TM, δ has the form:

   1. Q × Σ → Q
   2. Q × Γ → Q × Γ × {L, R}
   3. Q × Σ × Γ → Q × Γ*
   4. Q → Γ
2. MSQ

   Which outcomes are possible for a TM on some input?

   1. accept
   2. reject
   3. run forever
   4. accept and reject
3. MCQ

   ID a q3 bc means:

   1. state q3, head on a
   2. state q3, head on b
   3. state q3, head on c
   4. tape is q3
4. NAT

   tmLoop above: how many of the inputs ε, a, b, ab, aa are accepted?

   Write your answer before opening the key.

• Turing machine (TM)
• tape, head, blank □
• tape alphabet Γ
• TM transition δ(q, X) = (p, Y, D)
• ID α q β
• halting: accept / reject / loop

1. TM transition function type?
   Reveal answer

   δ : Q × Γ → Q × Γ × {L, R}
2. Three possible TM outcomes?
   Reveal answer

   Accept, reject, loop forever.
3. What does ID α q β mean?
   Reveal answer

   Tape αβ, state q, head on the first symbol of β.