TM variants, linear bounded automata and context-sensitive languages

1. Running time of the cross-off TM for aⁿbⁿcⁿ?
   Stuck? Peek at 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.

   Read lesson 4.1.2

2. NFA with n states → DFA states at most?
   Stuck? Peek at 1.2.3 Subset construction and the 2ⁿ blow-up

   • Subset construction: start {q₀} (or ECLOSE(q₀)); δ(S,a) = ⋃ δ(q,a) (then ECLOSE); accept iff S ∩ F ≠ ∅; ∅ = dead state.
   • ≤ 2ⁿ states; count only reachable sets.
   • ε-removal: δ'(q,a) = ECLOSE(δ(ECLOSE(q), a)); F' = {q : ECLOSE(q) ∩ F ≠ ∅}.
   • k-th from end is 1: NFA k+1, DFA 2ᵏ. k-th from start: DFA k+2.
   • DFA ≡ NFA ≡ ε-NFA in power.

   Read lesson 1.2.3

3. Is an NPDA more powerful than a DPDA?
   Stuck? Peek at 3.3.3 Designing PDAs; DPDA vs NPDA; DCFL ⊂ CFL

   • Recipe: stack stores what is unbounded; states store the phase; Z₀ detects empty; accept via ε, Z₀.
   • DPDA: ≤ 1 move per (q, a|ε, X), and no ε-move competing with input moves.
   • Regular ⊊ DCFL ⊊ CFL. wwᴿ, aⁿbⁿ ∪ aⁿb²ⁿ, aⁱbʲcᵏ (i=j or j=k): CFL not DCFL.
   • DCFL ⇒ unambiguous grammar; not conversely.

   Read lesson 3.3.3

Real computers have many memory banks, random access, parallel threads. Would a Turing machine with more tapes, or the power to guess, compute more? Remarkably, no: every reasonable upgrade can be simulated by a plain one-tape TM, only slower. This robustness is why “Turing machine” is the definition of computable. The one change that does matter is removing space: a tape no longer than the input gives a strictly weaker machine.

For finite automata, guessing added no power; for stack machines it did. What do you expect for Turing machines?

Prediction check

No extra power. A deterministic TM can explore every branch of a nondeterministic TM breadth-first (to avoid getting lost in a looping branch). It may take exponentially longer, but it accepts the same strings.

Equivalent variants

• Multi-tape TM: k tapes and heads. Simulated on one tape by interleaving tracks and marking head positions; t steps become O(t²).
• Nondeterministic TM: breadth-first simulation; same languages.
• Two-way infinite tape: fold it in half onto a one-way tape with two tracks.
• Multi-head, multi-track, 2-D tape, stay-put moves: all equivalent.
• PDA with two stacks: equivalent to a TM (left stack = tape left of the head, right stack = the rest). Two counters also suffice.

Two stacks = a tape

Cut the tape at the head: everything to the left is one stack (top = cell next to the head), the head cell and everything to the right is the other stack. Moving the head is popping one stack and pushing the other. So adding a single second stack jumps straight from CFLs to everything a TM can do.

Linear bounded automata

It can still mark and re-read the input, so aⁿbⁿcⁿ, ww and {aᵖ : p prime} are LBA languages. With finitely many states and cells, its number of configurations on input length n is bounded (|Q| · n · |Γ|ⁿ), so a halting check is possible: every LBA language has an always-halting decision procedure.

Context-sensitive grammars and languages

CSG languages = LBA languages = the context-sensitive languages (CSL). Example grammar for aⁿbⁿcⁿ (n ≥ 1): S → aSBC | aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc.

Facts: CFL ⊂ CSL (strict: aⁿbⁿcⁿ); every CSL is decided by an always-halting TM; CSLs are closed under ∪, ∩, complement, concatenation, star.

Putting it together

• Every unbounded-memory variant of the TM has the same power.
• Two stacks already equal a tape.
• Bounding the tape to the input gives LBAs and the context-sensitive languages, strictly between CFL and TM languages.

memory upgrades and their power
 DFA (no memory)            → regular
 PDA (1 stack)              → CFL
 LBA (tape = input length)  → CSL
 TM  (unbounded tape)       → RE        ← 2 stacks, k tapes, nondeterminism: all land here

All machines with unbounded tapes have the same power. But some TMs halt on every input and some don’t — that difference splits the TM languages into two classes, next.

1. MSQ

   Which are equivalent in power to a standard TM?

   1. multi-tape TM
   2. nondeterministic TM
   3. PDA with two stacks
   4. PDA with one stack
2. MCQ

   An LBA is:

   1. a DFA with a stack
   2. a TM with tape bounded by the input length
   3. a TM with two tapes
   4. a PDA with a bound on stack height
3. MCQ

   Which rule is allowed in a context-sensitive grammar?

   1. AB → a
   2. aA → aBb
   3. AbC → b
   4. S → ε (S on a right side)
4. NAT

   A one-tape simulation of a multi-tape TM running t = 100 steps takes on the order of how many steps (t²)?

   Write your answer before opening the key.

• multi-tape TM
• nondeterministic TM
• two-way infinite tape
• two-stack PDA
• linear bounded automaton (LBA)
• context-sensitive grammar (CSG)
• context-sensitive language (CSL)

1. Does nondeterminism add power to TMs?
   Reveal answer

   No — only speed differs.
2. Power of a PDA with two stacks?
   Reveal answer

   Same as a TM.
3. What does an LBA accept?
   Reveal answer

   Exactly the context-sensitive languages.
4. CSG rule restriction?
   Reveal answer

   |α| ≤ |β| (non-contracting).