🧠 Introduction

🎯 What is Decidability?

A problem is decidable if there exists an algorithm (a Turing machine that always halts) that correctly answers "yes" or "no" for every input. Undecidable problems have no such algorithm. Decidability theory studies the boundary between what can and cannot be computed.

Key insight: Not all problems can be solved by computers. Some problems are fundamentally impossible — no future technology can overcome this. Understanding decidability tells us the limits of computation.

Why Decidability Matters

Limits: What computers can't do. Foundation: Basis of computability theory. Halting problem: First undecidable problem. Reductions: Proving undecidability. Practical: No perfect debuggers, virus detectors. Philosophy: Limits of knowledge.

✅ Decidable🔄 Recognizable❌ Undecidable🛑 Halting problem

# Decidability — the big picture
print("""
=== What is Decidability? ===

A problem is DECIDABLE if:
  There's an algorithm that always halts
  and correctly answers "yes" or "no"
  for every input.

A problem is UNDECIDABLE if:
  No such algorithm exists.

=== The Three Classes ===

DECIDABLE (Recursive):
  - Always halts
  - Correct yes/no answer
  - Examples: DFA membership, CFL membership

RECOGNIZABLE (Recursively Enumerable):
  - Halts and accepts if "yes"
  - May loop if "no"
  - Examples: HALT, TM membership

UNDECIDABLE:
  - Not decidable
  - May be recognizable or not
  - Examples: HALT, EQUIVALENCE

=== The Hierarchy ===

  All Languages
  ┌─────────────────────────────┐
  │                             │
  │   Recognizable (r.e.)       │
  │   ┌─────────────────────┐   │
  │   │                     │   │
  │   │   Decidable         │   │
  │   │   (Recursive)       │   │
  │   │                     │   │
  │   └─────────────────────┘   │
  │                             │
  └─────────────────────────────┘

  Decidable ⊊ Recognizable ⊊ All Languages

Each inclusion is STRICT.

=== Why It Matters ===

1. LIMITS OF COMPUTATION
   Some problems have no algorithmic solution.
   This is a fundamental mathematical fact.

2. PRACTICAL IMPLICATIONS
   No perfect debugger, virus detector, optimizer.
   We must use approximations.

3. THEORETICAL FOUNDATION
   Decidability theory defines what's computable.
   It's the basis of computer science.

4. PHILOSOPHICAL IMPLICATIONS
   Limits of knowledge.
   Nature of computation.
   Mind and machine.

=== Historical Context ===

1900: Hilbert's 10th problem
  Find algorithm for Diophantine equations.
  (Solved negatively in 1970.)

1928: Hilbert's Entscheidungsproblem
  Find algorithm to decide provability.
  (Turing, 1936: No such algorithm!)

1931: Gödel's incompleteness
  Some truths are unprovable.

1936: Turing's halting problem
  First explicit undecidable problem.

1936: Church-Turing thesis
  Definition of computability.

These results shook the foundations
of mathematics and logic.
""")

# ANALOGY
print("=== Analogy: The Oracle's Limits ===")
print("""
Imagine an oracle that answers any question.

Question: "Will this program halt?"

Oracle's answer: "I can't tell you."

Why not?
  Because no oracle can answer that question
  for ALL programs.

This is the halting problem.

=== Another Analogy: The Perfect Doctor ===")

A doctor who can diagnose any disease?

Problem: Some diseases are undetectable.
  - Not because we lack technology.
  - But because the information isn't there.

Similarly:
  Some program properties are undecidable.
  Not because we lack algorithms.
  But because no algorithm exists.

=== The Map of Decidability ===

Think of all problems as a map:

  ┌─────────────────────────────────────┐
  │ Undecidable                         │
  │  ┌───────────────────────────────┐  │
  │  │ Recognizable                  │  │
  │  │  ┌─────────────────────────┐  │  │
  │  │  │ Decidable               │  │  │
  │  │  │                         │  │  │
  │  │  └─────────────────────────┘  │  │
  │  └───────────────────────────────┘  │
  └─────────────────────────────────────┘

We want to know where our problem lies.
""")

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

Decidability theory answers:
  "What can computers do?"

Answer:
  - Many things (decidable problems)
  - Some things with limitations (recognizable)
  - Some things impossible (undecidable)

Key results:
  1. HALT is undecidable
  2. Rice's theorem: all semantic properties undecidable
  3. Reductions: transfer undecidability
  4. Decidable = Recognizable ∩ Co-recognizable

=== The Landscape ===

DECIDABLE:
  - DFA/NFA problems
  - CFL membership, emptiness, finiteness
  - CSL membership
  - Integer arithmetic (Presburger)
  - Many practical problems

RECOGNIZABLE (not decidable):
  - HALT
  - TM membership
  - PCP
  - Hilbert's 10th

UNDECIDABLE (not recognizable):
  - HALT^c (complement of halting)
  - EQUIVALENCE (sometimes)
  - Many semantic properties

=== Practical Impact ===

Despite undecidability, we can:
  - Solve specific instances
  - Use approximations
  - Restrict to decidable subclasses
  - Use heuristics
  - Combine human insight with automation

Key insight:
  Undecidability is not pessimism.
  It's a fundamental fact about computation.
  It shapes what we can know and do.
""")

# DECIDABILITY IN CODE
print("=== Decidability in Code ===")

def decidable_example(n):
    """
    A decidable problem: Is n prime?
    Always halts, correct answer.
    """
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True


def recognizable_example(program, input_data, max_steps=1000):
    """
    A recognizable problem: Does program halt on input?
    Simulate for max_steps.
    If halts: accept.
    If not: may loop (we timeout).
    """
    # Simulate for max_steps
    # This is a recognizer, not a decider
    # We can't tell if it's looping or just slow
    return False  # placeholder


def undecidable_example():
    """
    Undecidable: Does program P halt on input w?
    No algorithm can solve this.
    """
    raise NotImplementedError("Halting problem is undecidable!")


print("Decidable: Is 17 prime?")
print(f"  {decidable_example(17)}")

print("\nRecognizable: Does program halt?")
print("  Simulate — but may loop.")

print("\nUndecidable: Halting problem")
print("  No algorithm exists.")

print("""
=== Key Observation ===

If you can write a program that ALWAYS HALTS
and gives the correct answer, the problem is decidable.

If your program might loop, it's a recognizer.

If no program can solve it, it's undecidable.
""")

✅ Decidable Problems

🎯 Problems We Can Solve

A decidable problem has an algorithm that always halts and gives the correct answer. These are the problems we can solve with computers.

Decidable Problems

Definition: TM always halts. Also called: Recursive. Examples: DFA membership, CFL membership, CSL membership. Closure: Union, intersection, complement. Practical: Most real-world problems. Hierarchy: Smallest class.

✅ Always halts🔄 Recursive📊 Closed under ∩, ¬💻 Practical

# Decidable Problems
print("=" * 60)
print("DECIDABLE PROBLEMS")
print("=" * 60)

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

A language L is DECIDABLE if:
  There exists a TM D such that:
    - D(w) = accept if w ∈ L
    - D(w) = reject if w ∉ L
    - D always halts

D is called a DECIDER for L.

Also called: RECURSIVE.

=== Examples by Machine Type ===

DFA:
  ✓ Membership: O(n)
  ✓ Emptiness: BFS
  ✓ Equivalence: minimize
  ✓ Universality: check complement empty
  ✓ Finiteness: check cycles

NFA:
  ✓ All of the above (convert to DFA)

CFG:
  ✓ Membership: CYK O(n³)
  ✓ Emptiness: generating symbols
  ✓ Finiteness: check cycles
  ✗ Equivalence: undecidable
  ✗ Ambiguity: undecidable
  ✗ Universality: undecidable

DPDA:
  ✓ Membership: O(n)
  ✓ Emptiness: decidable
  ✓ Equivalence: decidable
  ✓ Universality: decidable

LBA (CSL):
  ✓ Membership: PSPACE
  ✗ Emptiness: undecidable
  ✗ Equivalence: undecidable

TM:
  ✗ Membership: undecidable
  ✗ Almost everything: undecidable

=== Decidable Problems in Practice ===

1. INTEGER ARITHMETIC (Presburger)
   - Addition, comparison
   - Decidable (but expensive)

2. REAL ARITHMETIC (Tarski)
   - Polynomials over reals
   - Decidable (very expensive)

3. GRAPH PROBLEMS
   - Reachability: decidable
   - Shortest path: decidable
   - Connectivity: decidable

4. STRING PROBLEMS
   - Pattern matching: decidable
   - Regex matching: decidable
   - Parsing: decidable (Type 2)

5. LOGIC
   - Propositional logic: decidable
   - First-order logic: undecidable
   - Temporal logic: decidable (finite)

=== Why Decidable Problems Matter ===

They're the problems we CAN solve:
  - With algorithms
  - With guaranteed correctness
  - With guaranteed termination

This is the foundation of:
  - Programming
  - Algorithm design
  - Software engineering
  - Computer science
""")

# DECIDABLE PROBLEMS IN CODE
print("=== Decidable Problems in Code ===")

class DFA:
    """A simple DFA."""
    def __init__(self, states, alphabet, delta, q0, F):
        self.Q = states
        self.Sigma = alphabet
        self.delta = delta
        self.q0 = q0
        self.F = F
    
    def accepts(self, w):
        state = self.q0
        for symbol in w:
            if symbol not in self.Sigma:
                return False
            state = self.delta[(state, symbol)]
        return state in self.F
    
    def is_empty(self):
        """Decidable: Is L(M) empty?"""
        from collections import deque
        visited = {self.q0}
        queue = deque([self.q0])
        while queue:
            state = queue.popleft()
            if state in self.F:
                return False
            for symbol in self.Sigma:
                next_state = self.delta[(state, symbol)]
                if next_state not in visited:
                    visited.add(next_state)
                    queue.append(next_state)
        return True
    
    def is_universal(self):
        """Decidable: Is L(M) = Σ*?"""
        # Complement empty?
        comp = DFA(
            self.Q, self.Sigma,
            self.delta, self.q0,
            self.Q - self.F
        )
        return comp.is_empty()
    
    def is_finite(self):
        """Decidable: Is L(M) finite?"""
        # Check for cycles reachable from start
        # and co-reachable to accept
        from collections import deque
        
        # Find states that can reach accept
        can_reach_accept = set()
        reverse = {s: set() for s in self.Q}
        for (q, a), nq in self.delta.items():
            reverse[nq].add(q)
        
        queue = deque(self.F)
        while queue:
            state = queue.popleft()
            if state not in can_reach_accept:
                can_reach_accept.add(state)
                for prev in reverse.get(state, set()):
                    if prev not in can_reach_accept:
                        queue.append(prev)
        
        # DFS to detect cycle
        WHITE, GRAY, BLACK = 0, 1, 2
        color = {s: WHITE for s in self.Q}
        
        def has_cycle(state):
            color[state] = GRAY
            for symbol in self.Sigma:
                next_state = self.delta[(state, symbol)]
                if next_state not in can_reach_accept:
                    continue
                if color[next_state] == GRAY:
                    return True
                if color[next_state] == WHITE:
                    if has_cycle(next_state):
                        return True
            color[state] = BLACK
            return False
        
        return not has_cycle(self.q0)


# Example
dfa = DFA(
    states={'q0', 'q1', 'q2'},
    alphabet={'a', 'b'},
    delta={
        ('q0', 'a'): 'q1',
        ('q0', 'b'): 'q0',
        ('q1', 'a'): 'q1',
        ('q1', 'b'): 'q2',
        ('q2', 'a'): 'q1',
        ('q2', 'b'): 'q0',
    },
    q0='q0',
    F={'q2'}
)

print("DFA for strings ending in 'ab':")
print(f"  Membership 'aab': {dfa.accepts('aab')}")
print(f"  Empty? {dfa.is_empty()}")
print(f"  Universal? {dfa.is_universal()}")
print(f"  Finite? {dfa.is_finite()}")

# CLOSURE
print("""
=== Closure Properties of Decidable Languages ===

Decidable languages are CLOSED under:
  ✓ Union
  ✓ Intersection
  ✓ Complement
  ✓ Concatenation
  ✓ Kleene star
  ✓ Reversal
  ✓ Homomorphism
  ✓ Inverse homomorphism

PROOF IDEA:
  For union: run both deciders, accept if either accepts.
  For intersection: run both deciders, accept if both accept.
  For complement: swap accept/reject.

All constructions preserve decidability.
""")

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

Decidable:
  - TM always halts
  - Correct yes/no answer
  - Recursive

Examples:
  - DFA/NFA membership, emptiness, equivalence
  - CFL membership, emptiness, finiteness
  - CSL membership
  - Integer arithmetic
  - Propositional logic

Closure:
  - Closed under union, intersection, complement
  - Closed under concatenation, star, reversal

Key insight:
  Decidable problems are the ones we CAN solve.
  They form the smallest class in the hierarchy.
  Most practical problems are decidable.
""")

🔄 Recognizable Problems

🎯 Problems We Can Confirm

A recognizable problem (also called recursively enumerable) has an algorithm that halts and accepts if the answer is "yes," but may loop forever if the answer is "no." We can confirm "yes" but not "no."

Recognizable Problems

Definition: TM accepts if w ∈ L, may loop if w ∉ L. Also called: Recursively enumerable (r.e.). Examples: HALT, TM membership, PCP. Closure: Union, intersection (not complement). Hierarchy: Between decidable and all languages. Co-recognizable: Complement is recognizable.

🔄 May loop✅ Confirms "yes"❌ Can't confirm "no"r.e.

# Recognizable Problems
print("=" * 60)
print("RECOGNIZABLE PROBLEMS")
print("=" * 60)

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

A language L is RECOGNIZABLE if:
  There exists a TM R such that:
    - R(w) = accept if w ∈ L
    - R(w) = loop or reject if w ∉ L

R is called a RECOGNIZER for L.

Also called: RECURSIVELY ENUMERABLE (r.e.).

=== Key Difference from Decidable ===

Decidable:
  - Always halts
  - Both "yes" and "no" are reliable

Recognizable:
  - May loop on "no" instances
  - "Yes" answers are reliable
  - "No" answers may never come

=== Visual ===

  Recognizer R:
    w ∈ L → accept (eventually)
    w ∉ L → loop or reject (maybe forever)

  Decider D:
    w ∈ L → accept (always halts)
    w ∉ L → reject (always halts)

=== Examples ===

1. HALT = { (M, w) | M halts on w }
   Recognizer: simulate M on w.
   If M halts, accept.
   If M loops, we loop.
   So HALT is recognizable.

2. TM_MEMBERSHIP = { (M, w) | w ∈ L(M) }
   Same as HALT (essentially).
   Recognizable.

3. PCP (Post Correspondence Problem)
   Recognizable (search for solution).
   Not decidable.

4. HILBERT_10
   Recognizable (search for roots).
   Not decidable.

=== Co-Recognizable ===

A language L is CO-RECOGNIZABLE if L^c is recognizable.

Examples:
  - HALT^c is co-recognizable (not recognizable)
  - Most undecidable problems are either
    recognizable, co-recognizable, or neither

=== The Relationship ===

Decidable = Recognizable ∩ Co-recognizable

Proof:
  (→) Decidable → both recognizable.
  (←) If L and L^c are recognizable:
      Run both recognizers in parallel (dovetailing).
      One will accept.
      This decides L. ∎
""")

# RECOGNIZABLE IN CODE
print("=== Recognizable in Code ===")

class TM:
    """Simple TM for demonstration."""
    def __init__(self, transitions, q0, q_accept, q_reject):
        self.delta = transitions
        self.q0 = q0
        self.q_accept = q_accept
        self.q_reject = q_reject
    
    def simulate(self, w, max_steps=1000):
        """Simulate TM. Returns (halted, accepted)."""
        tape = list(w) + ['_'] * 100
        head = 0
        state = self.q0
        
        for step in range(max_steps):
            if state == self.q_accept:
                return True, True
            if state == self.q_reject:
                return True, False
            
            symbol = tape[head] if head < len(tape) else '_'
            if (state, symbol) not in self.delta:
                return True, False
            
            ns, wr, d = self.delta[(state, symbol)]
            tape[head] = wr
            
            if d == 'R':
                head += 1
                if head >= len(tape):
                    tape.extend(['_'] * 100)
            else:
                head = max(0, head - 1)
            
            state = ns
        
        return False, False  # didn't halt (timeout)


def halt_recognizer(M, w, max_steps=1000):
    """
    Recognizer for HALT.
    Returns True if M halts on w.
    May return False if M doesn't halt within max_steps.
    """
    halted, accepted = M.simulate(w, max_steps)
    return halted


# Example: TM that halts on all inputs
tm = TM(
    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("HALT Recognizer:")
for w in ['', '0', '101', '111']:
    result = halt_recognizer(tm, w)
    print(f"  M halts on '{w}': {result}")

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

To decide L given recognizers for L and L^c:

  def decide(w):
      for step in range(infinity):
          # Run R1 for step steps
          if R1(w, step) == accept:
              return accept
          # Run R2 for step steps
          if R2(w, step) == accept:
              return reject

This is DOVETAILING:
  - Run both recognizers in parallel
  - Interleave their steps
  - One will eventually accept
  - So we always get an answer

Time complexity:
  - If R1 accepts in t1 steps, we find it in O(t1)
  - If R2 accepts in t2 steps, we find it in O(t2)
  - Worst case: max(t1, t2) × constant

This works because:
  - w ∈ L or w ∈ L^c (exclusive)
  - One recognizer accepts
  - Dovetailing finds it
""")

# CLOSURE
print("""
=== Closure Properties ===

Recognizable languages are CLOSED under:
  ✓ Union: Run both in parallel, accept if either accepts.
  ✓ Intersection: Run both, accept if both accept.
  ✗ Complement: NOT closed!
  ✓ Concatenation
  ✓ Kleene star
  ✓ Reversal
  ✓ Homomorphism
  ✓ Inverse homomorphism

Why NOT complement?
  If L is r.e., L^c may not be r.e.
  Example: HALT is r.e., HALT^c is not.

=== The Hierarchy ===

  Decidable
     ↓ (strict)
  Recognizable
     ↓ (strict)
  All Languages

Examples:
  DFA membership: decidable
  HALT: recognizable, not decidable
  HALT^c: not recognizable

=== Why This Matters ===

Recognizable problems are "half-solvable":
  - We can confirm "yes"
  - We can't confirm "no"

This has practical implications:
  - We can search for solutions
  - We can't prove absence of solutions
  - May run forever
""")

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

Recognizable:
  - TM accepts if w ∈ L
  - May loop if w ∉ L
  - Recursively enumerable

Examples:
  - HALT
  - TM membership
  - PCP
  - Hilbert's 10th

Closure:
  - Closed under union, intersection
  - NOT closed under complement
  - Closed under concatenation, star

Key relationship:
  Decidable = Recognizable ∩ Co-recognizable

Key insight:
  Recognizable is between decidable and all languages.
  We can confirm "yes" but not "no."
  This is a fundamental limitation.
""")

❌ Undecidable Problems

🎯 Problems We Cannot Solve

An undecidable problem has no algorithm that always halts and gives the correct answer. These are the fundamental limits of computation.

Undecidable Problems

Definition: No decider exists. May be: Recognizable or not. Examples: HALT, EQUIVALENCE, PCP. Proof: Diagonalization, reductions. Implications: No perfect tools. Workarounds: Approximations, heuristics.

❌ No decider🛑 Halting problem📊 Rice's theorem🔗 Reductions

# Undecidable Problems
print("=" * 60)
print("UNDECIDABLE PROBLEMS")
print("=" * 60)

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

A problem is UNDECIDABLE if:
  No TM decides it.
  No algorithm always halts with correct answer.

May be:
  - Recognizable but not decidable (HALT)
  - Not recognizable (HALT^c)
  - Neither

=== Classic Undecidable Problems ===

1. HALT = { (M, w) | M halts on w }
   Undecidable (Turing, 1936)

2. EQUIVALENCE = { (M1, M2) | L(M1) = L(M2) }
   Undecidable (reduction from HALT)

3. EMPTINESS = { M | L(M) = ∅ }
   Undecidable (reduction from HALT)

4. REGULARITY = { M | L(M) is regular }
   Undecidable (reduction from HALT)

5. PCP (Post Correspondence Problem)
   Undecidable (Post, 1946)

6. HILBERT_10 (Diophantine equations)
   Undecidable (Matiyasevich, 1970)

7. WANG_TILES
   Undecidable (Berger, 1966)

8. MATRIX_MORTALITY
   Undecidable

9. CFG_EQUIVALENCE
   Undecidable

10. CFG_AMBIGUITY
    Undecidable

=== Why So Many? ===

Rice's theorem:
  Every non-trivial semantic property
  of TMs is undecidable.

Since almost everything we care about
is a semantic property, almost everything
is undecidable!

=== What IS Decidable? ===

For TMs:
  - Syntactic properties (about code)
  - Specific instances (sometimes)
  - Restricted classes

For other models:
  - DFA: everything
  - CFL: membership, emptiness
  - CSL: membership
  - TM: almost nothing
""")

# UNDECIDABLE PROBLEMS IN CODE
print("=== Undecidable Problems in Code ===")

print("""
Pseudo-code for undecidable problems:

  def halt(M, w):
      # Does M halt on w?
      # UNDECIDABLE: no algorithm exists!
      raise NotImplementedError("Halting problem is undecidable!")
  
  def equivalence(M1, M2):
      # Is L(M1) = L(M2)?
      # UNDECIDABLE!
      raise NotImplementedError("Equivalence is undecidable!")
  
  def emptiness(M):
      # Is L(M) = empty?
      # UNDECIDABLE!
      raise NotImplementedError("Emptiness is undecidable!")
  
  def regularity(M):
      # Is L(M) regular?
      # UNDECIDABLE!
      raise NotImplementedError("Regularity is undecidable!")

These cannot be implemented.
No algorithm exists.
""")

# THE PATTERN
print("""
=== The Pattern ===

Almost every non-trivial question about
program behavior is undecidable:

  - Does program P halt?
  - Does program P output 42?
  - Does program P ever access file X?
  - Is program P equivalent to Q?
  - Does program P have a bug?
  - Is program P's output sorted?
  - Does program P terminate?
  - Is program P's language regular?
  - Is program P's language empty?
  - Does program P accept at least 5 strings?

ALL undecidable!

=== Why? ===

Rice's theorem:
  Every non-trivial semantic property
  of TMs is undecidable.

Semantic = about L(M), not M's code.
Non-trivial = some TMs have it, some don't.

Almost everything interesting is semantic.
So almost everything is undecidable.

=== The Silver Lining ===

We CAN decide:
  - Syntactic properties (about code)
  - Specific instances (with insight)
  - Restricted classes
  - Approximations

So we can still:
  - Build useful tools
  - Solve practical problems
  - Make progress

Just not in full generality.
""")

# IMPLICATIONS
print("""
=== Practical Implications ===

1. NO PERFECT DEBUGGER
   Can't detect all infinite loops.

2. NO PERFECT VIRUS DETECTOR
   Can't detect all malicious programs.

3. NO PERFECT OPTIMIZER
   Can't optimize all programs optimally.

4. NO AUTOMATIC VERIFIER
   Can't verify all programs automatically.

5. NO GENERAL THEOREM PROVER
   Can't prove all theorems automatically.

=== Workarounds ===

1. APPROXIMATION
   - Static analysis (may be conservative)
   - Bug finding (may have false positives)

2. RESTRICTIONS
   - Finite-state programs
   - Bounded loops
   - Typed programs

3. HUMAN INSIGHT
   - Proofs for specific programs
   - Testing
   - Code review

4. HEURISTICS
   - Local search
   - Simulated annealing
   - Machine learning

=== The Trade-off ===

Soundness: No false positives
Completeness: No false negatives

For undecidable problems:
  Can't have both!
  
Static analyzers: sound but incomplete
Bug finders: complete but unsound

This is a fundamental trade-off.
""")

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

Undecidable:
  - No decider exists
  - May be recognizable or not
  - Fundamental limits of computation

Examples:
  - HALT
  - EQUIVALENCE
  - EMPTINESS
  - REGULARITY
  - PCP
  - Hilbert's 10th

Rice's theorem:
  Every non-trivial semantic property
  is undecidable.

Implications:
  - No perfect tools
  - Must use approximations
  - Human insight matters

Key insight:
  Undecidability is a fundamental mathematical limit.
  Not an engineering problem.
  No future technology can overcome it.
""")

🛑 The Halting Problem

🎯 The Most Famous Undecidable Problem

The halting problem asks: given a program and its input, will the program eventually halt or run forever? Turing proved in 1936 that no algorithm can solve this problem in general.

Halting Problem Facts

Problem: Does M halt on w? Undecidable: No algorithm exists. Proof: Diagonalization. Recognizable: Yes (simulate). Not co-recognizable: HALT^c not r.e. Implications: Many problems undecidable.

🛑 Halting❌ Undecidable📐 Diagonal🔗 Reductions

# The Halting Problem
print("=" * 60)
print("THE HALTING PROBLEM")
print("=" * 60)

print("""
=== Problem Statement ===

HALT = { (M, w) | M is a TM and M halts on input w }

Question: Is HALT decidable?

Answer: NO! (Turing, 1936)

=== Why It's Shocking ===

Before Turing, mathematicians thought:
  - Every well-defined problem is solvable
  - We just need to find the algorithm
  - Hilbert's program: find a procedure for everything

Turing showed:
  - Some problems have NO algorithm
  - Not a matter of cleverness
  - Fundamental mathematical limit

=== Proof (Diagonalization) ===

Suppose HALT is decidable.
Then there's a TM H that decides HALT:
  H(M, w) = "accept" if M halts on w
          = "reject" if M loops on w

Construct a new TM D:
  D(M) = 
    if H(M, M) accepts: loop forever
    if H(M, M) rejects: halt and accept

Now 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, H cannot exist.
HALT is undecidable. ∎
""")

# DIAGONALIZATION
print("""
=== Diagonalization Explained ===

Imagine a table:
  Rows: Turing machines M₁, M₂, M₃, ...
  Columns: inputs w₁, w₂, w₃, ...
  
  Cell (i, j): Does Mᵢ halt on wⱼ?
    H = halts, L = loops

         w₁   w₂   w₃   w₄  ...
    M₁   H    L    H    H   ...
    M₂   L    L    H    L   ...
    M₃   H    H    L    H   ...
    M₄   L    H    H    L   ...
    ...

Now define D:
  D(Mᵢ) = opposite of Mᵢ(Mᵢ)
  
  D(wᵢ) halts iff Mᵢ(wᵢ) loops.

The DIAGONAL:
         w₁   w₂   w₃   w₄  ...
    M₁   H    L    H    H   ...
    M₂   L    L    H    L   ...
    M₃   H    H    L    H   ...
    M₄   L    H    H    L   ...
    ...
    D    L    H    H    H   ...  ← opposite of diagonal

D is a TM (we constructed it).
So D = Mₖ for some k (all TMs are in the list).

But D(wₖ) = opposite of Mₖ(wₖ) = opposite of D(wₖ).
Contradiction!

Therefore, HALT is undecidable. ∎
""")

# RECOGNIZABLE
print("""
=== HALT is Recognizable ===

Proof:
  Build recognizer R for HALT:
    R(⟨M, w⟩):
      1. Simulate M on w
      2. If M halts, accept
      3. If M loops, R loops
  
  R accepts ⟨M, w⟩ iff M halts on w.
  So R recognizes HALT.
  HALT is recursively enumerable.

=== HALT is NOT Decidable ===

Proof:
  By diagonalization (previous slide).
  No TM can decide HALT.
  So HALT is not recursive.

=== HALT^c is NOT Recognizable ===

Proof:
  Suppose HALT^c is recognizable.
  Then HALT is co-recognizable.
  HALT is also recognizable.
  So HALT is decidable.
  Contradiction!
  Therefore, HALT^c is not recognizable.

=== The Hierarchy ===

  Decidable
     ↓
  Recognizable (HALT)
     ↓
  Co-recognizable (HALT^c)
     ↓
  All Languages
""")

# IMPLICATIONS
print("""
=== Implications ===

1. NO PERFECT DEBUGGER
   Can't detect all infinite loops.

2. NO PERFECT VIRUS DETECTOR
   Can't detect all malicious programs.

3. NO PERFECT OPTIMIZER
   Can't optimize all programs optimally.

4. NO AUTOMATIC VERIFIER
   Can't verify all programs automatically.

5. NO GENERAL THEOREM PROVER
   Can't prove all theorems automatically.

6. AI LIMITS
   No AI can solve the halting problem.
   Even superintelligent AI.

=== Practical Workarounds ===

1. TIMEOUTS
   Run program for N seconds.
   If not done, assume loop.

2. BOUNDED MODEL CHECKING
   Check properties up to depth k.

3. ABSTRACT INTERPRETATION
   Approximate program behavior.

4. TESTING
   Run on specific inputs.

5. HUMAN INSIGHT
   Expert review, proofs.

=== Why It Matters ===

The halting problem:
  - First undecidable problem
  - Foundation of computability
  - Source of many reductions
  - Shows limits of computation
  - Fundamental, not engineering
""")

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

Halting Problem:
  HALT = { (M, w) | M halts on w }
  UNDECIDABLE

Proof:
  Diagonalization.
  Assume H decides HALT.
  Construct D: D(M) loops iff H(M,M) accepts.
  Run D on D: contradiction.

Properties:
  - Recognizable (simulate M on w)
  - Not decidable
  - Not co-recognizable

Implications:
  - No perfect debugger
  - No perfect virus detector
  - No perfect optimizer
  - No automatic verifier

Key insight:
  Undecidability is a fundamental mathematical limit.
  Not an engineering problem.
  No future technology can overcome it.
""")

🔗 Reductions

🎯 Proving Undecidability

Reduction is the technique of showing that one problem is at least as hard as another. If A reduces to B, and A is undecidable, then B is also undecidable. It's the most powerful tool for proving undecidability.

Reduction Technique

Definition: A ≤ B if A can be solved using B. Contrapositive: A undecidable, A ≤ B ⟹ B undecidable. Mapping: Computable function f. Turing: Oracle for B. Template: Assume B decidable, use to decide A. Source: Usually HALT.

📉 A ≤ B🔗 Reduction❌ Undecidable✅ Decidable

# Reductions
print("=" * 60)
print("REDUCTIONS")
print("=" * 60)

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

A reduces to B (written A ≤ B) if:
  A solution to B gives a solution to A.
  
More formally:
  There's a computable function f such that:
    w ∈ A ⟺ f(w) ∈ B

f is called the REDUCTION.

=== Intuition ===

A ≤ B means:
  "A is no harder than B"
  "If we can solve B, we can solve A"
  "B is at least as hard as A"

=== Uses ===

1. PROVING UNDECIDABILITY
   If A is undecidable and A ≤ B,
   then B is undecidable.
   
2. PROVING DECIDABILITY
   If B is decidable and A ≤ B,
   then A is decidable.

=== Proof Template ===

To prove B is undecidable by reduction from A:

1. KNOWN UNDECIDABLE
   A is known to be undecidable.
   (Usually HALT)

2. ASSUME B DECIDABLE
   Suppose there's a decider D_B for B.

3. CONSTRUCT DECIDER FOR A
   Show how to decide A using D_B:
     Given input x for A:
       1. Compute f(x) (the reduction)
       2. Run D_B on f(x)
       3. Return D_B's answer

4. CONTRADICTION
   This would decide A, but A is undecidable.
   Contradiction.
   Therefore B is undecidable. ∎
""")

# EXAMPLE: HALT_EMPTY
print("=== Example: Reduce HALT to HALT_EMPTY ===")
print("""
Problem: Prove HALT_EMPTY is undecidable.

HALT_EMPTY = { M | M halts on ε }

Reduction from HALT:
  Given (M, w), construct M' such that:
    M' halts on ε ⟺ M halts on w

Construction of M':
  M' on input x:
    1. Ignore x
    2. Simulate M on w
    3. If M halts, M' halts (accepts)

  (M' doesn't even look at its input!)

Now:
  M halts on w → M' halts on ε → M' ∈ HALT_EMPTY
  M loops on w → M' loops on ε → M' ∉ HALT_EMPTY

So:
  (M, w) ∈ HALT ⟺ M' ∈ HALT_EMPTY

This is a mapping reduction: f(M, w) = M'.

Since HALT is undecidable, HALT_EMPTY is undecidable. ∎
""")

# EXAMPLE: EQUIVALENCE
print("=== Example: Reduce HALT to EQUIVALENCE ===")
print("""
Problem: Prove EQUIVALENCE is undecidable.

EQUIVALENCE = { (M1, M2) | L(M1) = L(M2) }

Reduction from HALT:
  Given (M, w), construct (M1, M2) such that:
    L(M1) = L(M2) ⟺ M does NOT halt on w

Construction:
  M1 = TM that always rejects (L(M1) = ∅)
  M2 = TM that:
    1. Simulates M on w
    2. If M halts, accepts
    3. If M loops, loops

  L(M2) = ∅ if M loops on w
  L(M2) = Σ* if M halts on w

Now:
  M halts on w → L(M2) = Σ* ≠ ∅ = L(M1)
                → (M1, M2) ∉ EQUIVALENCE
  M loops on w → L(M2) = ∅ = L(M1)
                → (M1, M2) ∈ EQUIVALENCE

So:
  (M, w) ∈ HALT ⟺ (M1, M2) ∉ EQUIVALENCE

Therefore, EQUIVALENCE is undecidable. ∎
""")

# COMMON REDUCTIONS
print("""
=== Classic Reductions ===

1. HALT ≤ HALT_EMPTY
   f(M, w) = M' that ignores input, runs M on w.

2. HALT ≤ HALT_ALL
   f(M, w) = M' that runs M on w on all inputs.

3. HALT ≤ EQUIVALENCE
   f(M, w) = (M1, M2) where:
     M1 always rejects
     M2 rejects iff M halts on w

4. HALT ≤ REGULARITY
   f(M, w) = M' where:
     L(M') = {0^n 1^n} if M halts on w
     L(M') = ∅ otherwise

5. HALT ≤ PCP
   Complex encoding.

6. HALT ≤ HILBERT_10
   Diophantine encoding.

=== The Pattern ===

Most undecidability proofs:
  1. Start with HALT (known undecidable)
  2. Reduce to the new problem
  3. Conclude new problem undecidable

This is why HALT is so important:
  It's the "seed" for all undecidability proofs.
""")

# PROPERTIES
print("""
=== Properties of Reductions ===

1. TRANSITIVE
   A ≤ B and B ≤ C ⟹ A ≤ C

2. REFLEXIVE
   A ≤ A

3. COMPATIBLE WITH COMPLEMENT
   A ≤_m B ⟹ A^c ≤_m B^c

4. PRESERVES DECIDABILITY
   B decidable, A ≤ B ⟹ A decidable

5. PRESERVES RECOGNIZABILITY
   B recognizable, A ≤_m B ⟹ A recognizable

6. TRANSFERS UNDECIDABILITY
   A undecidable, A ≤ B ⟹ B undecidable

7. TRANSFERS NON-RECOGNIZABILITY
   A not recognizable, A ≤_m B ⟹ B not recognizable

=== Why This Matters ===

Reductions let us:
  - Transfer hardness
  - Classify problems
  - Prove undecidability
  - Prove decidability
  - Build hierarchies

They're the most powerful tool
in computability theory.
""")

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

Reduction:
  A ≤ B means A is no harder than B.

Mapping reduction:
  A ≤_m B via computable f: w ∈ A ⟺ f(w) ∈ B.

Turing reduction:
  A ≤_T B via oracle for B.

Uses:
  - Prove undecidability
  - Prove decidability
  - Classify problems

Proof template:
  Assume B decidable.
  Use decider for B to decide A.
  Contradiction (A undecidable).
  Therefore B undecidable.

Key insight:
  Reductions let us transfer undecidability
  from known problems to new ones.
  This is the most powerful tool in
  computability theory.
""")

📊 Rice's Theorem

🎯 All Semantic Properties Are Undecidable

Rice's theorem states that every non-trivial semantic property of Turing machines is undecidable. It generalizes the halting problem and shows that undecidability is pervasive.

Rice's Theorem

Semantic: About L(M), not M. Non-trivial: Some M have it, some don't. Undecidable: No decider exists. Examples: Emptiness, universality, regularity. Syntactic: About M's code — decidable. Impact: Pervasive undecidability.

📊 Semantic❌ Non-trivial🛑 Undecidable📝 Syntactic

# Rice's Theorem
print("=" * 60)
print("RICE'S THEOREM")
print("=" * 60)

print("""
=== Statement ===

Every non-trivial semantic property of
Turing machines is undecidable.

=== Definitions ===

PROPERTY P:
  A set of recursively enumerable languages.
  
  M "has property P" if L(M) ∈ P.

SEMANTIC:
  Depends only on L(M), not on M's code.
  If L(M1) = L(M2), then either both have P
  or neither has P.

NON-TRIVIAL:
  P ≠ ∅ and P ≠ all r.e. languages.
  Some TMs have P, some don't.

=== Examples of Undecidable Properties ===

1. L(M) = ∅
2. L(M) = Σ*
3. L(M) is finite
4. L(M) is infinite
5. L(M) is regular
6. L(M) is context-free
7. w ∈ L(M) for a specific w
8. L(M) contains at least 5 strings
9. L(M) contains "hello"
10. L(M) is empty or Σ*

All these are undecidable!

=== Examples of Decidable Properties ===

1. M has 5 states
2. M has a transition from q1 to q2
3. M uses exactly 3 tape symbols
4. M has an accept state
5. M's transition function is total

All these are DECIDABLE!
(Because they're SYNTACTIC, not semantic.)

=== Why the Difference? ===

Syntactic properties:
  - About M's code
  - We can inspect the code
  - Decidable (often trivially)

Semantic properties:
  - About M's behavior (L(M))
  - Can't inspect behavior directly
  - Undecidable (Rice's theorem)

=== Proof Sketch ===

Let P be a non-trivial semantic property.

Case 1: ∅ ∉ P
  Since P is non-trivial, some language L has P.
  Let M_L be a TM for L.
  
  Reduce HALT to P:
    Given (M, w):
    Construct M' that:
      1. Ignores its input
      2. Simulates M on w
      3. If M halts on w, simulates M_L on input
      4. Accepts if M_L accepts
    
    Then:
      M halts on w → L(M') = L → L(M') has P
      M loops on w → L(M') = ∅ → L(M') doesn't have P
    
    So (M, w) ∈ HALT ⟺ M' has P.
    If P were decidable, HALT would be decidable.
    Contradiction. So P is undecidable.

Case 2: ∅ ∈ P
  Similar, using complement of P.
""")

# IMPLICATIONS
print("""
=== Implications of Rice's Theorem ===

Rice's theorem shows that undecidability is PERVASIVE.

Almost every interesting question about
program behavior is undecidable:

1. Does program P output 42?
2. Does program P ever access file X?
3. Is program P equivalent to program Q?
4. Does program P have a bug?
5. Is program P's output always positive?
6. Does program P terminate on all inputs?
7. Does program P use at most 1GB of memory?
8. Is program P's output sorted?
9. Does program P ever divide by zero?
10. Is program P's output deterministic?

All undecidable by Rice's theorem!

=== What IS Decidable? ===

Only syntactic properties:
  - About the code, not the behavior
  - Can be checked by inspection
  - Examples:
    * Does M have 5 states?
    * Does M use symbol 'X'?
    * Is M's transition function total?
    * Does M have an unreachable state?

And specific instances:
  - For specific programs, we can often prove properties
  - But not for ALL programs (Rice's theorem)
  - Human insight matters

=== The Power of Rice's Theorem ===

Instead of proving each problem undecidable:
  1. Check if property is semantic
  2. Check if it's non-trivial
  3. Conclude undecidable

This saves enormous effort!
""")

# APPLICATIONS
print("""
=== Applying Rice's Theorem ===

1. "Is L(M) empty?"
   - Semantic? Yes (about L(M)).
   - Non-trivial? Yes.
   - Undecidable! ✓

2. "Is L(M) regular?"
   - Semantic? Yes.
   - Non-trivial? Yes.
   - Undecidable! ✓

3. "Does M have 5 states?"
   - Semantic? No (about M's code).
   - Decidable! ✓

4. "Does M accept ε?"
   - Semantic? Yes (about L(M)).
   - Non-trivial? Yes.
   - Undecidable! ✓

5. "Is M's start state q0?"
   - Semantic? No (syntactic).
   - Decidable! ✓

6. "Is L(M) = Σ*?"
   - Semantic? Yes.
   - Non-trivial? Yes.
   - Undecidable! ✓

7. "Does M use at most 10 states?"
   - Semantic? No (syntactic).
   - Decidable! ✓

8. "Is L(M) infinite?"
   - Semantic? Yes.
   - Non-trivial? Yes.
   - Undecidable! ✓

=== The Pattern ===

If the property is about L(M):
  → Usually undecidable (Rice's theorem).

If the property is about M's code:
  → Usually decidable (syntactic inspection).
""")

# PROOF IN CODE
print("""
=== Proof of Rice's Theorem in Code ===

Pseudo-code for the reduction:

  def reduce_halt_to_P(M, w, P):
      '''Construct M' from (M, w) such that
         M' has property P iff M halts on w.'''
      
      def M_prime(x):
          # Simulate M on w
          if halt(M, w):
              # M halts: simulate M_L on x
              return M_L(x)
          else:
              # M loops: loop forever
              while True: pass
      
      return M_prime
  
  # Now:
  #   M halts on w  ⟺ L(M_prime) = L ∈ P
  #   M loops on w  ⟺ L(M_prime) = ∅ ∉ P (Case 1)
  #
  # So (M, w) ∈ HALT ⟺ M_prime has P
  #
  # If P were decidable:
  #   Decide HALT by: compute M_prime, run decider on M_prime.
  #   But HALT is undecidable. Contradiction.
  #   Therefore P is undecidable.
""")

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

Rice's Theorem:
  Every non-trivial semantic property
  of Turing machines is undecidable.

Semantic:
  About L(M), not M's code.

Non-trivial:
  Some TMs have it, some don't.

Examples:
  - L(M) = ∅
  - L(M) = Σ*
  - L(M) is finite
  - L(M) is regular
  - w ∈ L(M)
  - L(M) contains "hello"

All undecidable.

Decidable properties:
  - Syntactic (about code)
  - Specific instances (with human insight)

Key insight:
  Rice's theorem generalizes the halting problem.
  It shows undecidability is PERVASIVE.
  Almost every interesting question about
  program behavior is undecidable.

Practical impact:
  - No perfect tools
  - Must use approximations
  - Human insight matters
""")

🏛️ The Decidability Hierarchy

🎯 Mapping the Landscape

The decidability hierarchy classifies problems into decidable, recognizable, co-recognizable, and undecidable. Understanding this hierarchy tells us what computers can and cannot do.

The Hierarchy

Decidable: Always halts. Recognizable: Confirms "yes." Co-recognizable: Confirms "no." Decidable = Rec ∩ Co-rec. Strict: Each inclusion strict. Examples: DFA (decidable), HALT (recognizable), HALT^c (co-recognizable).

✅ Decidable🔄 Recognizable🔄 Co-recognizable❌ Undecidable

# The Decidability Hierarchy
print("=" * 60)
print("THE DECIDABILITY HIERARCHY")
print("=" * 60)

print("""
=== The Classes ===

DECIDABLE (Recursive):
  L is decidable if some TM always halts
  and correctly decides L.
  
  Examples: DFA membership, CFL membership

RECOGNIZABLE (Recursively Enumerable):
  L is recognizable if some TM accepts
  exactly the strings in L.
  (May loop on strings not in L.)
  
  Examples: HALT, TM membership

CO-RECOGNIZABLE:
  L is co-recognizable if L^c is recognizable.
  
  Examples: HALT^c, EQUIVALENCE^c

UNDECIDABLE:
  Not decidable.

=== Relationships ===

Decidable = Recognizable ∩ Co-recognizable

Proof:
  (→) Decidable → both recognizable.
  (←) If L and L^c are recognizable:
      Run both recognizers in parallel (dovetailing).
      One will accept.
      This decides L. ∎

=== The Hierarchy ===

  All Languages
  ┌─────────────────────────────────┐
  │                                 │
  │   Recognizable (r.e.)           │
  │   ┌─────────────────────────┐   │
  │   │                         │   │
  │   │   Decidable             │   │
  │   │   (Recursive)           │   │
  │   │                         │   │
  │   └─────────────────────────┘   │
  │                                 │
  │   Co-recognizable               │
  │                                 │
  └─────────────────────────────────┘

Decidable ⊊ Recognizable ⊊ All Languages
Decidable ⊊ Co-recognizable ⊊ All Languages

=== Examples by Class ===

DECIDABLE:
  - DFA membership
  - CFL membership
  - CSL membership
  - Integer arithmetic
  - Propositional logic

RECOGNIZABLE (not decidable):
  - HALT
  - TM membership
  - PCP
  - Hilbert's 10th

CO-RECOGNIZABLE (not decidable):
  - HALT^c
  - EQUIVALENCE^c

NEITHER:
  - Some languages are neither recognizable nor co-recognizable
  - But these are rare in practice
""")

# COMPARISON TABLE
print("""
=== Comparison of Decidability Classes ===

Class          Decider?  Recognizer?  Co-recognizer?
─────────────────────────────────────────────────────
Decidable      ✓         ✓            ✓
Recognizable   ✗         ✓            ✗ (usually)
Co-recognizable ✗        ✗            ✓
Neither        ✗         ✗            ✗

=== Examples by Machine Type ===

DFA:
  Membership: decidable
  Emptiness: decidable
  Equivalence: decidable
  Everything: decidable

CFG:
  Membership: decidable
  Emptiness: decidable
  Equivalence: undecidable (not recognizable)
  Ambiguity: undecidable

TM:
  Membership: recognizable (not decidable)
  Emptiness: undecidable (not recognizable)
  Equivalence: undecidable (neither)
  Almost everything: undecidable

=== The Pattern ===

More powerful model → less decidable problems.

DFA: everything decidable
CFG: most decidable
CSL: membership decidable
TM: almost nothing decidable
""")

# POST'S THEOREM
print("""
=== Post's Theorem ===

L is decidable
  ⟺
L is recognizable and L^c is recognizable.

Proof:
  (→) If L is decidable, both L and L^c
      are recognizable (use the decider).
  
  (←) If L and L^c are recognizable:
      Let R1 recognize L.
      Let R2 recognize L^c.
      
      Build decider D for L:
        D(w):
          Run R1 and R2 in parallel (dovetailing).
          If R1 accepts, accept.
          If R2 accepts, reject.
      
      One of them must accept (since w ∈ L or w ∈ L^c).
      So D always halts. D decides L. ∎

=== Why Dovetailing Works ===

Dovetailing runs both recognizers in parallel:

  Step 1: Run R1 for 1 step
  Step 2: Run R1 for 2 steps, R2 for 1 step
  Step 3: Run R1 for 3 steps, R2 for 2 steps
  Step 4: Run R1 for 4 steps, R2 for 3 steps
  ...

One of them will eventually accept.
We find it in finite time.

=== Implications ===

This theorem:
  - Connects decidability to recognizability
  - Gives a way to prove decidability
  - Explains why HALT is not decidable
    (HALT is recognizable, but HALT^c is not)

=== The Big Picture ===

  Decidable = Recognizable ∩ Co-recognizable

This is a fundamental theorem in computability.
""")

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

Decidability Classes:
  - Decidable: always halts
  - Recognizable: confirms "yes"
  - Co-recognizable: confirms "no"

Key theorem:
  Decidable = Recognizable ∩ Co-recognizable

Hierarchy:
  Decidable ⊊ Recognizable ⊊ All Languages
  Decidable ⊊ Co-recognizable ⊊ All Languages

Examples:
  DFA: decidable
  CFG: mostly decidable
  CSL: membership decidable
  TM: mostly undecidable

Post's theorem:
  L decidable ⟺ L and L^c both recognizable.

Key insight:
  The decidability hierarchy classifies
  problems by what we can compute about them.
  It's a fundamental map of computation.
""")

📐 Proof Techniques

🎯 How to Prove Decidability and Undecidability

Proving decidability or undecidability requires specific techniques. This section covers the main proof strategies.

Proof Strategies

Decidability: Construct algorithm. Decidability: Reduce to known decidable. Undecidability: Diagonalization. Undecidability: Reduction from HALT. Undecidability: Rice's theorem. Both: Closure properties.

🏗️ Construct📉 Reduce📐 Diagonal📊 Rice

# Proof Techniques
print("=" * 60)
print("PROOF TECHNIQUES")
print("=" * 60)

print("""
=== Proving DECIDABILITY ===

1. DIRECT CONSTRUCTION
   Build an algorithm that always halts.
   
   Example: DFA membership
     Simulate the DFA. Always halts. Decidable.

2. REDUCTION TO KNOWN DECIDABLE
   If A ≤ B and B is decidable, A is decidable.
   
   Example: NFA membership
     Convert NFA to DFA. Use DFA membership.
     Decidable.

3. CLOSURE PROPERTIES
   Use closure of decidable languages.
   
   Example: L1 ∩ L2
     If L1, L2 decidable, L1 ∩ L2 decidable.
     (Run both deciders.)

=== Proving UNDECIDABILITY ===

1. DIAGONALIZATION
   Construct a paradoxical machine.
   
   Example: HALT is undecidable.
     Assume H decides HALT. Construct D. Contradiction.

2. REDUCTION FROM HALT
   If HALT ≤ B, then B is undecidable.
   
   Example: HALT_EMPTY
     Reduce HALT to HALT_EMPTY.
     HALT undecidable → HALT_EMPTY undecidable.

3. RICE'S THEOREM
   Show property is semantic and non-trivial.
   
   Example: Is L(M) regular?
     Semantic? Yes. Non-trivial? Yes.
     Undecidable!

4. CLOSURE PROPERTIES
   Use closure to transfer undecidability.
   
   Example: If L undecidable and L ≤ B,
   then B undecidable.
""")

# PROOF TEMPLATES
print("""
=== Proof Templates ===

DECIDABILITY (Direct):
  Claim: L is decidable.
  Proof:
    1. Construct a TM D for L.
    2. Show D always halts.
    3. Show D accepts iff w ∈ L.
  Therefore, L is decidable. ∎

DECIDABILITY (Reduction):
  Claim: L is decidable.
  Proof:
    1. Show L ≤_m M for some decidable M.
    2. Since M is decidable and L ≤_m M,
       L is decidable. ∎

UNDECIDABILITY (Diagonalization):
  Claim: L is undecidable.
  Proof (by contradiction):
    1. Assume L is decidable with decider D.
    2. Construct a machine M that does the opposite.
    3. Run M on itself: contradiction.
  Therefore, L is undecidable. ∎

UNDECIDABILITY (Reduction):
  Claim: B is undecidable.
  Proof:
    1. Show A ≤_m B for some undecidable A (usually HALT).
    2. Since A is undecidable and A ≤_m B,
       B is undecidable. ∎

UNDECIDABILITY (Rice):
  Claim: L is undecidable.
  Proof:
    1. Show L corresponds to a semantic property P.
    2. Show P is non-trivial.
    3. By Rice's theorem, L is undecidable. ∎
""")

# EXAMPLE PROOFS
print("""
=== Example: HALT is Undecidable (Diagonalization) ===

Claim: HALT = { (M, w) | M halts on w } is undecidable.

Proof (by contradiction):
  Assume HALT is decidable.
  Let H be a decider for HALT:
    H(M, w) = accept if M halts on w
    H(M, w) = reject if M loops on w
    H always halts.
  
  Construct D:
    D(M):
      if H(M, M) accepts:
        loop forever
      else:
        halt and accept
  
  Consider D(D):
    If D(D) halts:
      H(D, D) accepts.
      So D(D) loops (by construction).
      Contradiction.
    If D(D) loops:
      H(D, D) rejects.
      So D(D) halts (by construction).
      Contradiction.
  
  Therefore, H cannot exist.
  HALT is undecidable. ∎

=== Example: HALT_EMPTY is Undecidable (Reduction) ===

Claim: HALT_EMPTY = { M | M halts on ε } is undecidable.

Proof:
  Reduce HALT to HALT_EMPTY.
  
  Given (M, w), construct M':
    M' on input x:
      1. Ignore x
      2. Simulate M on w
      3. If M halts, accept
  
  Then:
    M halts on w → M' halts on ε → M' ∈ HALT_EMPTY
    M loops on w → M' loops on ε → M' ∉ HALT_EMPTY
  
  So (M, w) ∈ HALT ⟺ M' ∈ HALT_EMPTY.
  
  Since HALT is undecidable,
  HALT_EMPTY is undecidable. ∎
""")

# COMMON MISTAKES
print("""
=== Common Mistakes ===

1. WRONG DIRECTION
   ✗ "A ≤ B and B undecidable, so A undecidable."
   ✓ "A ≤ B and A undecidable, so B undecidable."
   
   Direction matters!

2. ASSUMING DECIDABLE
   ✗ "It seems hard, so it must be undecidable."
   ✓ Prove it! Use diagonalization or reduction.

3. FORGETTING HALTING
   ✗ "We can just simulate."
   ✓ But simulation may not halt!

4. CONFUSING SYNTAX AND SEMANTICS
   ✗ "Is L(M) regular?" (semantic — undecidable)
   ✓ "Does M have 5 states?" (syntactic — decidable)

5. IGNORING CLOSURE
   ✗ Proving each problem from scratch.
   ✓ Use closure properties when possible.

6. NOT COMPLETING THE CONTRADICTION
   ✗ "So xy^0 z ∉ L." (stops here)
   ✓ "But pumping lemma says xy^0 z ∈ L. Contradiction."

=== Tips for Proofs ===

1. START WITH KNOWN RESULT
   HALT is undecidable.
   Use it as a source.

2. CHOOSE THE RIGHT TECHNIQUE
   Diagonalization: for self-reference.
   Reduction: for transferring undecidability.
   Rice: for semantic properties.

3. BE RIGOROUS
   Show every step.
   Justify every claim.
   Complete the contradiction.

4. PRACTICE
   The more proofs you see,
   the easier it gets.
""")

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

Proving DECIDABILITY:
  - Direct construction
  - Reduction to known decidable
  - Closure properties

Proving UNDECIDABILITY:
  - Diagonalization
  - Reduction from HALT
  - Rice's theorem
  - Closure properties

Proof templates:
  - Decidability: construct or reduce
  - Undecidability: diagonalize or reduce

Common mistakes:
  - Wrong direction
  - Assuming decidability
  - Forgetting halting
  - Confusing syntax and semantics
  - Ignoring closure
  - Not completing contradiction

Key insight:
  Proof techniques are tools.
  Choose the right one for the problem.
  Practice makes perfect.
""")

💼 Applications

🎯 Decidability in the Real World

Decidability theory has practical implications for software engineering, security, AI, and mathematics. Understanding what's decidable helps us design better systems and set realistic expectations.

Application Areas

Software: No perfect debugger. Security: No perfect virus detector. Compilers: Limited optimization. Verification: Need human insight. AI: Fundamental limits. Engineering: Workarounds and heuristics.

💻 Software🔐 Security⚙️ Compilers🤖 AI

# Applications of Decidability
print("=" * 60)
print("APPLICATIONS OF DECIDABILITY")
print("=" * 60)

# 1. SOFTWARE ENGINEERING
print("""
=== 1. Software Engineering ===

No perfect debugger:
  - Can't detect all infinite loops
  - Static analysis is approximate
  - Need testing + human insight

No perfect static analyzer:
  - Can't determine all program properties
  - Must trade soundness vs completeness
  - False positives or false negatives

Practical approaches:
  - Testing (find bugs, not prove absence)
  - Code review (human insight)
  - Type systems (prevent some errors)
  - Linters (warnings, not proofs)
""")

# 2. SECURITY
print("""
=== 2. Security ===

No perfect virus detector:
  - Can't detect all malicious programs
  - Malware can evade detection
  - Arms race continues

No perfect intrusion detection:
  - Can't detect all attacks
  - Heuristics + signatures
  - False positives/negatives

Practical approaches:
  - Signature-based detection
  - Heuristic analysis
  - Sandboxing
  - Behavior monitoring
""")

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

No perfect optimizer:
  - Can't always determine if code is dead
  - Can't always prove loops terminate
  - Must use conservative approximations

Practical approaches:
  - Data flow analysis (may be conservative)
  - Loop optimization (bounded loops)
  - Inlining (heuristics)
  - Register allocation (approximations)

=== 4. PROGRAM VERIFICATION ===

No automatic verifier:
  - Can't verify all programs
  - Need human insight
  - Some properties are undecidable

Practical approaches:
  - Model checking (finite state)
  - Type systems (restricted properties)
  - Proof assistants (human-guided)
  - Abstract interpretation (approximate)
""")

# 5. AI
print("""
=== 5. Artificial Intelligence ===

AI has fundamental limits:
  - No AI can solve the halting problem
  - No AI can predict arbitrary programs
  - No AI can verify arbitrary programs

But AI can:
  - Learn from data
  - Solve specific problems
  - Use heuristics
  - Be very useful

AGI (Artificial General Intelligence):
  - Could be Turing-complete
  - But can't exceed TMs
  - Still very powerful

AI safety:
  - Can't verify AI is safe (undecidable)
  - Must design for safety
  - Formal verification helps for specific properties
""")

# 6. WORKAROUNDS
print("""
=== 6. Engineering Workarounds ===

Since perfect tools are impossible,
we use workarounds:

1. TIMEOUTS
   - Run program for N seconds
   - If not done, assume loop
   - May have false positives

2. BOUNDED MODEL CHECKING
   - Check properties up to depth k
   - Not a proof, but finds bugs
   - Sound for bug finding

3. ABSTRACT INTERPRETATION
   - Approximate program behavior
   - Sound but incomplete
   - Used in static analysis

4. TESTING
   - Run on specific inputs
   - Find bugs, not prove absence
   - Practical and effective

5. HUMAN INSIGHT
   - Expert review
   - Mathematical proofs
   - Still essential

=== 7. PRACTICAL IMPLICATIONS ===

Despite undecidability:
  - We can build useful tools
  - We can solve specific problems
  - We can make progress
  - We just can't solve everything

Key insight:
  Undecidability sets limits,
  but doesn't prevent progress.
  We work within the limits.
""")

# 8. CASE STUDY
print("""
=== Case Study: Termination Analysis ===

Problem: Does a program terminate?

In general: undecidable.

But we can:
  1. Prove termination for specific programs
  2. Use ranking functions (measure decreasing)
  3. Use type systems (size types)
  4. Use abstract interpretation

Tools:
  - Terminator (Microsoft)
  - AProVE
  - T2
  - Julia

These tools:
  - Work for many practical programs
  - Can't work for all (undecidable)
  - Use heuristics + human guidance

Practical impact:
  - Prove termination of critical code
  - Find non-terminating loops
  - Improve software reliability
""")

# 9. SUMMARY TABLE
print("=== Application Summary ===")
print(f"{'Domain':<25} {'Application':<30} {'Impact':<25}")
print("-" * 80)
print(f"{'Software':<25} {'Debugging':<30} {'No perfect debugger':<25}")
print(f"{'Security':<25} {'Virus detection':<30} {'No perfect detector':<25}")
print(f"{'Compilers':<25} {'Optimization':<30} {'Limited optimization':<25}")
print(f"{'Verification':<25} {'Program correctness':<30} {'Need human insight':<25}")
print(f"{'AI':<25} {'General intelligence':<30} {'Fundamental limits':<25}")
print(f"{'Engineering':<25} {'Termination analysis':<30} {'Heuristics + proofs':<25}")

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

1. RECOGNIZE UNDECIDABLE PROBLEMS
   If your problem is undecidable,
   don't look for a perfect solution.

2. USE APPROXIMATIONS
   For undecidable problems,
   use approximation or heuristics.

3. APPLY RESTRICTIONS
   For decidable subclasses,
   use exact algorithms.

4. COMBINE HUMAN AND MACHINE
   Human insight + automation
   = best results.

5. UNDERSTAND LIMITS
   Undecidability is fundamental.
   Work within the limits.
   Make progress anyway.

Key insight:
  Decidability theory is not just theory.
  It guides software engineering,
  security, verification, and AI.
  Understanding limits helps us
  design better systems.
""")

🚀 Limits & Beyond

🎯 Living with Undecidability

Undecidability is a fundamental limit, but it doesn't mean we can't compute. It means we need to be smart about what we try to compute and how we approach problems.

Future Directions

Approximations: Better heuristics. Restrictions: Decidable subsets. Human-AI: Collaboration. Quantum: Same limits. New models: Hypercomputation? Philosophy: Limits of knowledge.

📊 Approximations🔬 Restrictions🤝 Human-AI⚛️ Quantum

# Limits & Beyond
print("=" * 60)
print("LIMITS & BEYOND")
print("=" * 60)

# 1. APPROXIMATION
print("""
=== 1. Approximation ===

Since exact answers are impossible,
we approximate.

Examples:
  - Static analysis: may have false positives
  - Bug finding: may have false negatives
  - Termination: prove for many programs, not all

Trade-offs:
  - Soundness vs completeness
  - Precision vs automation
  - Expressiveness vs decidability

Future:
  - Better algorithms
  - Machine learning for heuristics
  - Human-AI collaboration
""")

# 2. RESTRICTIONS
print("""
=== 2. Restrictions ===

Restrict the problem to make it decidable.

Examples:
  - Finite-state programs: decidable
  - Bounded loops: decidable
  - Linear programs: decidable
  - Typed programs: some properties decidable

Trade-offs:
  - Less expressive languages
  - More decidable properties
  - Practical for specific domains

Future:
  - Domain-specific languages
  - Verifiable subsets of languages
  - Design for verifiability
""")

# 3. HUMAN-AI
print("""
=== 3. Human-AI Collaboration ===

Combine human insight with AI power.

Examples:
  - Proof assistants (human-guided)
  - Interactive verification
  - AI-assisted debugging
  - Hybrid approaches

Benefits:
  - Human: creativity, insight
  - AI: speed, pattern recognition
  - Together: better than either alone

Future:
  - More intuitive proof assistants
  - AI that explains its reasoning
  - Collaborative problem solving
""")

# 4. QUANTUM
print("""
=== 4. Quantum Computing ===

Quantum computers:
  - Probably TM-equivalent
  - Same undecidability
  - Can't solve halting problem

BUT:
  - Faster for some problems
  - Different complexity profile
  - BQP, quantum algorithms

Quantum and undecidability:
  - Halting problem remains undecidable
  - No quantum algorithm can solve it
  - Fundamental limit applies

Future:
  - Quantum algorithms
  - Quantum complexity theory
  - Quantum verification
""")

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

Could we compute more than a TM?

Theoretical models:
  - Oracle machines
  - Infinite time TMs
  - Real computation
  - Zeno machines

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

Future:
  - Unlikely to be physical
  - Still theoretically interesting
  - Philosophical debates continue

If hypercomputation existed:
  - Would falsify Church-Turing
  - Could solve halting problem
  - Revolutionize CS
""")

# 6. PHILOSOPHY
print("""
=== 6. Philosophical Implications ===

Undecidability raises questions:

1. LIMITS OF KNOWLEDGE
   Some things are unknowable.
   Not just "hard to know."
   Fundamentally unknowable.

2. LIMITS OF COMPUTATION
   Some problems can't be solved.
   Not an engineering problem.
   Mathematical fact.

3. LIMITS OF AI
   No AI can solve undecidable problems.
   Even superintelligent AI.
   Fundamental limits.

4. NATURE OF MATHEMATICS
   Some truths are unprovable.
   Some problems are undecidable.
   Mathematics has limits.

5. FREE WILL
   If mind is computational,
   it has fundamental limits.
   (But still very powerful.)
""")

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

1. P vs NP
   Biggest open problem in CS.

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

3. Hypercomputation
   Do physical hypercomputers exist?

4. Quantum Complexity
   What is BQP's relationship to NP?

5. AI Limits
   What can AI not do?

6. Fine-Grained Complexity
   Exact complexity of specific problems.

7. Circuit Lower Bounds
   Prove explicit functions need large circuits.
""")

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

For students:
  1. Master halting problem proof
  2. Understand reductions
  3. Learn Rice's theorem
  4. Explore related problems
  5. Study complexity theory

For researchers:
  1. P vs NP
  2. Hypercomputation
  3. Quantum complexity
  4. AI limits
  5. Philosophy of computation

For practitioners:
  1. Recognize undecidable problems
  2. Use approximations wisely
  3. Understand complexity trade-offs
  4. Know when to stop
  5. Apply theory to practice

=== Final Thoughts ===

Decidability teaches us:

✓ LIMITS
  Some problems are impossible.

✓ TECHNIQUE
  Diagonalization, reductions.

✓ PERSPECTIVE
  Understanding limits helps us work within them.

✓ HUMILITY
  We can't solve everything.

✓ CREATIVITY
  We can still solve many things.

Key takeaway:
  Undecidability is not pessimism.
  It's a fundamental fact about computation.
  It shapes what we can know and do.
  And it's beautiful.

"We can only see a short distance ahead,
 but we can see plenty there that needs
 to be done."
  — Alan Turing

Go compute something!
""")

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

Decidable:
  TM always halts
  Recursive

Recognizable:
  TM accepts if w ∈ L
  May loop if w ∉ L
  Recursively enumerable

Co-recognizable:
  Complement is recognizable

Relationships:
  Decidable = Recognizable ∩ Co-recognizable

Hierarchy:
  Decidable ⊊ Recognizable ⊊ All Languages

Key problems:
  HALT: recognizable, not decidable
  HALT^c: co-recognizable, not recognizable
  EQUIVALENCE: undecidable (neither)

Proof techniques:
  Decidability: construct, reduce
  Undecidability: diagonalize, reduce, Rice

Rice's theorem:
  All non-trivial semantic properties undecidable.

Key insight:
  Decidability theory defines the limits
  of computation.
  It's the foundation of computer science.
""")