Computability Theory

What is Computability Theory?

Computability Theory studies what problems can and cannot be solved by algorithms.

Simple Analogy

Think of it like:

• Physics: Studies what’s physically possible
• Computability: Studies what’s algorithmically possible

Questions:

• Can we write a program to solve this problem?
• Are there problems no program can solve?
• What makes a problem unsolvable?

Core Question

“What can be computed?”

Not “how fast?” but “at all?”

Historical Background

1930s: Foundations laid

Key figures:

• Alan Turing: Turing machines (1936)
• Alonzo Church: Lambda calculus (1936)
• Kurt Gödel: Incompleteness theorems (1931)
• Emil Post: Post systems (1936)

Hilbert’s Entscheidungsproblem (Decision Problem):

Is there an algorithm to decide truth of mathematical statements?

Answer: NO! (Turing & Church, 1936)

Church-Turing Thesis

Church-Turing Thesis: Every effectively computable function can be computed by a Turing Machine.

What “Effectively Computable” Means

Informal: Can be computed by following a mechanical procedure

Properties:

1. Finite description (finitely many rules)
2. Discrete steps (no continuous operations)
3. Deterministic or bounded non-determinism
4. No randomness or oracles

Status

Not a theorem: Cannot be proved mathematically

Why?: “Effectively computable” is informal concept

Universally accepted: No counterexample in 90+ years!

Evidence

All these models equivalent:

• Turing Machines
• Lambda calculus
• Recursive functions
• Post systems
• Register machines
• Random access machines
• Modern programming languages

Convergence: All capture same class of functions

Computable Functions

Definition

Function f: ℕ → ℕ is computable if there exists TM M such that:

• On input n, M halts with f(n) on tape
• For all n ∈ ℕ

Also called: Recursive function, Turing-computable

Examples of Computable Functions

1. Addition: f(m, n) = m + n

TM can:
1. Count m a's
2. Count n more a's
3. Output m+n a's

2. Multiplication: f(m, n) = m × n

TM can:
1. Add m to itself n times

3. Exponentiation: f(m, n) = mⁿ

TM can:
1. Multiply m by itself n times

4. Factorial: f(n) = n!

TM can:
1. Multiply 1 × 2 × 3 × ... × n

5. Prime checking: f(n) = 1 if n prime, 0 otherwise

TM can:
1. Try dividing n by 2, 3, ..., n-1
2. Accept if no divisor found

6. GCD: f(m, n) = gcd(m, n)

TM can:
1. Implement Euclidean algorithm

Examples of Non-Computable Functions

1. Halting function:

h(⟨M⟩, w) = 1 if M halts on w
           = 0 if M loops on w

NOT computable! (Halting problem)

2. Busy Beaver function:

BB(n) = max steps any n-state TM makes before halting

NOT computable!

3. Kolmogorov complexity:

K(x) = length of shortest program that outputs x

NOT computable!

Decidable vs Recognizable

Decidable Languages (Recursive)

Definition: Language L is decidable if there exists TM M that:

1. Accepts every w ∈ L
2. Rejects every w ∉ L
3. Halts on all inputs

Key: Always gives answer (yes or no)

Also called:

• Recursive
• Computable
• Solvable

Recognizable Languages (Recursively Enumerable)

Definition: Language L is recognizable if there exists TM M that:

1. Accepts every w ∈ L
2. Rejects or loops on w ∉ L
3. May not halt on all inputs

Key: Says “yes” if true, may run forever if false

Also called:

• Recursively enumerable (RE)
• Turing-recognizable
• Partially decidable
• Computably enumerable (c.e.)

Relationship

Decidable ⊂ Recognizable ⊂ All Languages

Every decidable language is recognizable

• If always halts, certainly recognizes

Not every recognizable language is decidable

• May loop on reject

Comparison Table

Co-Recognizable Languages

Definition: Language L is co-recognizable if its complement L̄ is recognizable

Equivalently: TM that:

• Rejects every w ∈ L (loops or explicit reject)
• Accepts every w ∉ L

Important Theorem

Theorem: L is decidable ⟺ L is both recognizable and co-recognizable

Proof (⟹):

• If L decidable, TM M decides it
• M recognizes L (accepts w ∈ L)
• M also recognizes L̄ (accepts w ∉ L by rejecting)

Proof (⟸):

• If L recognizable by M₁ and co-recognizable by M₂
• Run M₁ and M₂ in parallel
• If w ∈ L: M₁ accepts eventually
• If w ∉ L: M₂ accepts eventually
• One must halt! So L decidable.

Significance

To prove L undecidable:

• Show L recognizable but not co-recognizable
• Or show L̄ not recognizable

The Chomsky Hierarchy

Four levels of languages:

Type 0: Recursively Enumerable (RE)
        ↑
Type 1: Context-Sensitive (CSL)
        ↑
Type 2: Context-Free (CFL)
        ↑
Type 3: Regular

Type 3: Regular Languages

Recognized by: Finite Automata (DFA/NFA)

Grammar: A → aB or A → a

Examples: {aⁿbⁿ | n ≥ 0} is NOT regular

Properties: Decidable, closed under all operations

Type 2: Context-Free Languages

Recognized by: Pushdown Automata (PDA)

Grammar: A → α (any α)

Examples: {aⁿbⁿ} yes, {aⁿbⁿcⁿ} no

Properties: Decidable, some closure properties

Type 1: Context-Sensitive Languages

Recognized by: Linear Bounded Automata (LBA)

Grammar: αAβ → αγβ where |γ| ≥ 1

Examples: {aⁿbⁿcⁿ} yes

Properties: Decidable, uses at most linear space

Type 0: Recursively Enumerable

Recognized by: Turing Machines

Grammar: α → β (any α, β)

Examples: All recognizable languages

Properties: Not all decidable

Undecidable Languages

Languages that are NOT decidable

Examples

1. Halting problem: HALT = {⟨M, w⟩ | M halts on w}

2. Acceptance problem: Aₜₘ = {⟨M, w⟩ | M accepts w}

3. Emptiness: Eₜₘ = {⟨M⟩ | L(M) = ∅}

4. Equivalence: EQₜₘ = {⟨M₁, M₂⟩ | L(M₁) = L(M₂)}

5. Totality: TOTₜₘ = {⟨M⟩ | M halts on all inputs}

Why Undecidable?

Diagonalization: Self-reference creates contradiction

Reduction: Reduce from known undecidable problem

Enumerability

Enumerable Languages

Definition: Language L is enumerable if there exists TM M (enumerator) that prints all strings in L

Output: w₁, w₂, w₃, … (all strings in L, in some order)

Lexicographic Enumeration

Order strings by:

1. Length (shorter first)
2. Alphabetically within same length

Example: ε, a, b, aa, ab, ba, bb, aaa, …

Equivalence Theorem

Theorem: L is recognizable ⟺ L is enumerable

Proof (⟹): Recognizable → Enumerable

Given TM M recognizing L:

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

Proof (⟸): Enumerable → Recognizable

Given enumerator E for L:

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

Countable vs Uncountable

Countable Sets

Definition: Set S is countable if can list elements: s₁, s₂, s₃, …

Examples:

• ℕ (natural numbers): Trivially countable
• ℤ (integers): 0, 1, -1, 2, -2, 3, -3, …
• ℚ (rationals): Use Cantor’s diagonal
• Σ* (all strings): Lexicographic order
• All TMs: Each TM has finite encoding

Uncountable Sets

Definition: Set S is uncountable if cannot be listed

Examples:

• ℝ (real numbers): Cantor’s diagonal proof
• P(ℕ) (power set of ℕ)
• All languages: 2^(Σ*) uncountable!

Key Theorem

Theorem: The set of all TMs is countable, but the set of all languages is uncountable.

Consequence: Most languages are not recognizable!

Proof:

1. TMs are countable (finite encodings)
2. Languages are uncountable (2^(Σ*))
3. Can’t have bijection TM ↔ Language
4. Most languages have no TM!

Diagonalization

Technique: Construct object different from all in list

Cantor’s Diagonal Argument

Prove: ℝ uncountable

Assume: Real numbers in [0,1] listable

r₁ = 0.d₁₁ d₁₂ d₁₃ d₁₄ ...
r₂ = 0.d₂₁ d₂₂ d₂₃ d₂₄ ...
r₃ = 0.d₃₁ d₃₂ d₃₃ d₃₄ ...
r₄ = 0.d₄₁ d₄₂ d₄₃ d₄₄ ...
...

Construct: r = 0.c₁c₂c₃c₄…

• c₁ ≠ d₁₁ (differs from r₁ in position 1)
• c₂ ≠ d₂₂ (differs from r₂ in position 2)
• c₃ ≠ d₃₃ (differs from r₃ in position 3)
• …

r differs from every rᵢ: Contradiction!

Turing’s Diagonalization

Prove: Halting problem undecidable

Uses: Self-reference and diagonal argument

Key: TM can take TM as input (Universal TM)

Reductions

Definition: Problem A reduces to problem B (A ≤ B) if:

• Solution to B gives solution to A
• “A is no harder than B”

Mapping Reduction

A ≤ₘ B: Computable function f such that:

w ∈ A ⟺ f(w) ∈ B

Use: To prove B undecidable

1. Take known undecidable A
2. Show A ≤ₘ B
3. Conclude B undecidable

Example: HALT ≤ₘ Eₜₘ

Turing Reduction

A ≤ₜ B: TM for A can call oracle for B

Weaker: More general than mapping reduction

Rice’s Theorem

Rice’s Theorem: Any non-trivial property of recognizable languages is undecidable.

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

Property of language: Depends only on L(M), not M itself

Examples

Undecidable (by Rice’s Theorem):

• Is L(M) empty?
• Is L(M) finite?
• Is L(M) regular?
• Is L(M) context-free?
• Does L(M) contain “hello”?
• Is L(M) = L(M’)?

Decidable (properties of M, not L(M)):

• Does M have 5 states?
• Does M’s description contain “a”?
• Does M have at least one transition?

Proof Sketch

Assume: Property P decidable

WLOG: ∅ doesn’t have P, some language L does

Construct: Reduction from Aₜₘ

Given ⟨M, w⟩:

Build M':
  M'(x):
    1. Run M on w
    2. If M accepts w, accept x iff x ∈ L
       (simulate TM for L)
    3. If M rejects w, reject x

Observe:

• If M accepts w: L(M’) = L (has property P)
• If M rejects w: L(M’) = ∅ (doesn’t have P)

Decidable P would decide Aₜₘ: Contradiction!

Complexity of Computability

Decidable = Recursive

Time: May take arbitrarily long

But: Always finishes

Example: {aⁿbⁿcⁿ} decidable (mark and match)

Recognizable = RE

Time: May never finish

Accept: Eventually says yes

Reject: May loop forever

Example: HALT recognizable (simulate and watch)

Not Recognizable

Can’t even accept members

Example: H̄ALT (complement of halting problem)

Neither HALT nor H̄ALT decidable

Practical Implications

Program Verification

Can’t decide:

• Does program halt on all inputs?
• Does program satisfy specification?
• Is program free of bugs?

Rice’s Theorem: Any semantic property undecidable

Compiler Optimization

Can’t decide:

• Is this code unreachable?
• Are these two programs equivalent?
• Does loop terminate?

Must use heuristics

Testing

Can’t prove: Program correct on all inputs

Can only: Test on finite cases

Undecidability: Fundamental limit

Important Exam Points

1. ✓ Computable function: TM halts and outputs f(n) for all n
2. ✓ Decidable: TM halts on all inputs (recursive)
3. ✓ Recognizable: TM accepts all in L, may loop on others (RE)
4. ✓ Church-Turing thesis: TM captures “algorithm”
5. ✓ L decidable ⟺ L and L̄ both recognizable
6. ✓ Chomsky hierarchy: Regular ⊂ CFL ⊂ CSL ⊂ RE
7. ✓ Enumerable ⟺ Recognizable
8. ✓ TMs countable, languages uncountable
9. ✓ Diagonalization: Proof technique for impossibility
10. ✓ Rice’s theorem: Non-trivial properties undecidable

Common Mistakes to Avoid

✗ Mistake 1: Confusing decidable and recognizable
✓ Correct: Decidable always halts, recognizable may loop

✗ Mistake 2: Thinking Church-Turing thesis provable
✓ Correct: It’s philosophical statement, not theorem

✗ Mistake 3: All languages recognizable
✓ Correct: Most languages not even recognizable!

✗ Mistake 4: If L decidable, L̄ may not be
✓ Correct: Decidable closed under complement

✗ Mistake 5: Rice’s theorem applies to all properties
✓ Correct: Only properties of L(M), not M itself

✗ Mistake 6: Recognizable = semi-decidable
✓ Correct: Yes, these are same thing

Practice Questions

Q1: Difference between decidable and recognizable?

Answer: Decidable always halts; recognizable may loop on reject.

Q2: Is addition computable?

Answer: Yes! TM can add by counting.

Q3: Is L decidable if L and L̄ recognizable?

Answer: Yes! Run both TMs in parallel, one halts.

Q4: What is Church-Turing thesis?

Answer: Every algorithm can be computed by TM.

Q5: Are there more languages than TMs?

Answer: Yes! Languages uncountable, TMs countable.

Q6: Can Rice’s theorem prove emptiness undecidable?

Answer: Yes! “Is L(M) empty?” is non-trivial language property.

Q7: Is every decidable language recognizable?

Answer: Yes! If halts always, certainly recognizes.

Q8: What does enumerable mean?

Answer: Can list all strings in language (equivalent to recognizable).

Q9: Is halting problem decidable?

Answer: No! Proved undecidable by Turing.

Q10: Chomsky hierarchy order?

Answer: Regular ⊂ CFL ⊂ CSL ⊂ RE ⊂ All.

Summary

• Computability theory: Studies what’s algorithmically possible
• Church-Turing thesis: TM = “algorithm” (not provable)
• Computable function: TM computes f(n) for all n
• Decidable: TM halts on all inputs (recursive)
• Recognizable: TM accepts members, may loop (RE)
• L decidable ⟺ L and L̄ both recognizable
• Chomsky hierarchy: Regular ⊂ CFL ⊂ CSL ⊂ RE
• Enumerable ⟺ Recognizable (can list all strings)
• TMs countable, languages uncountable → most not recognizable
• Diagonalization: Proof technique using self-reference
• Rice’s theorem: Non-trivial language properties undecidable
• Key insight: Fundamental limits on what’s computable

Computability theory reveals the boundaries of algorithmic problem-solving!