Note 12: Computability | EECS 70
EECS 70 — Fall 2021

Note 12: Self-Reference and Computability

Liar's Paradox · Quines · Halting Problem · Reductions · Gödel's Incompleteness

Can every mathematical question be answered by a computer? The answer is a resounding no. There are well-defined computational problems that no program can ever solve. This is not a technological limitation — it is a fundamental mathematical impossibility, proven rigorously using self-reference, the same trick that powers the Liar's Paradox.

Section 1

Self-Reference and Paradox

The root of all the impossibility results in this note is self-reference. Consider:

The Liar's Paradox
"This statement is false."

If true, then it is false. If false, then it is true. Neither assignment is consistent — a true paradox. This arises because the statement refers to itself.

Russell's Barber: "I shave all and only those men who do not shave themselves." Does the barber shave himself? Either answer leads to contradiction.

These paradoxes are not just curiosities. They reveal a deep truth: certain questions about self-referential systems cannot be consistently answered. The same structure appears in questions about programs (can a program analyze itself?) and in mathematical logic (can a formal system prove its own consistency?).

Section 2

Self-Replicating Programs (Quines)

Can a program output its own source code? Yes — such a program is called a quine. This demonstrates that self-reference in computation is possible, and it is a key ingredient in the Halting Problem proof.

The Recursion Theorem
For any program $P(x, y)$, there exists a program $Q(x)$ such that $Q(x) = P(x, Q)$ for all inputs $x$. That is, $Q$ behaves exactly like $P$ would if $P$'s second input were $Q$'s own description. $Q$ is "self-aware."
📘 A Quine in pseudocode

Consider this pseudocode program:

// Program: Quine "s"
Quine("Quine") // Execute Quine with input "Quine"
// This outputs: (Quine "Quine") — same as the instruction above!

When we run Quine("Quine"), the program runs the string "Quine" (as a program) on itself, producing (Quine "Quine") — which is exactly the program itself. Self-replication achieved.

Quines exist in every programming language. Python has 1-line quines, for example.
Section 3

The Halting Problem

The Halting Problem
Given a program $P$ and input $x$, decide whether $P$ halts (terminates) or loops forever on input $x$.

We want a program TestHalt(P, x) that returns "yes" if $P$ halts on $x$, and "no" if $P$ loops on $x$.
Theorem — The Halting Problem is Uncomputable
No program TestHalt with the above behavior can exist.

Proof of Uncomputability

The proof is by contradiction. Assume TestHalt exists. We construct a new program that leads to paradox.

def Turing(P):
    if TestHalt(P, P) == "yes":
        loop forever # P halts on P ⟹ we loop
    else:
        halt # P loops on P ⟹ we halt
The Contradiction
Ask: what does Turing(Turing) do?
  • Case 1: Turing(Turing) halts. Then TestHalt(Turing, Turing) returned "yes", so Turing loops forever on itself. Contradiction.
  • Case 2: Turing(Turing) loops. Then TestHalt(Turing, Turing) returned "no", so Turing halts on itself. Contradiction.
Both cases are impossible. Therefore our assumption (TestHalt exists) is false. ∎
The diagonalization table: each cell $(i,j)$ shows H (halts) or L (loops) when program $P_i$ runs on input $P_j$. The program Turing flips the diagonal — it cannot appear anywhere on this list. Click to animate.

Why This is Diagonalization

The set of all programs is countable (programs are finite strings). List them: $P_0, P_1, P_2, \ldots$. Make a table where entry $(i,j)$ is H if $P_i$ halts on $P_j$, or L if it loops. If Turing exists, it appears as some $P_n$. But Turing differs from $P_n$ at position $(n,n)$ (the diagonal) — a contradiction. This is the exact same structure as Cantor's proof.

⚠ Other Uncomputable Problems
Many natural questions about programs are uncomputable. No program can decide:
  • Does program $P$ ever output anything?
  • Does $P$ halt on input 0? (the "easy" halting problem — still uncomputable by reduction)
  • Do programs $P$ and $Q$ compute the same function?
  • Is program $P$ a virus?
Rice's Theorem (beyond this course): Every non-trivial property of what a program computes is uncomputable.
Section 4

Reductions

Reduction
A reduction from problem $A$ to problem $B$ is an algorithm that converts any instance of $A$ into an instance of $B$, such that if we can solve $B$ we can solve $A$.

If $A$ is hard (uncomputable) and $A$ reduces to $B$, then $B$ is at least as hard as $A$ (also uncomputable).

Contrapositive: If $B$ is easy (computable) and $A$ reduces to $B$, then $A$ is easy too.
📘 The Easy Halting Problem reduces to Halting

Easy Halting Problem: Does program $P$ halt on input 0? (Seemingly simpler than the general Halting Problem.)

Claim: This is still uncomputable.

Proof by reduction: Suppose TestEasyHalt(P) existed. We construct Halt(P, x):

def Halt(P, x):
    # Construct P' that ignores its input and runs P(x)
    P' = lambda y: P(x)
    return TestEasyHalt(P')

$P'$ halts on 0 if and only if $P(x)$ halts. So TestEasyHalt(P') correctly decides whether $P$ halts on $x$. But Halt solves the (uncomputable) Halting Problem. Contradiction — TestEasyHalt cannot exist.

Easy Halting ≡ General Halting (both uncomputable). The "easy" version is just as hard.
Section 5

Gödel's Incompleteness Theorem

In 1930, Kurt Gödel shocked the mathematical world by proving that no sufficiently powerful formal system can be both consistent and complete.

Key Definitions
A formal system consists of axioms and inference rules. It is:
  • Consistent: No statement can be both proved and disproved.
  • Complete: Every true statement has a proof.
Gödel's First Incompleteness Theorem
Any formal system $F$ that is sufficiently expressive to formalize arithmetic is either:
  • Inconsistent: There exist false statements that can be proved, OR
  • Incomplete: There exist true statements that cannot be proved.
In particular, a consistent system cannot prove its own consistency (Second Incompleteness Theorem).

Sketch of the Proof via Self-Reference

Gödel encoded propositions as natural numbers (Gödel numbering). This allowed him to write a statement $S(F)$ that says: "This statement is not provable in $F$." Two cases:

  • If $S(F)$ is provable in $F$: then it is true, but it says it is not provable. $F$ is inconsistent.
  • If $S(F)$ is not provable in $F$: then $S(F)$ is true (it correctly says it is unprovable). But $F$ cannot prove it. $F$ is incomplete.

Proof via the Halting Problem

A cleaner argument: Assume for contradiction that arithmetic is both consistent and complete. Given any program $P$ and input $x$, we want to decide if $P$ halts. Consider the statement $S_{P,x}$: "There exists a valid halting computation sequence of $P$ on $x$." This can be written in arithmetic.

Since arithmetic is complete, there is a proof of either $S_{P,x}$ or $\neg S_{P,x}$. Since proofs are finite strings, we can enumerate all proofs one by one and search for a proof of $S_{P,x}$ or $\neg S_{P,x}$. This search always terminates — solving the Halting Problem. But that is impossible. Contradiction.

The Big Picture
Computability, set theory, and logic are all connected by the same idea: self-reference leads to limits.
  • Cantor (1874): $\mathbb{R}$ is uncountable — too many things to list.
  • Turing (1936): Halting Problem is uncomputable — too many programs to analyze.
  • Gödel (1930): Arithmetic is incomplete — too many truths to prove.
All three proofs use the same diagonal construction.
Section 6

Hard Practice Problems

🔥 Hard Problem 1

Problem: Define the "printing" problem: given program $P$, does $P$ ever print the digit "7" at any point during its execution? Prove this is uncomputable by reducing the Halting Problem to it.

📋 Solution to Hard Problem 1

Goal: Assume TestPrint7(P) exists (returns "yes" if $P$ ever prints 7). Derive a contradiction by using it to solve the Halting Problem.

  1. Given program $P$ and input $x$, construct a new program $P'$:
    def P'(y):
        P(x) # Run P on x (ignoring y)
        print(7)
  2. Key observation: $P'$ prints 7 if and only if $P(x)$ halts. If $P(x)$ halts, $P'$ reaches the print(7) line. If $P(x)$ loops, $P'$ never reaches it.
  3. So TestPrint7(P') returns "yes" iff $P(x)$ halts. This solves the Halting Problem.
  4. Since the Halting Problem is uncomputable, TestPrint7 cannot exist.
The printing problem is uncomputable. The same reduction works for any "observable behavior" of a program. ∎
🔥 Hard Problem 2

Problem: Prove that the following problem is uncomputable: given two programs $P$ and $Q$, do they compute the same function? (That is, for all inputs $x$, do $P(x)$ and $Q(x)$ both halt or both loop, and if they halt, do they produce the same output?)

📋 Solution to Hard Problem 2

Strategy: Reduce the Halting Problem to program equivalence.

  1. Let TestEquiv(P, Q) be a hypothetical program that decides if $P$ and $Q$ compute the same function.
  2. Define the "trivially looping" program: $\text{Loop}(x) = $ loop forever.
  3. Given $P$ and $x$, construct $P'(y)$: run $P(x)$ (ignoring $y$), then output 0.
  4. Now: if $P(x)$ halts, then $P'(y)$ halts and outputs 0 for all $y$. If $P(x)$ loops, $P'$ loops forever for all $y$, just like $\text{Loop}$.
  5. So $P'$ is equivalent to $\text{Loop}$ if and only if $P(x)$ does not halt. Therefore TestEquiv(P', Loop) decides whether $P$ halts on $x$. This solves the Halting Problem.
Program equivalence is uncomputable. This is essentially Rice's Theorem for this specific property. ∎
Scroll to Top