Variants of TMs

What are Variants of Turing Machines?

Variants are different designs of Turing Machines with modified features.

Key Question

“Do these variants have more computational power than standard TM?”

Surprising Answer

NO! All reasonable variants are equivalent to standard TM.

Equivalence means:

• Variant can simulate standard TM
• Standard TM can simulate variant
• They recognize same class of languages

Church-Turing Thesis (Extended)

Extended Church-Turing Thesis: All reasonable computational models have the same power as Turing Machines.

“Reasonable” means:

• Finite description
• Discrete steps
• Deterministic or bounded non-determinism

Consequence: Can’t make TM more powerful by adding features!

Standard vs Variant

Standard TM:

• One tape
• Two-way infinite tape
• One read/write head
• Deterministic
• Moves L or R

Variants modify one or more features

Variant 1: Multi-Tape Turing Machine

Definition

Multi-tape TM has k tapes (k ≥ 1)

Components:

• k tapes (each infinite in both directions)
• k independent read/write heads
• One finite control
• Input initially on tape 1, others blank

Visualization

 Tape 1:  [a][b][c][B][B]...
            ↑
         Head 1

 Tape 2:  [B][X][Y][B][B]...
               ↑
            Head 2

 Tape 3:  [B][B][B][B][B]...
            ↑
         Head 3

    Finite Control (state q₁)

Transition Function

Signature: δ: Q × Γᵏ → Q × Γᵏ × {L,R,S}ᵏ

Reads: k symbols (one from each tape)

Writes: k symbols (one to each tape)

Moves: k directions (each head moves independently)

Example (2-tape):

δ(q₀, a, X) = (q₁, b, Y, R, L)

Meaning:

• Read ‘a’ from tape 1, ‘X’ from tape 2
• Write ‘b’ to tape 1, ‘Y’ to tape 2
• Move tape 1 head Right, tape 2 head Left
• Go to state q₁

Advantages

More intuitive: Separate tapes for different purposes

• Tape 1: Input
• Tape 2: Work space
• Tape 3: Output

Faster: Can access different parts simultaneously

Easier to design: Natural for many algorithms

Example: {0ⁿ1ⁿ | n ≥ 0} on 2-Tape TM

Strategy:

• Tape 1: Input (read-only)
• Tape 2: Copy 0’s

Algorithm:

1. Copy all 0's from tape 1 to tape 2
2. For each 1 on tape 1:
   - Remove one 0 from tape 2
3. Accept if tape 2 empty and tape 1 finished

Transitions:

// Phase 1: Copy 0's
δ(q₀, 0, B) = (q₀, 0, 0, R, R)  // Copy 0 to tape 2
δ(q₀, 1, B) = (q₁, 1, B, S, L)  // Start matching phase

// Phase 2: Match 1's with 0's
δ(q₁, 1, 0) = (q₁, 1, B, R, L)  // Remove one 0 for each 1
δ(q₁, B, B) = (qaccept, B, B, S, S) // All matched!

Much simpler than single-tape version!

Equivalence Theorem

Theorem: Every k-tape TM has an equivalent single-tape TM.

Proof idea: Simulate k tapes on one tape

Simulation technique:

Single tape format:
[#][tape1_contents][#][tape2_contents][#][tape3_contents][#]...

Mark head positions with special symbols

Example (2 tapes → 1 tape):

Tape 1: a b ↓c d
Tape 2: X ↓Y Z

↓

Single tape: #a b ċ d#X Ẏ Z#
             (dot marks head position)

Simulation Steps

To simulate one step of k-tape TM:

1. Scan: Read marked symbols (simulate reading from k heads)
2. Update: Write new symbols, update marks (simulate k writes and moves)
3. Return: Go back to start

Cost: O(n) steps for each k-tape step

Result: k-tape TM with time T(n) → single-tape TM with time O(n·T(n))

Variant 2: Multi-Head Turing Machine

Definition

Multi-head TM has k heads on one tape

Features:

• Single tape
• k independent read/write heads
• All heads move on same tape

Visualization

    ↓Head 1      ↓Head 2    ↓Head 3
[a][b][c][d][e][f][g][h][i][B]...

    Finite Control

Advantage

Can compare distant parts of tape without moving back and forth

Example: Check if input = ww

• Head 1 at position i
• Head 2 at position n/2 + i
• Compare simultaneously!

Equivalence

Theorem: Multi-head TM ≡ Standard TM

Proof: Similar to multi-tape simulation

Variant 3: Two-Way Infinite vs One-Way Infinite Tape

Standard: Two-Way Infinite

... ← [B][B][a][b][c][B][B] → ...
              ↑
           (extends both ways)

Variant: One-Way Infinite (Semi-infinite)

LEFT END → [a][b][c][B][B] → ...
            ↑
         (only extends right)

Leftmost cell: Special end marker (can’t move left from here)

Equivalence

Theorem: One-way infinite TM ≡ Two-way infinite TM

Simulation: Fold two-way tape onto one-way tape

Two-way:
... c b a | d e f ...
      ← | →

↓ Fold

One-way:
[#][a][d][b][e][c][f]...
   ↑   ↑   ↑
   0   1   2  (positions)

Even positions: Right side of original Odd positions: Left side of original (reversed)

Two tracks: Remember original direction

Variant 4: Multi-Dimensional Tape

Definition

2D Tape: Infinite grid

    ... B B B B B ...
    ... B a b c B ...
    ... B d e f B ...
    ... B g h i B ...
    ... B B B B B ...
         ↑
       (Head can move: Up, Down, Left, Right)

Directions: U (up), D (down), L (left), R (right)

Higher dimensions: 3D, 4D, … grids

Example Use

Graph algorithms:

• Store adjacency matrix on 2D tape
• Navigate naturally

Equivalence

Theorem: 2D (or any k-D) TM ≡ Standard TM

Simulation: Encode 2D coordinates as 1D positions

Pairing function: (x, y) → single number

Example:

(0,0)→0, (0,1)→1, (1,0)→2, (1,1)→3, (0,2)→4, ...

Zig-zag encoding:

(0,0) (0,1) (1,0) (0,2) (1,1) (2,0) ...
  0     1     2     3     4     5   ...

Variant 5: Non-Deterministic Turing Machine (NTM)

Definition

NTM: Can have multiple possible transitions

Transition relation: δ: Q × Γ → P(Q × Γ × {L,R})

Accepts: If any computation path leads to acceptance

Example

δ(q₀, a) = {(q₁, X, R), (q₂, Y, L)}

Two choices: Go to q₁ or q₂

Computation Tree

         q₀abc
        /     \
   q₁Xbc       Yq₂bc
    / \         / \
  ...  ...    ...  ...
   ↓    ↓      ↓    ↓
accept reject accept reject

Accept if ANY path reaches qaccept

Advantages

Guess and verify: Guess solution, then verify

Example: Hamiltonian path

• Guess path non-deterministically
• Verify it visits all vertices once

Most Important Theorem!

Theorem: Every NTM can be simulated by a DTM.

NTM ≡ DTM (same power!)

Shocking result: Non-determinism doesn’t add power!

Contrast:

• NFA = DFA ✓ (same power)
• NPDA ≠ DPDA ✗ (NPDA more powerful)
• NTM = DTM ✓ (same power!)

Simulation of NTM by DTM

Strategy: Use breadth-first search on computation tree

3-tape DTM:

• Tape 1: Input (never modified)
• Tape 2: Simulation tape (current path)
• Tape 3: Path encoding (which branches taken)

Algorithm:

1. Try all paths of length 1
2. Try all paths of length 2
3. Try all paths of length 3
...
k. If any path accepts, ACCEPT

Breadth-first: Ensures we find accepting path if it exists

Example (paths to try):

Length 0: ε
Length 1: L, R
Length 2: LL, LR, RL, RR
Length 3: LLL, LLR, LRL, LRR, RLL, ...

Time Complexity

If NTM runs in time T(n):

• DTM simulation takes O(bᵀ⁽ⁿ⁾) time
• b = max branching factor

Exponential blowup! But still computable.

Consequence: NTM doesn’t solve undecidable problems, just faster for some problems

Variant 6: Enumerator

Definition

Enumerator: TM with attached printer

No input tape! Just generates strings and prints them.

Visualization

   Enumerator
  ┌──────────┐
  │          │
  │ TM Logic │
  │          │
  └────┬─────┘
       │
       ↓
    Printer
  (prints strings)

Operation

Runs forever, printing strings:

Output: w₁, w₂, w₃, w₄, ...

Language of Enumerator

L(E) = {w | E eventually prints w}

“Eventually”: May take arbitrarily long

Example: Enumerator for {aⁿbⁿ | n ≥ 0}

Print: ε
Print: ab
Print: aabb
Print: aaabbb
Print: aaaabbbb
...

Pattern: Print aⁿbⁿ for n = 0, 1, 2, 3, …

Equivalence Theorem

Theorem: Language is Turing-recognizable ⟺ Some enumerator enumerates it.

Proof (⇒): TM → Enumerator

Given TM M recognizing L:

Enumerator E:
  For i = 1, 2, 3, ...:
    For each string w of length ≤ i:
      Run M on w for i steps
      If M accepts w, print w

Proof (⇐): Enumerator → TM

Given enumerator E for L:

TM M(w):
  Run E
  If E prints w, accept
  (Run forever if w ∉ L)

Uses

Generate all proofs in a formal system

Enumerate all programs in a programming language

List all solutions to a problem

Variant 7: Stay Option

Definition

Allow head to stay: δ: Q × Γ → Q × Γ × {L, R, S}

S: Stay (don’t move)

Example

δ(q₀, a) = (q₁, X, S)  // Write X but don't move

Equivalence

Theorem: TM with stay ≡ Standard TM

Simulation: Stay = Move right, then move left

δ(q, a) = (p, b, S)
    ↓ Replace with
δ(q, a) = (q', b, R)
δ(q', c) = (p, c, L) for all c ∈ Γ

Variant 8: Multiple Tracks

Definition

k tracks: Tape divided horizontally

Track 1: [a][b][c][d]...
Track 2: [1][0][1][0]...
Track 3: [X][Y][Z][W]...
          ↑
      (One head reads all tracks)

Head reads k-tuple: (a, 1, X)

Implementation

Tape alphabet: Γ = Γ₁ × Γ₂ × … × Γₖ

Each cell stores tuple: (symbol₁, symbol₂, …, symbolₖ)

Uses

Track 1: Input symbols Track 2: Marks (processed/unprocessed) Track 3: Additional info

Equivalence

Theorem: k-track TM ≡ Standard TM

Already equivalent! Just different notation.

Single tape with larger alphabet Γ = Γ₁ × Γ₂ × … × Γₖ

Variant 9: Read-Only Input and Write-Only Output

Definition

Three tapes:

1. Input tape: Read-only, one-way (→)
2. Work tape: Read/write, two-way
3. Output tape: Write-only, one-way (→)

Visualization

Input:  [a][b][c]... →  (read-only, one-way)
         ↓

Work:   [X][Y][Z]...  ⟷  (read/write, two-way)
         ↓

Output: [1][0][1]... →  (write-only, one-way)

Uses

Complexity theory: Separate input/output from workspace

Space complexity: Measure only work tape usage

Equivalence

Theorem: 3-tape input/work/output TM ≡ Standard TM

Simulation: Multi-tape simulation technique

Variant 10: Queue Automaton

Definition

Replace tape with queue (FIFO)

Operations:

• Enqueue (write at rear)
• Dequeue (read from front)

Example

Queue: Front → [a][b][c][d] ← Rear
        ↑           ↑
     Dequeue    Enqueue

Equivalence

Theorem: Queue automaton ≡ Standard TM

Proof: Simulate tape on queue

• To move right: Dequeue, process, enqueue
• To move left: Rotate entire queue

Awkward but possible!

Summary of Equivalences

ALL EQUIVALENT! ✓

Robustness of TM Model

Church-Turing Thesis: Any reasonable modification still equivalent

Why robust?

1. Infinite tape (unlimited memory)
2. Can read/write anywhere (random access)
3. Turing-complete (can simulate any algorithm)

Can’t make more powerful by:

• Adding more tapes
• Adding more heads
• Adding more dimensions
• Adding non-determinism
• Changing tape structure

Complexity Considerations

Time complexity may differ!

Example: k-tape TM

• Can be faster than single-tape
• But polynomially related: T(n) vs O(n·T(n))

Complexity classes:

• P: Polynomial time on DTM
• NP: Polynomial time on NTM
• P vs NP: Open problem!

Space complexity also differs

Non-Equivalent Extensions

What would make TM more powerful?

Unlimited parallelism:

• Infinitely many heads
• All working simultaneously
• Not equivalent! (Hypercomputation)

Analog computation:

• Real number operations
• Infinite precision
• Not standard TM model

Oracle machines:

• Can query undecidable oracle
• More powerful! (relative to oracle)

Quantum TM:

• Superposition of states
• Possibly more efficient (P vs BQP)
• But same problems decidable (Church-Turing thesis holds)

Practical Implications

Algorithm design: Choose most convenient variant

• Multi-tape: Easier to design
• Standard: Theoretical analysis

Proof technique: Reduce to simplest model

Real computers: Essentially multi-tape TMs (with finite tape)

Important Exam Points

1. ✓ All standard variants equivalent: Multi-tape, multi-head, 2D, NTM, etc.
2. ✓ Multi-tape: k tapes, k heads, one control
3. ✓ Simulation: k-tape → single-tape (mark head positions)
4. ✓ NTM = DTM: Non-determinism doesn’t add power!
5. ✓ Enumerator: Prints all strings in language
6. ✓ One-way vs two-way: Fold tape for simulation
7. ✓ Time complexity: May differ (polynomial blowup)
8. ✓ Church-Turing thesis: All reasonable models equivalent
9. ✓ Robustness: Can’t make TM more powerful with standard modifications
10. ✓ NFA=DFA, NPDA≠DPDA, NTM=DTM: Important distinction!

Common Mistakes to Avoid

✗ Mistake 1: Thinking multi-tape more powerful
✓ Correct: Equivalent, just more convenient

✗ Mistake 2: Thinking NTM more powerful than DTM
✓ Correct: NTM = DTM in decidability (differs in time)

✗ Mistake 3: Confusing NTM with NPDA
✓ Correct: NPDA ≠ DPDA, but NTM = DTM

✗ Mistake 4: Claiming 2D tape more powerful
✓ Correct: Can simulate on 1D tape

✗ Mistake 5: Forgetting time complexity differences
✓ Correct: Equivalent in power, different in efficiency

✗ Mistake 6: Thinking enumerator different from TM
✓ Correct: Equivalent to Turing-recognizable

Practice Questions

Q1: Is multi-tape TM more powerful than single-tape?

Answer: No, equivalent! Can simulate multi-tape on single-tape.

Q2: How to simulate 2-tape TM on 1-tape TM?

Answer: Use format #tape1#tape2#, mark head positions with dots.

Q3: Can NTM solve undecidable problems?

Answer: No! NTM = DTM in decidability power.

Q4: What is an enumerator?

Answer: TM that prints all strings in a language (no input).

Q5: How to simulate 2D tape on 1D tape?

Answer: Use pairing function (x,y) → single position.

Q6: Why is NTM = DTM surprising?

Answer: Because NPDA ≠ DPDA (non-determinism helps PDAs but not TMs).

Q7: Can we make TM more powerful by adding features?

Answer: No! Church-Turing thesis: all reasonable models equivalent.

Q8: Time complexity difference between multi-tape and single-tape?

Answer: T(n) on k-tape → O(n·T(n)) on single-tape.

Q9: What does “equivalent” mean for TM variants?

Answer: Can simulate each other, recognize same languages.

Q10: Is DTM faster than NTM?

Answer: NTM may be faster, but DTM can simulate (exponentially slower).

Summary

• Variants: Multi-tape, multi-head, 2D, NTM, enumerator, etc.
• All equivalent: Same computational power as standard TM
• Multi-tape: k tapes with k independent heads
• Simulation: Can reduce any variant to standard TM
• NTM = DTM: Non-determinism doesn’t add decidability power
• Enumerator ≡ TM: Generates all strings in language
• Time complexity: Variants may be faster (polynomially)
• Church-Turing thesis: All reasonable models equivalent
• Robustness: TM model very stable under modifications
• Key insight: Unlimited tape + read/write + bidirectional = ultimate power

Variants show TM model is robust and well-defined!