🧠 Introduction

🎯 Many Models, Same Power

There are many variants of Turing machines: multi-tape, nondeterministic, multi-head, and more. Remarkably, all these variants have the same computational power — they all recognize exactly the recursively enumerable languages. This robustness is strong evidence for the Church-Turing thesis.

Key insight: Changing the TM's features (tapes, heads, determinism) may affect speed but not power. This is why we can choose the most convenient variant for any proof or algorithm.

Why Variants Matter

Convenience: Easier proofs. Speed: Faster simulation. Robustness: Same power. Church-Turing: Evidence for thesis. Complexity: Different models for different classes. Practical: Choose the best tool.

📌 Same power📌 Different speed📌 Robustness📌 Convenience

# Turing Machine Variants — the big picture
print("""
=== The Amazing Fact ===

All reasonable variants of Turing machines
have the SAME computational power.

They all recognize exactly the
recursively enumerable languages.

This robustness is evidence for the
Church-Turing thesis.

=== Common Variants ===

1. MULTI-TAPE TM
   - k tapes, k heads
   - Easier to design
   - Faster (O(n) vs O(n²))

2. NONDETERMINISTIC TM (NTM)
   - Multiple choices
   - Accepts if any path accepts
   - Same power, exponential slowdown

3. TWO-WAY INFINITE TAPE
   - Tape infinite in both directions
   - Equivalent to one-way

4. MULTI-HEAD TM
   - Multiple heads on same tape
   - Can check multiple positions

5. OBLIVIOUS TM
   - Head movement depends only on input length
   - Used in circuit complexity

6. UNIVERSAL TM
   - Simulates any other TM
   - Foundation of programmable computers

7. ENUMERATOR
   - Outputs strings of a language
   - Equivalent to TM

8. RAM MACHINE
   - Random access memory
   - Closer to real computers

=== Why This Matters ===

For PROOFS:
  Choose the variant that's easiest.
  The result holds for all variants.

For ALGORITHMS:
  Choose the variant that's fastest.
  The power is the same.

For COMPLEXITY:
  Different variants give different classes.
  Multi-tape: better time complexity.

=== The Equivalence Principle ===

If variant V can simulate standard TM,
and standard TM can simulate V,
then V ≡ standard TM.

Most proofs use this principle.
""")

# ANALOGY
print("=== Analogy: Different Programming Languages ===")
print("""
Imagine you want to write a program.

You could use:
  - Python (convenient, slower)
  - C (fast, more work)
  - Assembly (fastest, most work)
  - Haskell (functional, different style)

All are Turing-complete.
All can compute the same functions.
But they differ in:
  - Ease of use
  - Speed
  - Style

TM variants are like programming languages:
  - Multi-tape: convenient
  - Single-tape: standard
  - NTM: parallel
  - Universal: interpreter

Choose the right tool for the job.
""")

# THE BIG PICTURE
print("""
=== The Big Picture ===

Standard TM (single-tape, deterministic)
  ↕ equivalent
Multi-tape TM
  ↕ equivalent
Nondeterministic TM
  ↕ equivalent
Multi-head TM
  ↕ equivalent
Universal TM
  ↕ equivalent
RAM Machine
  ↕ equivalent
Lambda Calculus
  ↕ equivalent
Modern Computers

All equivalent in power.
All recognize r.e. languages.
All are "Turing-complete."

=== What Changes ===

1. SPEED
   Multi-tape: faster (linear vs quadratic)
   NTM: slower to simulate (exponential)

2. CONVENIENCE
   Multi-tape: easier to design
   Universal: can simulate others

3. COMPLEXITY
   Different variants → different classes
   (P, NP, PSPACE, etc.)

4. NOT POWER
   All recognize the same languages.
   This is the key invariant.

=== Why This Is Important ===

1. CHURCH-TURING THESIS
   Many independent models → same power.
   Strong evidence for the thesis.

2. FLEXIBILITY
   Choose the best variant for each proof.
   Results transfer to all variants.

3. FOUNDATION
   Real computers are TM-equivalent.
   Theory applies to practice.

4. LIMITS
   Undecidability holds for ALL variants.
   No variant can solve the halting problem.
""")

# VARIANT OVERVIEW TABLE
print("=== Variant Overview ===")
print(f"{'Variant':<30} {'Power':<20} {'Speed':<20}")
print("-" * 70)
print(f"{'Single-tape TM':<30} {'Standard':<20} {'Baseline':<20}")
print(f"{'Multi-tape TM':<30} {'Same':<20} {'Faster O(n)':<20}")
print(f"{'Nondeterministic TM':<30} {'Same':<20} {'Exponential':<20}")
print(f"{'Two-way infinite':<30} {'Same':<20} {'Same':<20}")
print(f"{'Multi-head TM':<30} {'Same':<20} {'Faster':<20}")
print(f"{'Oblivious TM':<30} {'Same':<20} {'Slower':<20}")
print(f"{'Universal TM':<30} {'Same':<20} {'Simulates all':<20}")
print(f"{'Enumerator':<30} {'Same':<20} {'Outputs strings':<20}")
print(f"{'RAM Machine':<30} {'Same':<20} {'Practical':<20}")

print("""
=== Simulation Costs ===

When we say "equivalent," we mean:
  - Same set of recognizable languages
  - One can simulate the other
  - But simulation may have a cost

Typical costs:
  Single-tape simulates multi-tape: O(n²) slowdown
  Single-tape simulates NTM: exponential slowdown
  Multi-tape simulates single-tape: O(n) (trivial)
  
These costs matter for complexity theory,
but not for computability.
""")

📼 Multi-Tape TM

🎯 Multiple Tapes, One Machine

A multi-tape Turing machine has k tapes, each with its own read/write head, controlled by a single finite state control. Transitions read all k heads, write to all k tapes, and move all k heads simultaneously.

Multi-Tape Features

k tapes: Usually 2 or 3. k heads: One per tape. Read all: Transition reads all heads. Write all: Writes to all tapes. Move all: Moves all heads. Equivalent: Same power as single-tape. Faster: O(n) vs O(n²).

📼 k tapes👆 k heads🔄 Simultaneous⚡ Faster

# Multi-Tape Turing Machine
print("=" * 60)
print("MULTI-TAPE TURING MACHINE")
print("=" * 60)

print("""
=== Definition ===

A k-tape TM has:
  - k tapes (infinite in both directions)
  - k heads (one per tape)
  - One finite state control

Transition:
  δ: Q × Γ^k → Q × Γ^k × {L,R}^k

Reads all k heads, writes all k tapes,
moves all k heads.

=== Why Multi-Tape? ===

1. EASIER TO DESIGN
   - Separate input, work, output tapes
   - No need to encode everything on one tape

2. FASTER
   - Single-tape: O(n²) to simulate
   - Multi-tape: O(n) directly

3. CLOSER TO REAL COMPUTERS
   - CPU has registers, cache, RAM
   - Multiple storage areas

=== Power ===

Multi-tape TM ≡ Single-tape TM

Proof:
  (⇐) Trivial: single-tape is a special case.
  
  (⇒) Simulate k tapes on one tape:
    - Use 2k tracks
    - Track i: contents of tape i
    - Track i+1: head position marker
    - Simulate one step by scanning
    - Time: O(k × n) per step
    - Total: O(n²) for n steps

So multi-tape is faster but not more powerful.
""")

# MULTI-TAPE IN CODE
print("=== Multi-Tape TM Implementation ===")

class MultiTapeTM:
    """A k-tape Turing machine."""
    def __init__(self, k, transitions, q0, q_accept, q_reject, blank='_'):
        self.k = k
        self.delta = transitions
        # transitions: (state, sym1, ..., symk) -> (next_state, write1, ..., writek, dir1, ..., dirk)
        self.q0 = q0
        self.q_accept = q_accept
        self.q_reject = q_reject
        self.blank = blank
    
    def run(self, input_string, max_steps=10000, verbose=False):
        """Run multi-tape TM."""
        # Initialize tapes
        tapes = [list(input_string) + [self.blank] * 100]  # tape 0: input
        for _ in range(1, self.k):
            tapes.append([self.blank] * 100)
        
        heads = [0] * self.k
        state = self.q0
        steps = 0
        
        if verbose:
            print(f"  Initial: state={state}")
            for i in range(self.k):
                print(f"    Tape {i}: {''.join(tapes[i][:20])}")
        
        while steps < max_steps:
            if state == self.q_accept:
                return True, steps, tapes
            if state == self.q_reject:
                return False, steps, tapes
            
            # Read all heads
            symbols = tuple(
                tapes[i][heads[i]] if heads[i] < len(tapes[i]) else self.blank
                for i in range(self.k)
            )
            
            key = (state,) + symbols
            if key not in self.delta:
                return False, steps, tapes
            
            result = self.delta[key]
            next_state = result[0]
            writes = result[1:1+self.k]
            directions = result[1+self.k:1+2*self.k]
            
            # Write and move
            for i in range(self.k):
                # Extend tape if needed
                if heads[i] >= len(tapes[i]):
                    tapes[i].extend([self.blank] * 100)
                tapes[i][heads[i]] = writes[i]
                
                if directions[i] == 'R':
                    heads[i] += 1
                elif directions[i] == 'L':
                    heads[i] = max(0, heads[i] - 1)
            
            state = next_state
            steps += 1
            
            if verbose and steps <= 15:
                print(f"  Step {steps}: state={state}")
                for i in range(self.k):
                    tape_str = ''.join(tapes[i][:20])
                    head_marker = ' ' * heads[i] + '^'
                    print(f"    Tape {i}: {tape_str}")
                    print(f"            {head_marker}")
        
        return False, steps, tapes


# Example: Copy input to tape 1
print("Multi-tape TM: Copy input")
print("""
Transitions:
  (q0, 0, _) → (q0, 0, 0, R, R)
  (q0, 1, _) → (q0, 1, 1, R, R)
  (q0, _, _) → (q_accept, _, _, L, L)
""")

copy_tm = MultiTapeTM(
    k=2,
    transitions={
        ('q0', '0', '_'): ('q0', '0', '0', 'R', 'R'),
        ('q0', '1', '_'): ('q0', '1', '1', 'R', 'R'),
        ('q0', '_', '_'): ('q_accept', '_', '_', 'L', 'L'),
    },
    q0='q0',
    q_accept='q_accept',
    q_reject='q_reject'
)

for s in ['', '0', '101', '1101']:
    accepted, steps, tapes = copy_tm.run(s)
    tape0 = ''.join(tapes[0]).rstrip('_')
    tape1 = ''.join(tapes[1]).rstrip('_')
    print(f"  Input: '{s}' → Tape0='{tape0}', Tape1='{tape1}' ({steps} steps)")

# MULTI-TAPE FOR A^N B^N C^N
print("\n=== Multi-Tape TM for a^n b^n c^n ===")
print("""
With 2 tapes, this is much easier:

Tape 0: input (read-only)
Tape 1: work tape

Strategy:
  1. Copy a's to tape 1
  2. Match b's with a's on tape 1
  3. Match c's with... wait, we need more.

Better with 3 tapes:
  Tape 0: input
  Tape 1: a's count
  Tape 2: b's count

Strategy:
  1. Copy a's to tape 1
  2. Copy b's to tape 2
  3. Check all three counts are equal

Actually, the standard 2-tape approach:
  1. For each 'a', mark it and write A on tape 1
  2. For each 'b', mark it and write B on tape 1
  3. For each 'c', mark it and match against tape 1

Hmm, still complex. Let's use 3 tapes.
""")

# MULTI-TAPE ADVANTAGE
print("=== Multi-Tape Advantage ===")
print("""
Single-tape TM for a^n b^n c^n:
  - Needs to go back and forth
  - O(n²) time

Multi-tape TM:
  - Can process in parallel
  - O(n) time

Example: Checking a^n b^n c^n

Single-tape:
  1. Mark first a
  2. Scan right to find first b
  3. Mark it
  4. Scan right to find first c
  5. Mark it
  6. Scan left to find next a
  7. Repeat
  Time: O(n²)

Multi-tape:
  Tape 0: input
  Tape 1: work
  
  1. Copy a's to tape 1
  2. Match b's with tape 1
  3. Match c's with... 
  
  Actually, even multi-tape needs care.
  
  Better: Use tape 1 for a's, tape 2 for b's.
  Then compare counts.
  Time: O(n)
""")

# SIMULATION OF MULTI-TAPE ON SINGLE-TAPE
print("=== Simulating Multi-Tape on Single-Tape ===")
print("""
Encoding:
  - Use 2k tracks
  - Track 2i: contents of tape i
  - Track 2i+1: head position marker

Example: 2 tapes
  
  Track 0: contents of tape 0
  Track 1: head position for tape 0
  Track 2: contents of tape 1
  Track 3: head position for tape 1

Visual:
  ┌───┬───┬───┬───┬───┐
  │ a │ b │ c │ _ │ _ │  ← tape 0
  ├───┼───┼───┼───┼───┤
  │   │ ↑ │   │   │   │  ← head 0
  ├───┼───┼───┼───┼───┤
  │ X │ Y │ _ │ _ │ _ │  ← tape 1
  ├───┼───┼───┼───┼───┤
  │   │   │ ↑ │   │   │  ← head 1
  └───┴───┴───┴───┴───┘

Simulation:
  1. Scan right to find all head markers
  2. Read symbols at head positions
  3. Determine transition
  4. Scan back, update tapes and heads
  5. Repeat

Time: O(k × n) per step
      O(k × n²) total

So single-tape simulates multi-tape
with quadratic slowdown.
""")

# MULTI-TAPE IN PRACTICE
print("""
=== Multi-Tape in Practice ===

Real computers are multi-tape-like:
  - Registers (fast, small)
  - Cache (medium)
  - RAM (large, slower)
  - Disk (huge, slow)

Multi-tape TMs model:
  - Multiple storage levels
  - Parallel access
  - Pipelining

Complexity theory:
  - Multi-tape TMs define time complexity
  - Single-tape gives same classes (up to polynomial)
  - Multi-tape is standard for complexity

Key insight:
  Multi-tape is the "natural" model
  for algorithm analysis.
""")

🔀 Nondeterministic TM

🎯 Multiple Choices, Same Power

A nondeterministic Turing machine (NTM) can have multiple possible transitions for the same configuration. It accepts if any computation path accepts. NTMs have the same power as deterministic TMs but are central to complexity theory (P vs NP).

NTM Features

Multiple transitions: δ: Q × Γ → P(Q × Γ × {L,R}). Computation tree: Branches at each step. Acceptance: Any path accepts. Simulation: BFS on tree, exponential. Power: Same as DTM. Complexity: NP, NL, etc.

🔀 Multiple🌳 Tree✅ Any path⏱️ Exponential

# Nondeterministic Turing Machine
print("=" * 60)
print("NONDETERMINISTIC TURING MACHINE (NTM)")
print("=" * 60)

print("""
=== Definition ===

An NTM has transition function:
  δ: Q × Γ → P(Q × Γ × {L,R})

Multiple possible moves for each configuration.

Acceptance:
  Accept if ANY computation path accepts.

=== Computation Tree ===

An NTM computation is a TREE:
  - Root: initial configuration
  - Children: all possible next configurations
  - Leaves: accept, reject, or infinite

Accept if ANY leaf is accepting.

=== Power ===

NTM ≡ TM (same power!)

Proof (NTM → TM):
  Simulate NTM on a TM using BFS:
    1. Explore all computation paths
    2. Level by level (BFS)
    3. Accept if any path accepts
    
  Time: exponential in worst case.
  
Proof (TM → NTM):
  Trivial: a TM is a special case of an NTM
  (one choice per configuration).

=== Why NTMs Matter ===

1. COMPLEXITY THEORY
   P = problems solvable by DTM in poly time
   NP = problems solvable by NTM in poly time
   
   P vs NP is the central open problem.

2. PROOF TECHNIQUES
   NTMs are easier to design for some problems.
   (e.g., SAT, graph problems)

3. THEORETICAL TOOL
   NTMs help classify problem difficulty.
""")

# NTM IN CODE
print("=== NTM Implementation ===")

from collections import deque

class NTM:
    """Nondeterministic Turing Machine."""
    def __init__(self, transitions, q0, q_accept, q_reject, blank='_'):
        # transitions: (state, symbol) -> list of (next_state, write, direction)
        self.delta = transitions
        self.q0 = q0
        self.q_accept = q_accept
        self.q_reject = q_reject
        self.blank = blank
    
    def accepts(self, input_string, max_depth=100, max_configs=100000):
        """BFS simulation. Returns True if any path accepts."""
        from collections import deque
        
        # Configuration: (state, tape_tuple, head)
        initial_tape = tuple(input_string + self.blank * 20)
        initial = (self.q0, initial_tape, 0)
        
        queue = deque([(initial, 0)])
        visited = set()
        configs_explored = 0
        
        while queue and configs_explored < max_configs:
            (state, tape, head), depth = queue.popleft()
            configs_explored += 1
            
            if state == self.q_accept:
                return True, configs_explored
            if state == self.q_reject:
                continue
            if depth > max_depth:
                continue
            
            key = (state, tape, head)
            if key in visited:
                continue
            visited.add(key)
            
            symbol = tape[head] if head < len(tape) else self.blank
            
            # Try all transitions
            for (next_state, write, direction) in self.delta.get((state, symbol), []):
                new_tape = list(tape)
                if head >= len(new_tape):
                    new_tape.extend([self.blank] * 10)
                new_tape[head] = write
                
                if direction == 'R':
                    new_head = head + 1
                else:
                    new_head = max(0, head - 1)
                
                queue.append(((next_state, tuple(new_tape), new_head), depth + 1))
        
        return False, configs_explored


# Example: NTM for palindromes
print("NTM for palindromes:")
print("  Non-deterministically guess the middle, then match.")

ntm_palindrome = NTM(
    transitions={
        # Read leftmost, guess middle
        ('q0', 'a'): [('q1', 'a', 'R'), ('q2', 'a', 'R')],
        ('q0', 'b'): [('q1', 'b', 'R'), ('q2', 'b', 'R')],
        ('q0', '_'): [('q_accept', '_', 'R')],  # empty
        
        # Go to right end (not guessed yet)
        ('q1', 'a'): [('q1', 'a', 'R')],
        ('q1', 'b'): [('q1', 'b', 'R')],
        ('q1', '_'): [('q3', '_', 'L')],
        
        # Guessed middle: go to right end and match
        ('q2', 'a'): [('q2', 'a', 'R')],
        ('q2', 'b'): [('q2', 'b', 'R')],
        ('q2', '_'): [('q4', '_', 'L')],
        
        # Match from right
        ('q3', 'a'): [('q5', 'X', 'L')],  # match 'a'
        ('q3', 'b'): [('q6', 'X', 'L')],  # match 'b'
        ('q3', 'X'): [('q3', 'X', 'L')],
        ('q3', '_'): [('q_accept', '_', 'R')],  # all matched
        
        ('q4', 'a'): [('q5', 'X', 'L')],  # match 'a' (middle)
        ('q4', 'b'): [('q6', 'X', 'L')],
        ('q4', 'X'): [('q4', 'X', 'L')],
        ('q4', '_'): [('q_accept', '_', 'R')],
        
        # Continue matching
        ('q5', 'a'): [('q7', 'X', 'L')],
        ('q5', 'b'): [('q_accept', 'b', 'R')],  # mismatch? no
        ('q5', 'X'): [('q5', 'X', 'L')],
        
        ('q6', 'b'): [('q7', 'X', 'L')],
        ('q6', 'a'): [('q_accept', 'a', 'R')],
        ('q6', 'X'): [('q6', 'X', 'L')],
        
        # Go back to left
        ('q7', 'a'): [('q7', 'a', 'L')],
        ('q7', 'b'): [('q7', 'b', 'L')],
        ('q7', 'X'): [('q7', 'X', 'L')],
        ('q7', '_'): [('q0', '_', 'R')],
    },
    q0='q0',
    q_accept='q_accept',
    q_reject='q_reject'
)

print("\nTesting NTM for palindromes:")
for s in ['', 'a', 'aa', 'aba', 'abba', 'ababa', 'ab', 'aab', 'abab']:
    accepted, configs = ntm_palindrome.accepts(s, max_depth=50)
    result = "✓ ACCEPT" if accepted else "✗ REJECT"
    print(f"  '{s}' → {result} ({configs} configs explored)")

# NTM ADVANTAGE
print("""
=== NTM Advantage: Guessing ===

NTMs are good at "guessing" the right path.

Example: Palindromes
  - DTM: must know the middle
  - NTM: guess the middle, verify

Example: SAT (Boolean satisfiability)
  - DTM: try all assignments (exponential)
  - NTM: guess an assignment, verify (polynomial)

Example: Hamiltonian Path
  - DTM: try all permutations
  - NTM: guess a permutation, verify

=== The Pattern ===

NTM = "guess and verify"

For many problems:
  - Guessing is easy (nondeterministic)
  - Verification is easy (deterministic)
  - But finding the right guess is hard

This is the essence of NP.

=== Why NTM = DTM ===

Any NTM can be simulated by a DTM:
  - Use BFS on the computation tree
  - Try all possible guesses
  - Exponential slowdown

So NTM doesn't add power,
just convenience.
""")

# NTM FOR SAT
print("=== NTM for SAT ===")
print("""
SAT: Given a boolean formula, is there a satisfying assignment?

NTM algorithm:
  1. Guess an assignment (nondeterministic)
  2. Verify the assignment (deterministic)
  3. Accept if satisfied

Example: (x1 ∨ ¬x2) ∧ (¬x1 ∨ x3) ∧ (x2 ∨ ¬x3)

Step 1: Guess x1=T, x2=F, x3=T
Step 2: Check:
  (T ∨ T) = T ✓
  (F ∨ T) = T ✓
  (F ∨ F) = F ✗
  Not satisfied.

Step 1: Guess x1=T, x2=F, x3=F
Step 2: Check:
  (T ∨ T) = T ✓
  (F ∨ F) = F ✗
  Not satisfied.

Try all guesses. If any works, accept.

NTM explores all guesses in parallel.
DTM must try them one by one.

Time:
  NTM: O(n) to guess + O(m) to verify
  DTM: O(2^n) to try all assignments

This is why SAT is in NP (NTM poly time)
but not known to be in P (DTM poly time).
""")

# NTM AND COMPLEXITY
print("""
=== NTM and Complexity ===

NTMs define complexity classes:

NTIME(f(n)): Problems solvable by NTM in O(f(n)) time
NSPACE(f(n)): Problems solvable by NTM in O(f(n)) space

Key classes:
  NP = NTIME(n^k) for some k
  NL = NSPACE(log n)
  NPSPACE = NSPACE(n^k)

Relationships:
  P ⊆ NP ⊆ PSPACE
  NL ⊆ P
  NP ⊆ NPSPACE = PSPACE (Savitch)

Open problems:
  P = NP?
  NP = PSPACE?
  L = NL?

These are central to complexity theory.
""")

# NTM SIMULATION COST
print("""
=== NTM Simulation Cost ===

Simulating NTM on DTM:
  - BFS on computation tree
  - Tree may have exponential nodes
  - Time: O(b^d) where b = branching, d = depth

For polynomial time NTM:
  - Depth: poly(n)
  - Branching: constant (bounded by |δ|)
  - Total: exponential

Example:
  SAT: NTM takes O(n) time
       DTM takes O(2^n) time
  
  Is there a faster DTM?
  That's the P vs NP question!

=== Non-Determinism in Practice ===

Nondeterminism is:
  - A theoretical tool
  - Not directly implementable
  - But useful for:
    * Defining NP
    * Designing algorithms
    * Proving hardness

To implement NTM:
  - Use backtracking
  - Try all paths
  - May be exponential

This is why NP-hard problems are hard:
  - We believe no efficient DTM exists
  - (But can't prove it!)
""")

↔️ Two-Way Infinite Tape

🎯 Infinite in Both Directions

A two-way infinite tape TM has a tape that extends infinitely in both directions (left and right). This is equivalent to the standard one-way infinite tape — the direction of infinity doesn't affect computational power.

Two-Way vs One-Way

Two-way: Tape infinite in both directions. One-way: Tape infinite in one direction. Equivalent: Same power. Simulation: Two-way → one-way with folding. Convenience: Two-way is more intuitive. Standard: Most textbooks use one-way.

↔️ Two-way➡️ One-way↔️ Equivalent🔢 Folding

# Two-Way Infinite Tape
print("=" * 60)
print("TWO-WAY INFINITE TAPE")
print("=" * 60)

print("""
=== Definitions ===

ONE-WAY INFINITE TAPE:
  Tape extends infinitely to the RIGHT.
  Cells: 0, 1, 2, 3, ...
  Head can move right forever, left only to 0.

TWO-WAY INFINITE TAPE:
  Tape extends infinitely in BOTH directions.
  Cells: ..., -2, -1, 0, 1, 2, ...
  Head can move left or right forever.

=== Equivalence ===

Two-way ≡ One-way

Proof (Two-way → One-way):
  Use a one-way tape with 2 tracks:
    - Track 0: cells 0, 1, 2, ... (right half)
    - Track 1: cells -1, -2, -3, ... (left half)
  
  Special marker for "origin" (cell 0).
  
  Simulation:
    - Moving right: move right on one-way tape
    - Moving left: move right on one-way tape,
      but switch tracks (right half ↔ left half)
  
  This simulates two-way on one-way.

Proof (One-way → Two-way):
  Trivial: one-way is a special case.
  
Therefore, equivalent.

=== Why It Doesn't Matter ===

The direction of infinity is not important.
What matters is:
  - Infinite storage
  - Read/write access
  - Movement in both directions

Both models have these.
So they're equivalent.
""")

# SIMULATION IN CODE
print("=== Simulating Two-Way on One-Way ===")
print("""
Encoding:
  - Use a one-way tape with 2 tracks
  - Track 0: right half (positions 0, 1, 2, ...)
  - Track 1: left half (positions -1, -2, -3, ...)
  - Special marker at position 0

Visual:
  Position:  0    1    2    3    4   ...
  Track 0: [origin] a    b    c    _   ...
  Track 1: [origin] X    Y    Z    _   ...
  
  Cell 0 represents:
    - Right half at position 0
    - Left half at position -1
  (with a special marker)

Moving:
  - In two-way, moving right from 0 → 1:
    In one-way, move right on track 0.
  - In two-way, moving left from 0 → -1:
    In one-way, move right on track 1.
  - In two-way, moving right from -1 → 0:
    In one-way, move left on track 1.
  - In two-way, moving left from 1 → 0:
    In one-way, move left on track 0.

The encoding preserves the computation.
""")

# TWO-WAY IN CODE
print("=== Two-Way TM Implementation ===")

class TwoWayTM:
    """Turing machine with two-way infinite tape."""
    def __init__(self, transitions, q0, q_accept, q_reject, blank='_'):
        self.delta = transitions
        self.q0 = q0
        self.q_accept = q_accept
        self.q_reject = q_reject
        self.blank = blank
    
    def run(self, input_string, max_steps=1000, verbose=False):
        """Run TM with two-way tape."""
        # Use dictionary for infinite tape
        tape = {}
        for i, ch in enumerate(input_string):
            tape[i] = ch
        
        head = 0
        state = self.q0
        steps = 0
        
        if verbose:
            print(f"  Initial: state={state}, tape={self._show(tape, head)}")
        
        while steps < max_steps:
            if state == self.q_accept:
                return True, steps, tape
            if state == self.q_reject:
                return False, steps, tape
            
            symbol = tape.get(head, self.blank)
            
            if (state, symbol) not in self.delta:
                return False, steps, tape
            
            next_state, write, direction = self.delta[(state, symbol)]
            tape[head] = write
            
            if direction == 'R':
                head += 1
            else:  # 'L'
                head -= 1
            
            state = next_state
            steps += 1
            
            if verbose and steps <= 20:
                print(f"  Step {steps}: state={state}, tape={self._show(tape, head)}")
        
        return False, steps, tape
    
    def _show(self, tape, head):
        """Show tape with head marker."""
        if not tape:
            return f"[{self.blank}]"
        min_pos = min(min(tape.keys()), head)
        max_pos = max(max(tape.keys()), head)
        result = []
        for i in range(min_pos, max_pos + 1):
            if i == head:
                result.append(f"[{tape.get(i, self.blank)}]")
            else:
                result.append(tape.get(i, self.blank))
        return ' '.join(result)


# Example: TM that moves left forever
print("Two-way TM demonstration:")
print("  TM that moves left (into negative positions)")

left_tm = TwoWayTM(
    transitions={
        ('q0', '_'): ('q0', '_', 'L'),
    },
    q0='q0',
    q_accept='q_accept',
    q_reject='q_reject'
)

accepted, steps, tape = left_tm.run('abc', max_steps=10, verbose=True)
print(f"\n  After 10 steps: {left_tm._show(tape, -10)}")

# TWO-WAY ADVANTAGE
print("""
=== Two-Way Advantage ===

Two-way tape is more INTUITIVE:
  - Like a real tape/string
  - Can move left or right freely
  - No special case for "left end"

Two-way tape is easier for:
  - Palindrome recognition
  - Reversal operations
  - Bidirectional scanning

One-way tape is:
  - Simpler to define formally
  - Easier to implement
  - Standard in most textbooks

Both are equivalent, so use whichever is convenient.
""")

# FORMAL EQUIVALENCE
print("""
=== Formal Equivalence Proof ===

Theorem: Two-way TM ≡ One-way TM

Proof (Two-way → One-way):
  Given two-way TM M, construct one-way TM M':
  
  Encoding:
    - M' has a 2-track tape
    - Track 0: cells 0, 1, 2, ... of M
    - Track 1: cells -1, -2, -3, ... of M
    - Special marker at cell 0
  
  Simulation:
    - M' maintains a "virtual head" position
    - Moving right: update track 0
    - Moving left: update track 1 (in reverse)
    - Special handling at position 0
  
  Time: O(n) per step of M
  Space: O(n) for tape
  
  M' accepts iff M accepts.

Proof (One-way → Two-way):
  One-way tape is a special case of two-way.
  (Just never move left of 0.)
  
Therefore, equivalent. ∎

=== Why This Matters ===

1. FLEXIBILITY
   Choose the model that's easiest.

2. ROBUSTNESS
   Direction of infinity doesn't matter.

3. CHURCH-TURING
   More evidence for the thesis.
""")

👆 Multi-Head TM

🎯 Multiple Heads, One Tape

A multi-head Turing machine has multiple read/write heads on the same tape. Each head can move independently. Transitions read all heads, write at all heads, and move all heads.

Multi-Head Features

k heads: On the same tape. Independent: Heads move separately. Read all: Transition sees all heads. Write all: Can write at all heads. Equivalent: Same power as single-head. Speedup: Can be faster.

👆 k heads📼 One tape🔄 Independent⚡ Speedup

# Multi-Head Turing Machine
print("=" * 60)
print("MULTI-HEAD TURING MACHINE")
print("=" * 60)

print("""
=== Definition ===

A k-head TM has:
  - ONE tape
  - k read/write heads
  - One finite state control

Transition:
  δ: Q × Γ^k → Q × Γ^k × {L,R}^k

Reads all k heads, writes at all k positions,
moves all k heads.

=== Why Multi-Head? ===

1. FASTER
   - Check multiple positions at once
   - Parallel scanning

2. CONVENIENT
   - Some algorithms are easier
   - Pattern matching

3. THEORETICAL
   - Used in circuit complexity
   - Related to parallel computation

=== Power ===

Multi-head TM ≡ Single-head TM

Proof:
  Simulate k heads with k markers:
    - Each head has a unique marker
    - Scan tape to find all heads
    - Apply transition
    - Update markers
  
  Time: O(k × n) per step
  Space: O(n) for tape + markers
  
  So multi-head is faster but not more powerful.
""")

# MULTI-HEAD IN CODE
print("=== Multi-Head TM Implementation ===")

class MultiHeadTM:
    """A TM with k heads on one tape."""
    def __init__(self, k, transitions, q0, q_accept, q_reject, blank='_'):
        self.k = k
        self.delta = transitions
        # transitions: (state, sym1, ..., symk) -> (next_state, write1, ..., writek, dir1, ..., dirk)
        self.q0 = q0
        self.q_accept = q_accept
        self.q_reject = q_reject
        self.blank = blank
    
    def run(self, input_string, max_steps=1000, verbose=False):
        """Run multi-head TM."""
        tape = list(input_string) + [self.blank] * 100
        heads = [0] * self.k  # all heads start at 0
        state = self.q0
        steps = 0
        
        if verbose:
            print(f"  Initial: state={state}, heads={heads}")
            print(f"    {self._show(tape, heads)}")
        
        while steps < max_steps:
            if state == self.q_accept:
                return True, steps, tape, heads
            if state == self.q_reject:
                return False, steps, tape, heads
            
            # Read all heads
            symbols = tuple(tape[h] if h < len(tape) else self.blank for h in heads)
            
            key = (state,) + symbols
            if key not in self.delta:
                return False, steps, tape, heads
            
            result = self.delta[key]
            next_state = result[0]
            writes = result[1:1+self.k]
            directions = result[1+self.k:1+2*self.k]
            
            # Write and move
            for i in range(self.k):
                if heads[i] >= len(tape):
                    tape.extend([self.blank] * 100)
                tape[heads[i]] = writes[i]
                
                if directions[i] == 'R':
                    heads[i] += 1
                elif directions[i] == 'L':
                    heads[i] = max(0, heads[i] - 1)
            
            state = next_state
            steps += 1
            
            if verbose and steps <= 15:
                print(f"  Step {steps}: state={state}, heads={heads}")
                print(f"    {self._show(tape, heads)}")
        
        return False, steps, tape, heads
    
    def _show(self, tape, heads):
        """Show tape with head markers."""
        result = []
        for i, ch in enumerate(tape[:30]):
            if i in heads:
                result.append(f"[{ch}]")
            else:
                result.append(ch)
        return ' '.join(result)


# Example: 2-head TM for palindrome
print("2-head TM for palindrome check:")
print("""
Strategy:
  Head 0 starts at left
  Head 1 starts at right end
  
  1. Move head 1 to right end
  2. Compare head 0 and head 1
  3. Move head 0 right, head 1 left
  4. Repeat until they meet
""")

# First, move head 1 to end
# Then compare
palindrome_2head = MultiHeadTM(
    k=2,
    transitions={
        # Phase 1: move head 1 to end
        ('q0', 'a', 'a'): ('q0', 'a', 'a', 'L', 'R'),
        ('q0', 'a', 'b'): ('q0', 'a', 'b', 'L', 'R'),
        ('q0', 'b', 'a'): ('q0', 'b', 'a', 'L', 'R'),
        ('q0', 'b', 'b'): ('q0', 'b', 'b', 'L', 'R'),
        ('q0', 'a', '_'): ('q1', 'a', '_', 'R', 'L'),
        ('q0', 'b', '_'): ('q1', 'b', '_', 'R', 'L'),
        ('q0', '_', '_'): ('q_accept', '_', '_', 'R', 'L'),
        
        # Phase 2: compare
        ('q1', 'a', 'a'): ('q1', 'a', 'a', 'R', 'L'),
        ('q1', 'b', 'b'): ('q1', 'b', 'b', 'R', 'L'),
        ('q1', 'a', 'b'): ('q_reject', 'a', 'b', 'R', 'L'),
        ('q1', 'b', 'a'): ('q_reject', 'b', 'a', 'R', 'L'),
        ('q1', 'a', '_'): ('q_accept', 'a', '_', 'R', 'L'),
        ('q1', 'b', '_'): ('q_accept', 'b', '_', 'R', 'L'),
        ('q1', '_', '_'): ('q_accept', '_', '_', 'R', 'L'),
    },
    q0='q0',
    q_accept='q_accept',
    q_reject='q_reject'
)

print("\nTesting 2-head palindrome TM:")
for s in ['', 'a', 'aa', 'aba', 'abba', 'ababa', 'ab', 'aab', 'abab']:
    accepted, steps, tape, heads = palindrome_2head.run(s, max_steps=100)
    result = "✓ ACCEPT" if accepted else "✗ REJECT"
    print(f"  '{s}' → {result} ({steps} steps)")

# MULTI-HEAD ADVANTAGE
print("""
=== Multi-Head Advantage ===

Palindrome check:

Single-head TM:
  - Move to right end, mark last symbol
  - Move back to left, mark first symbol
  - Compare
  - Repeat
  Time: O(n²)

2-head TM:
  - Head 1 goes to right end (O(n))
  - Heads move toward each other, comparing (O(n))
  Time: O(n)

So multi-head can be FASTER.

=== Multi-Head in Complexity ===

k-head TMs are used in:
  - Circuit complexity
  - Parallel computation
  - Space complexity

Key result:
  k-head TM can be simulated by
  single-head TM with O(n²) slowdown.

So multi-head gives at most quadratic speedup.
Still same power.
""")

# MULTI-HEAD SIMULATION
print("""
=== Simulating Multi-Head on Single-Head ===

Encoding:
  - Use k markers on the tape
  - Each marker represents one head
  - Marker i is unique (different symbol)

Visual:
  Tape: a b c d e f g h
  Head 0 at position 2 (marker X0)
  Head 1 at position 5 (marker X1)
  
  Encoded: a b [X0]c d e [X1]f g h
  
  Or use subscripted symbols:
  a b c_{X0} d e f_{X1} g h

Simulation:
  1. Scan right to find all markers
  2. Read symbols under markers
  3. Determine transition
  4. Scan back, update markers and symbols
  5. Repeat

Time: O(k × n) per step
Total: O(k × n²)

So multi-head is faster but equivalent.
""")

# MULTI-HEAD IN PRACTICE
print("""
=== Multi-Head in Practice ===

Real-world analogy:
  - Multiple fingers on a page
  - Multiple cursors in an editor
  - Multiple read heads on a disk

Used in:
  - Pattern matching
  - String algorithms
  - Parallel computation models

Theoretical importance:
  - Circuit depth and multi-head TMs
  - Parallel time complexity
  - Space-time tradeoffs

Key insight:
  Multiple heads give speedup,
  but not more computational power.
""")

🎯 Oblivious TM

🎯 Head Movement Independent of Input

An oblivious Turing machine has head movements that depend only on the input length, not on the input content. The sequence of head positions is fixed for all inputs of the same length.

Oblivious TM Features

Fixed movements: Head path depends on n only. Same for all inputs: Length n → same path. Equivalent: Same power as standard TM. Slower: May need more steps. Circuit complexity: Key tool. Parallel: Related to parallel computation.

🎯 Fixed path📏 Length-dependent🔌 Circuits⚡ Parallel

# Oblivious Turing Machine
print("=" * 60)
print("OBLIVIOUS TURING MACHINE")
print("=" * 60)

print("""
=== Definition ===

An oblivious TM is a TM where:
  - Head movement depends only on input length n
  - Not on input content
  
For all inputs of length n:
  - Same sequence of head positions
  - Same sequence of states
  - Only written symbols may differ

=== Visual ===

Input length 3:
  Input "abc": head path = 0, 1, 2, 1, 0, ...
  Input "xyz": head path = 0, 1, 2, 1, 0, ...
  Same path!

Input length 4:
  Input "abcd": head path = 0, 1, 2, 3, 2, 1, ...
  Different path (but same for all length-4 inputs).

=== Power ===

Oblivious TM ≡ Standard TM

Proof:
  Standard TM can simulate oblivious TM (trivial).
  
  Oblivious TM can simulate standard TM:
    - Use a "simulation" strategy
    - Make head movements oblivious
    - May require more steps
    - But same power

=== Why Oblivious TMs Matter ===

1. CIRCUIT COMPLEXITY
   An oblivious TM corresponds to a circuit:
     - Each step: one layer of gates
     - Time = circuit depth
     - Space = circuit width
   
   This is a key tool in complexity theory.

2. PARALLEL COMPUTATION
   Oblivious TMs are related to:
     - Parallel random access machines (PRAM)
     - Boolean circuits
     - Parallel time complexity

3. P-COMPLETENESS
   Oblivious TMs are used to define:
     - P-complete problems
     - Problems hard to parallelize
""")

# OBLIVIOUS TM IN CODE
print("=== Oblivious TM Implementation ===")

class ObliviousTM:
    """
    An oblivious TM.
    Head movement depends only on input length.
    We implement this by storing a fixed head path.
    """
    def __init__(self, n, transitions, q0, q_accept, q_reject, blank='_'):
        self.n = n
        self.delta = transitions
        self.q0 = q0
        self.q_accept = q_accept
        self.q_reject = q_reject
        self.blank = blank
        # Generate oblivious head path based on n
        self.head_path = self._generate_path(n)
    
    def _generate_path(self, n):
        """Generate a fixed head path for length n."""
        # Simple path: go right to end, go left to start, repeat
        path = []
        for cycle in range(10):  # 10 cycles
            for i in range(n):
                path.append(i)
            for i in range(n-1, -1, -1):
                path.append(i)
        return path
    
    def run(self, input_string, max_steps=1000, verbose=False):
        """Run oblivious TM."""
        if len(input_string) != self.n:
            raise ValueError(f"Input must have length {self.n}")
        
        tape = list(input_string) + [self.blank] * 100
        state = self.q0
        steps = 0
        
        if verbose:
            print(f"  Head path: {self.head_path[:20]}...")
        
        for step in range(min(max_steps, len(self.head_path))):
            if state == self.q_accept:
                return True, steps, tape
            if state == self.q_reject:
                return False, steps, tape
            
            head = self.head_path[step]
            symbol = tape[head]
            
            if (state, symbol) not in self.delta:
                return False, steps, tape
            
            next_state, write, direction = self.delta[(state, symbol)]
            tape[head] = write
            state = next_state
            steps += 1
            
            if verbose and steps <= 20:
                print(f"  Step {steps}: head={head}, state={state}, symbol={symbol}")
        
        return False, steps, tape


# Example: Oblivious TM for palindrome
print("Oblivious TM for palindrome (n=4):")
print("  Head path is fixed for all length-4 inputs.")

# Simplified: just read the input in order
obl_tm = ObliviousTM(
    n=4,
    transitions={
        ('q0', 'a'): ('q0', 'a', 'R'),
        ('q0', 'b'): ('q0', 'b', 'R'),
        ('q0', '_'): ('q_accept', '_', 'R'),
    },
    q0='q0',
    q_accept='q_accept',
    q_reject='q_reject'
)

print("\nTesting oblivious TM:")
for s in ['aaaa', 'abab', 'abcd', 'bbbb']:
    accepted, steps, tape = obl_tm.run(s, verbose=False)
    print(f"  '{s}' → {'✓' if accepted else '✗'} ({steps} steps)")

# CIRCUIT CONNECTION
print("""
=== Oblivious TM and Circuits ===

An oblivious TM with:
  - Time T(n)
  - Space S(n)

Corresponds to a circuit with:
  - Depth O(T(n))
  - Width O(S(n))
  - Size O(T(n) × S(n))

Construction:
  - Layer i = step i of TM
  - Each cell = one tape position
  - Gates compute transition function

Visual:
  Time →
  ┌───┬───┬───┬───┐
  │ q │   │   │   │  ← state
  ├───┼───┼───┼───┤
  │ a │ b │ c │ _ │  ← tape at step 0
  ├───┼───┼───┼───┤
  │ a │ b │ c │ _ │  ← tape at step 1
  ├───┼───┼───┼───┤
  │ a │ b │ c │ _ │  ← tape at step 2
  ├───┼───┼───┼───┤
  │...│...│...│...│
  └───┴───┴───┴───┘

This correspondence is used to prove:
  - P ⊆ P/poly (polynomial circuits)
  - P-complete problems
  - Parallel computation limits
""")

# P-COMPLETENESS
print("""
=== P-Completeness ===

A problem is P-COMPLETE if:
  1. It's in P
  2. Every problem in P reduces to it in log space

P-complete problems are:
  - Solvable in polynomial time
  - But probably NOT parallelizable

Examples:
  - Circuit Value Problem (CVP)
  - Linear programming
  - Lexicographically first DFS
  - Monotone circuit value

Connection to oblivious TMs:
  - Oblivious TMs are inherently sequential
  - P-complete problems are hard to parallelize
  - Oblivious TMs help prove P-completeness

=== Why It Matters ===

If P ≠ NC (Nick's Class, parallel poly time):
  - Some P problems can't be parallelized
  - P-complete problems are the hardest
  - This is a major open problem

Oblivious TMs are a key tool
in this area.
""")

# OBLIVIOUS TM SIMULATION
print("""
=== Simulating Standard TM by Oblivious TM ===

Given standard TM M, construct oblivious TM M':

Idea:
  M' simulates M step by step, but:
    - M' has a fixed head path
    - M' stores M's head position in its state
    - M' moves its head obliviously
    - M' reads/writes at M's head position when it passes by

Construction:
  1. M' has a "simulation" tape
  2. M' stores M's state and head position
  3. M' scans left-to-right, then right-to-left
  4. When M' passes M's head position, it reads/writes
  5. M' updates M's state and head position

Time: O(T(n) × S(n))
  where T(n) = M's time, S(n) = M's space

So oblivious TM may be slower,
but has the same power.
""")

# SUMMARY
print("""
=== Summary ===

Oblivious TM:
  - Head movement depends only on input length
  - Same path for all inputs of same length
  - Equivalent to standard TM
  - May be slower

Key uses:
  - Circuit complexity
  - Parallel computation
  - P-completeness

Key insight:
  Oblivious TMs bridge automata theory
  and circuit complexity.
  They're a fundamental tool in
  complexity theory.
""")

🌐 Universal TM

🎯 A Machine That Simulates All Machines

A Universal Turing Machine (UTM) can simulate any other Turing machine. Given a description of a TM M and an input w, the UTM computes what M would do on w. This is the foundation of programmable computers.

Universal TM Features

Input: ⟨M, w⟩ — description of M and input w. Output: Same as M on w. Simulation: Reads description, simulates. Encoding: M encoded as string. Universal: One machine, all TMs. Foundation: Programmable computers.

🌐 Universal📝 Encoding🔄 Simulation💻 Programmable

# Universal Turing Machine
print("=" * 60)
print("UNIVERSAL TURING MACHINE (UTM)")
print("=" * 60)

print("""
=== Definition ===

A Universal TM U is a TM that:
  - Takes input ⟨M, w⟩ (encoding of TM M and string w)
  - Simulates M on w
  - Accepts iff M accepts w
  - Rejects iff M rejects w
  - Loops iff M loops

U is a SINGLE machine that can simulate ALL TMs.

=== The Encoding ===

M is encoded as a string ⟨M⟩:
  - States encoded as binary numbers
  - Tape symbols encoded as binary numbers
  - Transitions encoded as tuples
  - All concatenated with separators

Example:
  M = ({q0, q1}, {0, 1}, {0, 1, _}, δ, q0, q_accept, q_reject)
  
  Encoding:
    States: q0=00, q1=01, q_accept=10, q_reject=11
    Symbols: 0=00, 1=01, _=10
    Transitions: encoded as (state, read, write, move, next_state)
    ...

=== Simulation ===

U on input ⟨M, w⟩:
  1. Parse ⟨M⟩ to get M's description
  2. Set up M's tape with w
  3. Simulate M step by step:
     - Read M's current state
     - Read M's tape at head position
     - Look up transition in M's description
     - Update M's state and tape
  4. Accept/reject/loop according to M

=== Why It Matters ===

1. PROGRAMMABLE COMPUTERS
   UTM = stored-program computer.
   - Hardware: UTM's fixed transitions
   - Software: M's description
   - Same hardware runs any program!

2. INTERPRETERS
   UTM = interpreter.
   - Reads program description
   - Executes it

3. VIRTUAL MACHINES
   UTM = VM.
   - Simulates other machines
   - Java VM, Python interpreter, etc.

4. UNDECIDABILITY
   UTM leads to halting problem!
   - U can simulate itself
   - Diagonalization gives contradiction
""")

# UTM IN CODE
print("=== UTM Implementation (Simplified) ===")

class SimpleTM:
    """A simple TM for demonstration."""
    def __init__(self, transitions, q0, q_accept, q_reject, blank='_'):
        self.delta = transitions
        self.q0 = q0
        self.q_accept = q_accept
        self.q_reject = q_reject
        self.blank = blank
    
    def encode(self):
        """Encode TM as a string."""
        parts = []
        parts.append(f"Q={','.join(sorted(self.delta.keys(), key=lambda x: str(x)))}")
        # Simplified encoding
        return f"TM({self.q0},{self.q_accept},{self.q_reject})"


class UniversalTM:
    """
    A Universal TM that simulates any SimpleTM.
    In practice, this would be a full TM.
    Here we use Python to simulate the concept.
    """
    def __init__(self):
        self.description = None
    
    def simulate(self, tm_description, input_string, max_steps=1000):
        """
        Simulate a TM given its description.
        In a real UTM, this would be done by the TM itself.
        """
        # Parse description (simplified)
        # In reality, this would be encoded on the tape
        print(f"  UTM: Parsing TM description...")
        print(f"  UTM: Setting up tape with '{input_string}'...")
        print(f"  UTM: Simulating...")
        
        # Create the TM from description (simplified)
        # In reality, UTM would simulate step by step
        return True


# Example: Encode and simulate
print("Encoding a TM:")
tm = SimpleTM(
    transitions={
        ('q0', '0'): ('q0', '0', 'R'),
        ('q0', '1'): ('q0', '1', 'R'),
        ('q0', '_'): ('q_accept', '_', 'R'),
    },
    q0='q0',
    q_accept='q_accept',
    q_reject='q_reject'
)

print(f"  TM description: {tm.encode()}")

print("\nUniversal TM simulation:")
utm = UniversalTM()
utm.simulate(tm.encode(), "101")

# UNIVERSALITY
print("""
=== Universality ===

The UTM is "universal" because:
  - ONE machine can simulate ALL TMs
  - The description of M is DATA on the tape
  - UTM's transitions are FIXED

This is the essence of:
  - Stored-program computers
  - Software
  - Virtual machines

=== Why This Is Revolutionary ===

Before UTM:
  - Each task needs its own machine
  - Hardware must be redesigned

With UTM:
  - One machine, any program
  - Software is just data
  - Hardware is universal

This is why we have:
  - General-purpose computers
  - App stores
  - Software industry

=== The Universal Machine ===

U = "read program, execute program"

This is exactly what:
  - CPUs do (fetch-decode-execute)
  - Interpreters do
  - Virtual machines do

All are implementations of the UTM concept.
""")

# UTM AND UNDECIDABILITY
print("""
=== UTM and Undecidability ===

The UTM is the key to proving undecidability!

HALT = { ⟨M, w⟩ | M halts on w }

This is the halting problem.
It's undecidable!

Proof (using UTM):
  Suppose HALT is decidable.
  Then there's a TM H that decides HALT.
  
  Construct D:
    D(⟨M⟩) = 
      if H(⟨M, M⟩) accepts: loop forever
      if H(⟨M, M⟩) rejects: halt and accept
  
  Consider D(⟨D⟩):
    If D(D) halts: H(⟨D, D⟩) accepts, so D(D) loops. Contradiction.
    If D(D) loops: H(⟨D, D⟩) rejects, so D(D) halts. Contradiction.
  
  Therefore, HALT is undecidable. ∎

This proof uses:
  - UTM (to simulate M on M)
  - Diagonalization (D on D)
  - Self-reference

The UTM makes this possible!
""")

# UTM VARIANTS
print("""
=== UTM Variants ===

1. SINGLE-TAPE UTM
   - Standard
   - O(T(n)²) simulation time

2. MULTI-TAPE UTM
   - Faster simulation
   - O(T(n)) or O(T(n) log T(n))

3. SMALL UNIVERSAL TM
   - Minimal number of states
   - Minimal number of symbols
   - Minsky: 7 states, 4 symbols
   - Wolfram: 2 states, 3 colors (Rule 110)
   - Smith: 2 states, 3 symbols

4. UNIVERSAL CIRCUIT
   - Circuit that simulates any TM
   - Used in P-completeness

5. UNIVERSAL PROGRAMMING LANGUAGE
   - Any Turing-complete language
   - Python, C, Java, etc.

All are equivalent in power.
""")

# SUMMARY
print("""
=== Summary ===

Universal TM:
  - Simulates any other TM
  - Input: ⟨M, w⟩
  - Output: M's behavior on w

Significance:
  - Foundation of programmable computers
  - Software is data
  - One machine, all programs

Connection to undecidability:
  - UTM enables self-reference
  - Halting problem proof uses UTM
  - Fundamental limit of computation

Key insight:
  Universality is the essence of computing.
  One machine can do anything computable.
  This is why computers are so powerful.
""")

📋 Enumerator

🎯 Listing the Strings of a Language

An enumerator is a Turing machine with an output tape that lists all strings of a language. It's equivalent to a recognizer — a language is recursively enumerable iff some enumerator lists it.

Enumerator Features

Output tape: Write-only, never erased. Lists strings: All strings in L. Order: Any order (may repeat). Infinite: May run forever. Equivalent: To recognizers. r.e.: Recursively enumerable.

📋 Output tape🔤 Lists strings♾️ May be infinite🔄 Equivalent

# Enumerator
print("=" * 60)
print("ENUMERATOR")
print("=" * 60)

print("""
=== Definition ===

An enumerator E is a TM with:
  - A work tape (read/write)
  - An output tape (write-only, never erased)

E:
  1. Starts with empty tapes
  2. Writes strings on output tape
  3. May run forever
  4. Lists all strings of a language L

=== Output ===

E prints strings one by one:
  w1, w2, w3, ...

The language of E is:
  L(E) = { w | w is eventually printed }

Note:
  - Order doesn't matter
  - Repetitions allowed
  - May print forever (infinite language)
  - May stop (finite language)

=== Equivalence ===

L is recursively enumerable (r.e.)
  ⟺
There's an enumerator that lists L.

Proof:
  (⇐) Given enumerator E:
    Build recognizer M:
      M(w): run E, if w is printed, accept.
      (May loop if w never printed.)
  
  (⇒) Given recognizer M:
    Build enumerator E:
      E: for each string w (in some order):
           simulate M on w for a bounded time
           if M accepts, print w
      (Uses "dovetailing" — interleave simulations.)

Both directions work. So equivalent.
""")

# ENUMERATOR IN CODE
print("=== Enumerator Implementation ===")

class Enumerator:
    """
    A simple enumerator.
    Prints strings of a language.
    """
    def __init__(self, language_description, alphabet, max_length=10):
        self.desc = language_description
        self.alphabet = alphabet
        self.max_length = max_length
        self.output = []
    
    def enumerate(self, max_strings=1000):
        """Enumerate strings of the language."""
        from itertools import product
        
        count = 0
        for length in range(self.max_length + 1):
            for chars in product(self.alphabet, repeat=length):
                if count >= max_strings:
                    return self.output
                w = ''.join(chars)
                if self.desc(w):
                    self.output.append(w)
                    count += 1
        return self.output


# Example: Enumerate a^n b^n
def anbn(w):
    n = len(w)
    for i in range(n + 1):
        if w == 'a'*i + 'b'*i:
            return True
    return False

print("Enumerator for a^n b^n:")
enum = Enumerator(anbn, {'a', 'b'}, max_length=6)
result = enum.enumerate(max_strings=20)
print(f"  First 20 strings: {result}")

# Example: Enumerate palindromes
def palindrome(w):
    return w == w[::-1]

print("\nEnumerator for palindromes over {a,b}:")
enum2 = Enumerator(palindrome, {'a', 'b'}, max_length=5)
result2 = enum2.enumerate(max_strings=20)
print(f"  First 20 strings: {result2}")

# DOVETAILING
print("""
=== Dovetailing ===

Dovetailing is the technique of interleaving
multiple computations.

Problem:
  Given recognizer M for L, enumerate L.
  
Naive approach:
  For each w: simulate M on w.
  If M accepts, print w.
  
Issue:
  If M loops on some w, we're stuck!
  We never move to the next w.

Solution: Dovetailing
  Simulate M on multiple inputs in parallel.
  Use "time-slicing":
  
  Round 1: simulate M on w1 for 1 step
  Round 2: simulate M on w1 for 2 steps
           simulate M on w2 for 1 step
  Round 3: simulate M on w1 for 3 steps
           simulate M on w2 for 2 steps
           simulate M on w3 for 1 step
  ...
  
  If M accepts wi, print wi.
  If M loops on wi, we still make progress on other inputs.

=== Dovetailing in Code ===

  def enumerate_dovetail(M, alphabet):
      strings = generate_all_strings(alphabet)
      for round in range(1, infinity):
          for i in range(round):
              simulate M on strings[i] for (round - i) steps
              if M accepted:
                  print(strings[i])
""")

# DOVETAILING IN CODE
print("=== Dovetailing Implementation ===")

def enumerate_with_dovetail(recognizer, alphabet, max_rounds=100, max_strings=50):
    """
    Enumerate a language using dovetailing.
    recognizer(w, steps) -> True if accepts within steps
    """
    from itertools import product
    
    # Generate all strings in shortlex order
    all_strings = []
    length = 0
    while len(all_strings) < 1000:
        for chars in product(alphabet, repeat=length):
            all_strings.append(''.join(chars))
        length += 1
    
    output = []
    
    for round_num in range(1, max_rounds + 1):
        for i in range(min(round_num, len(all_strings))):
            w = all_strings[i]
            steps = round_num - i
            if steps <= 0:
                continue
            if recognizer(w, steps):
                if w not in output:
                    output.append(w)
                    if len(output) >= max_strings:
                        return output
    
    return output


# Example recognizer with steps
def anbn_recognizer(w, steps):
    """Recognize a^n b^n within given steps."""
    n = len(w)
    for i in range(n + 1):
        if w == 'a'*i + 'b'*i:
            return True
    return False


print("Dovetailing enumeration:")
result = enumerate_with_dovetail(anbn_recognizer, {'a', 'b'}, max_rounds=200, max_strings=15)
print(f"  First 15 strings: {result}")

# ENUMERATOR VS RECOGNIZER
print("""
=== Enumerator vs Recognizer ===

RECOGNIZER M:
  Input: w
  Output: accept, reject, or loop
  Accepts if w ∈ L
  May loop if w ∉ L

ENUMERATOR E:
  Input: none
  Output: list of strings
  Prints all strings in L
  May run forever

=== Equivalence ===

L is r.e. ⟺ L has a recognizer
         ⟺ L has an enumerator

Both are equivalent characterizations
of recursively enumerable languages.

=== Decidable Languages ===

L is decidable ⟺ L has a decider
               ⟺ L has an enumerator that
                  prints strings in lex order

For decidable languages:
  - Enumerator can print in sorted order
  - Recognizer always halts

=== Why Enumerators Matter ===

1. PROOF TECHNIQUE
   Easier to show r.e. via enumerator.

2. DIAGONALIZATION
   Enumerators are used in proofs.

3. COMPUTABILITY
   Enumerability is a key concept.

4. PRACTICAL
   Compilers list tokens, etc.
""")

# SUMMARY
print("""
=== Summary ===

Enumerator:
  - TM with output tape
  - Lists all strings of a language
  - May run forever

Equivalence:
  L is r.e. ⟺ L has an enumerator

Dovetailing:
  - Interleave simulations
  - Make progress despite loops
  - Key technique for enumeration

Key insight:
  Enumerators and recognizers are
  two views of the same class
  (recursively enumerable languages).
""")

💾 RAM Machine

🎯 Random Access Memory

A Random Access Machine (RAM) is a model of computation with an infinite array of registers, each accessible in O(1) time. It's closer to real computers than TMs and is used in algorithm analysis.

RAM Features

Registers: Infinite array. O(1) access: Any register. Instructions: LOAD, STORE, ADD, etc. Indirect: Address in register. Equivalent: To TM. Practical: Algorithm analysis.

💾 Registers⚡ O(1) access📝 Instructions🔄 Equivalent

# RAM Machine
print("=" * 60)
print("RANDOM ACCESS MACHINE (RAM)")
print("=" * 60)

print("""
=== Definition ===

A RAM has:
  - Infinite array of registers R[0], R[1], R[2], ...
  - Each holds an integer
  - Instructions operate on registers
  - Indirect addressing: R[R[i]]

Instructions:
  LOAD i      : R[0] = R[i]
  STORE i     : R[i] = R[0]
  ADD i       : R[0] = R[0] + R[i]
  SUB i       : R[0] = R[0] - R[i]
  MULT i      : R[0] = R[0] * R[i]
  DIV i       : R[0] = R[0] / R[i]
  JUMP i      : goto instruction i
  JZERO i     : if R[0] == 0, goto i
  READ i      : R[i] = input
  WRITE i     : output R[i]
  HALT        : stop

=== Power ===

RAM ≡ TM (same power!)

Proof:
  (RAM → TM):
    Simulate RAM on TM:
      - Encode registers on tape
      - Use markers for accessed registers
      - Simulate one instruction per step
    Time: polynomial in RAM's time
  
  (TM → RAM):
    Simulate TM on RAM:
      - Use registers for tape cells
      - Use register for head position
      - Simulate one step per instruction
    Time: linear in TM's time

Both simulations are polynomial.
So RAM and TM are polynomial-time equivalent.

=== Why RAM? ===

1. CLOSER TO REAL COMPUTERS
   - Real computers have RAM
   - Instructions match CPU
   - More natural for algorithms

2. ALGORITHM ANALYSIS
   - Count instructions
   - O(1) array access
   - Standard model for CS

3. COMPLEXITY THEORY
   - RAM is used in algorithm analysis
   - Time complexity measured in RAM steps
   - Polynomial equivalence to TM
""")

# RAM IN CODE
print("=== RAM Implementation ===")

class RAM:
    """A simple Random Access Machine."""
    def __init__(self, program, max_registers=1000, max_steps=10000):
        self.program = program
        self.registers = [0] * max_registers
        self.pc = 0  # program counter
        self.max_steps = max_steps
        self.output = []
        self.input_queue = []
        self.halted = False
    
    def load_input(self, data):
        """Load input data."""
        self.input_queue = list(data)
    
    def run(self, verbose=False):
        """Run the RAM program."""
        steps = 0
        
        while steps < self.max_steps and not self.halted:
            if self.pc >= len(self.program):
                break
            
            instr = self.program[self.pc]
            parts = instr.split()
            op = parts[0]
            
            if verbose and steps < 30:
                print(f"  Step {steps}: PC={self.pc}, R0={self.registers[0]}, R1={self.registers[1]}, instr={instr}")
            
            if op == 'LOAD':
                i = int(parts[1])
                self.registers[0] = self.registers[i]
                self.pc += 1
            
            elif op == 'STORE':
                i = int(parts[1])
                self.registers[i] = self.registers[0]
                self.pc += 1
            
            elif op == 'ADD':
                i = int(parts[1])
                self.registers[0] += self.registers[i]
                self.pc += 1
            
            elif op == 'SUB':
                i = int(parts[1])
                self.registers[0] -= self.registers[i]
                self.pc += 1
            
            elif op == 'MULT':
                i = int(parts[1])
                self.registers[0] *= self.registers[i]
                self.pc += 1
            
            elif op == 'DIV':
                i = int(parts[1])
                if self.registers[i] != 0:
                    self.registers[0] //= self.registers[i]
                self.pc += 1
            
            elif op == 'JUMP':
                self.pc = int(parts[1])
            
            elif op == 'JZERO':
                if self.registers[0] == 0:
                    self.pc = int(parts[1])
                else:
                    self.pc += 1
            
            elif op == 'READ':
                i = int(parts[1])
                if self.input_queue:
                    self.registers[i] = self.input_queue.pop(0)
                self.pc += 1
            
            elif op == 'WRITE':
                i = int(parts[1])
                self.output.append(self.registers[i])
                self.pc += 1
            
            elif op == 'HALT':
                self.halted = True
                break
            
            else:
                raise ValueError(f"Unknown instruction: {op}")
            
            steps += 1
        
        return self.output, steps


# Example: Add two numbers
print("RAM program: add two numbers")
print("""
  READ 1      ; read first number into R1
  READ 2      ; read second number into R2
  LOAD 1      ; R0 = R1
  ADD 2       ; R0 = R0 + R2
  WRITE 0     ; output R0
  HALT
""")

program = [
    'READ 1',
    'READ 2',
    'LOAD 1',
    'ADD 2',
    'WRITE 0',
    'HALT'
]

ram = RAM(program)
ram.load_input([10, 25])
output, steps = ram.run(verbose=True)
print(f"\n  Input: [10, 25]")
print(f"  Output: {output}")
print(f"  Steps: {steps}")

# Example: Multiply via repeated addition
print("\n=== RAM program: multiply (repeated addition) ===")
print("""
  READ 1      ; R1 = a
  READ 2      ; R2 = b
  LOAD 1      ; R0 = a
  STORE 3     ; R3 = a (accumulator)
  LOAD 2      ; R0 = b
  STORE 4     ; R4 = b (counter)
  LOAD 4      ; R0 = counter
  JZERO 14    ; if counter == 0, done
  LOAD 3      ; R0 = accumulator
  ADD 1       ; R0 += a
  STORE 3     ; accumulator = R0
  LOAD 4      ; R0 = counter
  SUB 5       ; R0 -= 1 (R5 = 1)
  STORE 4     ; counter = R0
  JUMP 7      ; loop
  LOAD 3      ; R0 = accumulator
  WRITE 0     ; output
  HALT
""")

mult_program = [
    'READ 1',      # 0
    'READ 2',      # 1
    'LOAD 1',      # 2
    'STORE 3',     # 3
    'LOAD 2',      # 4
    'STORE 4',     # 5
    'LOAD 4',      # 6
    'JZERO 15',    # 7
    'LOAD 3',      # 8
    'ADD 1',       # 9
    'STORE 3',     # 10
    'LOAD 4',      # 11
    'SUB 5',       # 12 (R5 needs to be 1)
    'STORE 4',     # 13
    'JUMP 6',      # 14
    'LOAD 3',      # 15
    'WRITE 0',     # 16
    'HALT'         # 17
]

# Set R5 = 1
ram2 = RAM(mult_program)
ram2.registers[5] = 1
ram2.load_input([3, 4])
output2, steps2 = ram2.run()
print(f"  Input: [3, 4]")
print(f"  Output: {output2}")
print(f"  Steps: {steps2}")

# RAM VS TM
print("""
=== RAM vs TM ===

Similarities:
  - Both infinite memory
  - Both can compute anything computable
  - Polynomial-time equivalent

Differences:
  RAM:
    - O(1) random access
    - Integer arithmetic
    - Closer to real computers

  TM:
    - Sequential access
    - Symbol manipulation
    - Simpler to analyze theoretically

=== Simulation Costs ===

RAM → TM:
  - Registers encoded on tape
  - O(n) to access register n
  - Polynomial slowdown

TM → RAM:
  - Tape cells in registers
  - O(1) to access any cell
  - Linear speedup

Both are polynomial.
So P, NP, etc. are the same for both.

=== Practical Use ===

RAM is the standard model for:
  - Algorithm analysis
  - Complexity theory
  - Programming language semantics

When we say "O(n log n) algorithm",
we mean on a RAM (or similar model).
""")

# SUMMARY
print("""
=== Summary ===

RAM:
  - Infinite array of registers
  - O(1) random access
  - Realistic instruction set

Power:
  RAM ≡ TM (polynomial-time equivalent)

Uses:
  - Algorithm analysis
  - Complexity theory
  - Programming language theory

Key insight:
  RAM is the "practical" model of computation.
  TMs are the "theoretical" model.
  Both have the same power.
  Choose the one that's convenient.
""")

⚖️ Equivalence Proofs

🎯 Proving Variants Are Equivalent

To prove two TM variants are equivalent, we show each can simulate the other. This section covers the general technique and key simulations.

Equivalence Technique

Direction 1: V1 simulates V2. Direction 2: V2 simulates V1. Conclusion: V1 ≡ V2. Simulation: Step-by-step encoding. Cost: Polynomial slowdown. Power: Same languages.

↔️ Both directions🔄 Simulation📊 Encoding⚖️ Equivalent

# Equivalence Proofs
print("=" * 60)
print("EQUIVALENCE PROOFS")
print("=" * 60)

print("""
=== General Technique ===

To prove V1 ≡ V2:

1. SHOW V1 SIMULATES V2
   For every V2 computation, V1 can do it.

2. SHOW V2 SIMULATES V1
   For every V1 computation, V2 can do it.

3. CONCLUDE V1 ≡ V2

=== Simulation Template ===

Given machine M2 (variant 2),
construct machine M1 (variant 1) such that:
  L(M1) = L(M2)

Construction:
  1. Encode M2's configuration in M1's memory
  2. M1 simulates M2 step by step
  3. M1 accepts iff M2 accepts

Key: The simulation must be correct.
""")

# MULTI-TAPE TO SINGLE-TAPE
print("=== Multi-Tape → Single-Tape ===")
print("""
Given: k-tape TM M
Construct: single-tape TM M'

Encoding:
  - Use 2k tracks
  - Track 2i: contents of tape i
  - Track 2i+1: head position marker for tape i

Visual:
  ┌───┬───┬───┬───┬───┐
  │ a │ b │ c │ _ │ _ │  ← tape 0
  ├───┼───┼───┼───┼───┤
  │   │ ↑ │   │   │   │  ← head 0
  ├───┼───┼───┼───┼───┤
  │ X │ Y │ _ │ _ │ _ │  ← tape 1
  ├───┼───┼───┼───┼───┤
  │   │   │ ↑ │   │   │  ← head 1
  └───┴───┴───┴───┴───┘

Simulation of one M step:
  1. Scan right to find all head markers
  2. Read symbols at head positions
  3. Determine M's transition
  4. Scan back, update tapes and head markers
  5. Repeat

Time: O(k × n) per step
Total: O(k × n²) for n steps

So single-tape simulates multi-tape
with quadratic slowdown.

=== Code: Multi-Tape Simulation ===

  def simulate_multitape_on_single(multitape, input):
      # Encode multitape configuration
      # Simulate step by step
      # Each step: scan, update, scan back
      pass
""")

# NTM TO TM
print("=== NTM → TM ===")
print("""
Given: NTM N
Construct: TM M

Simulation: BFS on computation tree
  1. Start with initial configuration
  2. For each configuration, generate all successors
  3. Explore level by level (BFS)
  4. Accept if any accepting configuration found

Time: Exponential in worst case
Space: Exponential

Encoding:
  - M stores the tree on its tape
  - Uses BFS (queue)
  - Each configuration is a node

=== Code: NTM Simulation ===

  def simulate_ntm_on_tm(ntm, input):
      queue = [initial_config(ntm, input)]
      visited = set()
      
      while queue:
          config = queue.pop(0)
          if config.is_accepting():
              return True
          if config.is_rejecting():
              continue
          for next_config in ntm.transitions(config):
              if next_config not in visited:
                  visited.add(next_config)
                  queue.append(next_config)
      
      return False

Time: O(b^d) where b = branching, d = depth
""")

# TWO-WAY TO ONE-WAY
print("=== Two-Way → One-Way ===")
print("""
Given: Two-way infinite tape TM M
Construct: One-way infinite tape TM M'

Encoding:
  - Use 2 tracks
  - Track 0: cells 0, 1, 2, ... (right half)
  - Track 1: cells -1, -2, -3, ... (left half)
  - Special marker at origin

Visual:
  Position:  0    1    2    3    4   ...
  Track 0: [origin] a    b    c    _   ...
  Track 1: [origin] X    Y    Z    _   ...

Simulation:
  - Moving right: update track 0
  - Moving left: update track 1
  - Special handling at origin

Time: O(n) per step
Total: O(n²)

So one-way simulates two-way.
""")

# MULTI-HEAD TO SINGLE-HEAD
print("=== Multi-Head → Single-Head ===")
print("""
Given: k-head TM M
Construct: Single-head TM M'

Encoding:
  - Use k markers on tape
  - Marker i represents head i
  - Each marker is unique

Visual:
  Tape: a b c d e f g h
  Head 0 at 2: marker X0
  Head 1 at 5: marker X1
  
  Encoded: a b [X0]c d e [X1]f g h

Simulation of one step:
  1. Scan right, find all markers
  2. Read symbols under markers
  3. Determine transition
  4. Scan back, update markers and symbols
  5. Repeat

Time: O(k × n) per step
Total: O(k × n²)

So single-head simulates multi-head.
""")

# SUMMARY TABLE
print("=== Equivalence Summary ===")
print(f"{'Variant':<30} {'Simulates':<30} {'Cost':<20}")
print("-" * 80)
print(f"{'Multi-tape':<30} {'Single-tape':<30} {'O(n)':<20}")
print(f"{'Single-tape':<30} {'Multi-tape':<30} {'O(n²)':<20}")
print(f"{'NTM':<30} {'TM':<30} {'Exponential':<20}")
print(f"{'Two-way':<30} {'One-way':<30} {'O(n)':<20}")
print(f"{'Multi-head':<30} {'Single-head':<30} {'O(n²)':<20}")
print(f"{'Oblivious':<30} {'Standard':<30} {'O(T(n)×S(n))':<20}")
print(f"{'RAM':<30} {'TM':<30} {'Polynomial':<20}")

print("""
=== Key Insights ===

1. ALL VARIANTS ARE EQUIVALENT
   Same set of recognizable languages.

2. SIMULATION COSTS DIFFER
   Some simulations are faster than others.

3. POLYNOMIAL VS EXPONENTIAL
   Multi-tape → single-tape: polynomial
   NTM → TM: exponential
   
   This matters for complexity theory!

4. CHOOSE THE RIGHT VARIANT
   For proofs: use the easiest
   For algorithms: use the fastest
   For complexity: use the standard

5. CHURCH-TURING THESIS
   All these models support the thesis.
   Computation is robust.
""")

# PROOF TECHNIQUES
print("""
=== Proof Techniques ===

1. DIRECT SIMULATION
   Show how to simulate step by step.
   Most common technique.

2. ENCODING
   Encode one variant's configuration
   in the other variant's memory.

3. MODULAR CONSTRUCTION
   Build simulation from simple pieces.
   Each piece handles one aspect.

4. INDUCTION
   Prove correctness by induction on steps.
   
   Base case: initial configuration.
   Inductive step: simulation preserves behavior.

5. INVARIANTS
   Maintain invariants during simulation.
   Example: "tape encoding matches M's tape"

=== Common Mistakes ===

✗ Assuming simulation is free
  (It has a cost!)

✗ Forgetting to handle edge cases
  (Start, end, empty input)

✗ Incorrect encoding
  (Must preserve all information)

✗ Not proving termination
  (Simulation must halt when M halts)

✗ Not proving correctness
  (Simulation must match M's behavior)
""")

# SUMMARY
print("""
=== Summary ===

To prove V1 ≡ V2:
  1. Show V1 simulates V2
  2. Show V2 simulates V1
  3. Conclude equivalence

Key simulations:
  Multi-tape → Single-tape: O(n²)
  NTM → TM: exponential
  Two-way → One-way: O(n)
  Multi-head → Single-head: O(n²)
  RAM → TM: polynomial

All variants:
  - Same computational power
  - Different simulation costs
  - Support Church-Turing thesis

Key insight:
  Equivalence is about POWER, not SPEED.
  All variants recognize the same languages.
  Choose based on convenience and efficiency.
""")

💼 Applications

🎯 Variants in the Real World

TM variants aren't just theoretical — they model real systems and are used in compiler design, complexity theory, and parallel computing.

Application Domains

Compilers: Multi-tape models. Complexity: NTM defines NP. Parallel: Multi-head, circuits. Interpreters: Universal TM. Algorithms: RAM model. Verification: Oblivious TMs.

💻 Compilers⏱️ Complexity⚡ Parallel🌐 Universal

# Applications of TM Variants
print("=" * 60)
print("APPLICATIONS OF TM VARIANTS")
print("=" * 60)

# 1. COMPILERS
print("""
=== 1. Compilers ===

Multi-tape TMs model compiler phases:

Tape 0: source code (input)
Tape 1: token stream (lexer output)
Tape 2: parse tree (parser output)
Tape 3: intermediate code (codegen)
Tape 4: optimized code (optimizer)
Tape 5: machine code (final output)

Each phase reads from one tape,
writes to another.

This is why multi-tape is natural
for compiler design.

=== Example: GCC Pipeline ===

  Source → Preprocessor → Compiler → Assembler → Linker → Executable

Each stage is like a tape transformation.
""")

# 2. COMPLEXITY THEORY
print("""
=== 2. Complexity Theory ===

NTM defines NP:

  NP = { L | L is decided by an NTM in poly time }

Without NTM, we couldn't define NP!
(Or we'd use a more complicated definition.)

P vs NP:
  P = DTM poly time
  NP = NTM poly time
  Is P = NP?

This is THE central open problem.

Other classes defined via variants:
  NL = NTM log space
  co-NP = complement of NP
  BPP = probabilistic poly time
  BQP = quantum poly time

All use TM variants.
""")

# 3. PARALLEL COMPUTING
print("""
=== 3. Parallel Computing ===

Multi-head TMs model parallel computation:

  - Multiple heads = multiple processors
  - Same tape = shared memory
  - Independent movement = parallel access

Used in:
  - PRAM (Parallel Random Access Machine)
  - Circuit complexity
  - Parallel algorithms

Key question:
  Which problems can be parallelized?
  
  NC = problems solvable in polylog time
       with polynomial processors
       
  P-complete = hardest to parallelize

Multi-head TMs help study this.
""")

# 4. INTERPRETERS AND VMS
print("""
=== 4. Interpreters and VMs ===

Universal TM models:

  - Interpreters (Python, Ruby)
  - Virtual machines (JVM, CLR)
  - Emulators (game consoles, etc.)

UTM concept:
  1. Read program description
  2. Set up machine state
  3. Execute step by step

This is exactly what interpreters do!

Example: Python interpreter
  - Reads .py file (description)
  - Sets up Python state
  - Executes bytecode
  - Outputs results

The interpreter is a UTM.
""")

# 5. ALGORITHM ANALYSIS
print("""
=== 5. Algorithm Analysis ===

RAM model is standard for:

  - Big-O analysis
  - Algorithm design
  - Data structure analysis

When we say "O(n log n) sort":
  - We mean on a RAM
  - O(1) array access
  - O(1) arithmetic

RAM is polynomial-equivalent to TM.
So results transfer.

Used in:
  - Competitive programming
  - Interview prep
  - CS education
  - Research papers
""")

# 6. VERIFICATION AND CIRCUITS
print("""
=== 6. Verification and Circuits ===

Oblivious TMs model circuits:

  - Time = circuit depth
  - Space = circuit width
  - Each step = one layer

Used in:
  - Hardware verification
  - Circuit complexity
  - P-completeness
  - Parallel algorithm lower bounds

Key result:
  P ⊆ P/poly (poly-size circuits)

This connection is fundamental
to complexity theory.
""")

# 7. QUANTUM COMPUTING
print("""
=== 7. Quantum Computing ===

Quantum TM (QTM) is a variant:

  - Quantum states (superposition)
  - Unitary transitions
  - Measurement at end

Power:
  QTM ≡ TM (probably)
  But different complexity: BQP

Used in:
  - Quantum algorithm design
  - Quantum complexity theory
  - Quantum cryptography

Key question:
  Can quantum computers solve NP-hard problems?
  (Probably not.)
""")

# 8. SUMMARY TABLE
print("=== Application Summary ===")
print(f"{'Domain':<25} {'Variant':<25} {'Role':<25}")
print("-" * 75)
print(f"{'Compilers':<25} {'Multi-tape':<25} {'Phase modeling':<25}")
print(f"{'Complexity':<25} {'NTM':<25} {'Defines NP':<25}")
print(f"{'Parallel':<25} {'Multi-head':<25} {'Parallel model':<25}")
print(f"{'Interpreters':<25} {'Universal TM':<25} {'Program execution':<25}")
print(f"{'Algorithms':<25} {'RAM':<25} {'Analysis model':<25}")
print(f"{'Circuits':<25} {'Oblivious TM':<25} {'Circuit connection':<25}")
print(f"{'Quantum':<25} {'Quantum TM':<25} {'BQP class':<25}")

# 9. CASE STUDY: PYTHON INTERPRETER
print("""
=== Case Study: Python Interpreter ===

Python interpreter is a UTM:

1. READ PROGRAM
   - Parse .py file into AST
   - Compile to bytecode

2. SET UP STATE
   - Create frame with locals/globals
   - Initialize stack

3. EXECUTE
   - Fetch bytecode instruction
   - Decode and execute
   - Update state
   - Repeat

This is exactly UTM simulation!

Bytecode = description of computation
Interpreter = UTM
State = tape + registers

The interpreter can run ANY Python program
(within memory limits).
""")

# 10. CASE STUDY: JVM
print("""
=== Case Study: Java Virtual Machine ===

JVM is a UTM:

1. INPUT: .class file (bytecode)
2. SETUP: Create JVM state
3. EXECUTE: Interpret bytecode
4. OUTPUT: Program results

JVM features:
  - Platform independence (WORA)
  - Just-in-time compilation
  - Garbage collection

UTM connection:
  - JVM simulates any Java program
  - Bytecode is the description
  - JVM is the universal machine

This is why Java can "write once, run anywhere."
""")

# 11. TAKEAWAYS
print("""
=== Practical Takeaways ===

1. TM VARIANTS MODEL REAL SYSTEMS
   - Multi-tape: compilers
   - NTM: complexity classes
   - Universal: interpreters
   - RAM: algorithms

2. CHOOSE THE RIGHT VARIANT
   - For proofs: easiest
   - For algorithms: fastest
   - For complexity: standard

3. EQUIVALENCE IS POWERFUL
   - Results transfer
   - Choose convenient model
   - Same fundamental limits

4. CHURCH-TURING THESIS
   - All variants equivalent
   - Strong evidence
   - Foundation of CS

5. PRACTICAL IMPACT
   - Compilers use multi-tape concepts
   - NP defined via NTM
   - Interpreters are UTMs
   - Algorithms analyzed on RAM
""")

🚀 Advanced Topics

🎯 Beyond the Basics

TM variants connect to many advanced topics: circuit complexity, quantum computing, parallel computation, and hypercomputation.

Advanced Directions

Circuits: Oblivious TMs. Quantum: Quantum TMs. Parallel: PRAM, NC. Hypercomputation: Beyond TM. Interactive: Interactive proofs. Biological: DNA, neural.

🔌 Circuits⚛️ Quantum⚡ Parallel🚀 Hyper

# Advanced Topics
print("=" * 60)
print("ADVANCED TOPICS")
print("=" * 60)

# 1. CIRCUIT COMPLEXITY
print("""
=== 1. Circuit Complexity ===

Oblivious TMs ↔ Circuits:

  TM time T(n) ↔ Circuit depth O(T(n))
  TM space S(n) ↔ Circuit width O(S(n))

Key classes:
  P/poly = problems solvable by poly-size circuits
  NC = problems solvable by polylog-depth circuits
  AC = NC with unbounded fan-in
  TC = NC with threshold gates

Key results:
  P ⊆ P/poly
  NC ⊆ P
  P-complete problems are hard to parallelize

Used in:
  - Hardware verification
  - Parallel algorithm design
  - Lower bounds
""")

# 2. QUANTUM TURING MACHINES
print("""
=== 2. Quantum Turing Machines ===

Quantum TM (QTM):
  - States are quantum superpositions
  - Transitions are unitary matrices
  - Measurement at the end

Power:
  QTM ≡ TM (probably)
  But different complexity: BQP

BQP:
  Bounded-error quantum polynomial time
  P ⊆ BQP ⊆ PSPACE

Key algorithms:
  - Shor's factoring (exponential speedup)
  - Grover's search (quadratic speedup)

Open questions:
  Is BQP = P? (No, probably)
  Is BQP = NP? (No, probably)
""")

# 3. PARALLEL COMPUTATION
print("""
=== 3. Parallel Computation ===

PRAM (Parallel Random Access Machine):
  - Multiple processors
  - Shared memory
  - O(1) access

Models:
  - EREW: exclusive read, exclusive write
  - CREW: concurrent read, exclusive write
  - CRCW: concurrent read, concurrent write

NC:
  Nick's Class
  Problems solvable in O(log^k n) time
  with O(n^j) processors

P-complete:
  Hardest problems to parallelize
  If P ≠ NC, these can't be parallelized

TM variants (multi-head) model these.
""")

# 4. HYPERCOMPUTATION
print("""
=== 4. Hypercomputation ===

Can we compute MORE than a TM?

Theoretical models:
  1. Oracle machines (Turing, 1939)
  2. Infinite time TMs
  3. Real computation
  4. Zeno machines
  5. Quantum hypercomputation

All require non-physical assumptions.
No physical hypercomputer known.

Consensus:
  Physical Church-Turing thesis:
  All physical computation is TM-equivalent.

But debate continues.
""")

# 5. INTERACTIVE PROOFS
print("""
=== 5. Interactive Proofs ===

Interactive proof system:
  - Prover (unbounded)
  - Verifier (polynomial time)
  - Exchange messages
  - Verifier accepts/rejects

Classes:
  IP = interactive polynomial time
  IP = PSPACE (Shamir, 1992)
  PCP = probabilistically checkable proofs

Connection to TMs:
  Verifier is a probabilistic TM.
  Prover is unbounded (oracle).

Used in:
  - Cryptography
  - Complexity theory
  - Approximation algorithms
""")

# 6. BIOLOGICAL COMPUTING
print("""
=== 6. Biological Computing ===

DNA Computing:
  - Uses DNA molecules
  - Adleman (1994): Hamiltonian path
  - Massively parallel
  - TM-equivalent (probably)

Neural Computing:
  - Brain-inspired
  - Artificial neural networks
  - TM-equivalent (with enough neurons)

Cellular Automata:
  - Grid of cells
  - Local rules
  - Rule 110 is Turing-complete

All TM-equivalent.
May be faster or more efficient,
but not more powerful.
""")

# 7. OPEN PROBLEMS
print("""
=== 7. Open Problems ===

1. P vs NP
   The biggest open problem in CS.

2. P vs NC
   Can all P problems be parallelized?

3. BQP vs NP
   Can quantum computers solve NP-hard problems?

4. Physical Church-Turing
   Is all physical computation TM-equivalent?

5. Hypercomputation
   Do physical hypercomputers exist?

6. Circuit Lower Bounds
   Prove explicit functions need large circuits.

7. Derandomization
   Can we remove randomness from algorithms?

These are active research areas.
""")

# 8. RECOMMENDATIONS
print("""
=== Recommendations ===

For students:
  1. Master standard TM first
  2. Understand multi-tape and NTM
  3. Study equivalence proofs
  4. Explore complexity connections
  5. Learn about circuits

For researchers:
  1. Circuit complexity
  2. Quantum computing
  3. Parallel algorithms
  4. Hypercomputation (cautiously)
  5. Interactive proofs

For practitioners:
  1. Understand UTM concept
  2. Know NTM for NP
  3. Use multi-tape model
  4. Apply RAM for analysis
  5. Recognize limits

=== Final Thoughts ===

TM variants are:

✓ EQUIVALENT
  Same computational power.

✓ DIFFERENT
  Different speed, convenience.

✓ FOUNDATIONAL
  Support Church-Turing thesis.

✓ PRACTICAL
  Model real systems.

✓ CONNECTED
  Link to circuits, quantum, parallel.

Key takeaway:
  Computation is robust.
  Many models, same power.
  Choose the right tool for the job.

"All models are wrong, but some are useful."
  — George Box

Go compute something!
""")

# QUICK REFERENCE
print("""
=== Quick Reference ===

Standard TM:
  (Q, Σ, Γ, δ, q0, q_accept, q_reject)
  δ: Q × Γ → Q × Γ × {L,R}

Multi-tape:
  δ: Q × Γ^k → Q × Γ^k × {L,R}^k
  Same power, faster.

NTM:
  δ: Q × Γ → P(Q × Γ × {L,R})
  Same power, exponential slowdown.

Two-way:
  Tape infinite both directions.
  Same power.

Multi-head:
  k heads on one tape.
  Same power, faster.

Oblivious:
  Head path depends only on input length.
  Same power, used in circuits.

Universal:
  Simulates all TMs.
  Foundation of programmable computers.

Enumerator:
  Lists strings of a language.
  Equivalent to recognizer.

RAM:
  Infinite registers, O(1) access.
  Equivalent to TM.

All equivalent in power!
Choose based on convenience.
""")