N or Space for next slide, P for previous slide, F for full screen, M for menu
Lec 10: Godel’s Incompleteness Theorem
Boaz Barak (instructor), Brian Sapozhnikov (Head TF), Albert Chalom, Alexis Ross, Charles O’Mara, Daniel Chen, David Li , Jambay Kinley, Jane Ahn, John Shen, Josh Seides, Laura Pierson, Pranay Tankala, Raymond Lin, Theresa Nguyen, Wanqian Yang, William Fu, Hikari Sorensen (Extension TF), Eric Lu (Patel Fellow)
Laptops/phones only on last 5 rows please.
Uncomputability
“Take any definite unsolved problem, such as … the existence of an infinite number of prime numbers of the form \(2^n + 1\). However unapproachable these problems may seem to us and however helpless we stand before them, we have, nevertheless, the firm conviction that their solution must follow by a finite number of purely logical processes…”
“…This conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus.”, David Hilbert, 1900.
A brief history of math
- 300 BC Euclid’s The Elements: the axiomatic method.
- \(\approx\) 500BC till 1400AD: Several cultures independently (and not) discover positional number systems, linear equations in many variables, single-variable quadratic equations, etc..
- 1600’s-1800’s “Golden age of calculations”: Calculus, Fourier transform,… Calculate first, worry about justification later
- 1800’s: “Rigor rising”: Group theory, weird counterexamples, re-doing calculus from foundations (\(\epsilon\)’s, \(\delta\)’s). Cantor and others “breaking math at the seams”
A brief history of math (2)
- Late 1800’s, early 1900’s: “Grand rigor project” Base all of math on axioms. Russel and Whitehead Principia Mathematica. The Hilbert Program
Gödel, 1931: For every sound proof system there is a number theoretic statement that is true but unprovable.
- Cohen, 1963: Continuum hypothesis cannot be proven by “Zermelo Frankel and Choice” axioms.
- Yuri Matiyasevich, Julia Robinson, Martin Davis, and Hilary Putnam (MRDP): 1949-1970 No algorithm for solving diophantine equations, Hilbert’s 10th problem is impossible to solve.
What is a proof?
A mathematical statement is a piece of text that can be either true or false. A proof is a piece of text whose existence certifies a statement is true.
What is a proof?
A mathematical statement is a piece of text that can be either true or false. A proof is a piece of text whose existence certifies a statement is true.
Def: A proof for a statement \(x\in \{0,1\}^*\) is a string \(w\in \{0,1\}^*\) such that \(V(x,w)=1\) for some function \(V\). \(V\) is verifier or proof system and should be:
Sound: if there exists \(w\in \{0,1\}^*\) s.t. \(V(x,w)=1\) then \(x\) is true.
Effective: \(V\) is computable.
Ideally, we would also like \(V\) to be complete: for every true statement \(x\) in some domain, there exists a proof \(w\) s.t. \(V(x,w)=1\).
Examples: First order logic (Gödel 1929), Presburger arithmetic (Presburger 1929), Geometry (.. Tarski 1951), Quantified Statements over closed fields.
Proofs
Def: A proof system is an algorithm \(V\) such that for every \(x\in \{0,1\}^*\), if there exists \(w\in \{0,1\}^*\) such that \(V(x,w)=1\) then \(x\) is true.
Question: Which one of the following proof systems satisfies def?
Proofs
Def: A (sound+effective) proof system is an algorithm \(V\) such that for every \(x\in \{0,1\}^*\), if there exists \(w\in \{0,1\}^*\) such that \(V(x,w)=1\) then \(x\) is true. \(V\) is complete if for every true \(x\), there exists \(w\in \{0,1\}^*\) s.t. \(V(x,w)=1\).
Gödel’s Incompleteness Theorem: If a proof system is sound, effective, and sufficiently rich, then it is incomplete.
Gödel Second Theorem: If a proof system is effective and sufficiently rich, then it can’t prove its own consistency.
What Gödel’s Theorems don’t say
Machines can’t think
There is no such thing as objective truth
God exists
The moon landing was faked
Nothing is Impossible (Chris Harris)
Nothing is impossible,
Child, nothing is impossible,
Every bridge is crossable,
Every tooth is flossable,
Every win is lossable,
Every worker’s bossable,
Every cookie’s tossable,
Every yak’s a Lhasa bull,
Nothing is impossible,
Child, nothing is impossible
OK, teacher, can you name something that ISN’T possible?
No, child, nothing is impossible
So, there is something that’s impossible: naming something that’s impossible is impossible.
Well, um, I guess, child..
In that case, it IS possible to name something that’s impossible, because naming something that’s impossible is impossible.
But THEN, naming something that’s impossible is NOT impossible; it’s possible, which means it IS impossible to name something that’s impossible
Gödel statement
\(x\) = “The statement \(x\) has no proof in the system \(V\)”
\(x\) = “\(\forall_{w\in \{0,1\}^*} V(x,w)=0\)”
If \(x\) is true, then it has no proof.
If \(x\) is false then \(x\) has a proof and then it is true!
Bottom line: \(x\) is true and has no proof: \(V\) is incomplete!
Note: Proof for \(x\) is proof for \(NOT(x)\). Hence, \(V\) is consistent \(\Rightarrow\) \(x\) has no proof Hence, \(V\) is consistent \(\Rightarrow\) \(x\) is true. Hence \(V\) can’t prove that \(V\) is consistent.
Gödel statement construction
\(x\) = “The statement \(x\) has no proof in the system \(V\)”
\(x\) = “\(\forall_{w\in \{0,1\}^*} V(x,w)=0\)”
- Use quantifiers to simulate computation.
- Find a program that can print its own code (related to fixed-point theorems, Y Combinator)
- Equivalent of a program that goes to infinite loop if it has a proof that it halts.
CS version of Gödel Theorem
Domain: Statements of form “Program \(P\) halts on input \(z\)” and “Program \(P\) does not halt on input \(z\)” (encoded as strings)
Thm: For every sound and effective \(V\), there is a true statement \(x\) that does not have a proof in \(V\).
Proof of thm: Suppose otherwise, then this is an algorithm for halting problem:
Input: TM \(P\), input \(z\)
Operation: Let \(n=0\) and
- Enumerate over all \(w \in \{0,1\}^n\):
- If \(V(\text{"$P$ doesn't halt on $z$"},w)=1\) halt and output \(0\).
- If \(V(\text{"$P$ halts on $z$"},w)=1\) output \(1\).
- Let \(n=n+1\) and go back to 1.
Analysis: \(H\) either halts on \(z\) or not. If \(V\) is complete then eventually we will recover the proof of the right statement.
High level lesson
If \(F:\{0,1\}^* \rightarrow \{0,1\}\) is uncomputable, then there is no sound, effective, and complete proof system for statements of form “\(F(x)=0\)” and “\(F(x)=1\)”.
Gödel’s Thm (restatement): \(QIS:\{0,1\}^* \rightarrow \{0,1\}\) is uncomputable, where \(QIS(x)=1\) iff \(x\) is a true statement on natural numbers involving \(\forall\), \(\exists\), \(\wedge\), \(\vee\), \(\neg\), \(\gt\),\(\lt\),\(=\),\(+\),\(\times\), \(0\) and \(1\).
Example: \(\color{red}{HILBERTCONJ}\): For every \(n\), there exists a prime \(p \gt n\) of the form \(p=2^n+1\):
\(\color{red}{DIVIDES(a,c)} = \exists_{b\in \mathbb{N}} a = b \times c\)
\(\color{red}{PRIMES(p)} = \forall_{a \in \mathbb{N}} \neg DIVIDES(a,p) \vee (a=1) \vee (a=p)\)
\(\color{red}{HILBERTCONJ} = \forall_{n\in \mathbb{N}} \exists_{p\in \mathbb{N}} (p \gt n) \wedge PRIME(p) \wedge\)
\(\forall_{a\in \mathbb{N}} DIVIDES(a,p-1) \Rightarrow DIVIDES(2,a)\)
High level lesson
If \(F:\{0,1\}^* \rightarrow \{0,1\}\) is uncomputable, then there is no sound, effective, and complete proof system for statements of form “\(F(x)=0\)” and “\(F(x)=1\)”.
Gödel’s Thm (restatement): \(QIS:\{0,1\}^* \rightarrow \{0,1\}\) is uncomputable, where \(QIS(x)=1\) iff \(x\) is a true statement on natural numbers involving \(\forall\), \(\exists\), \(\wedge\), \(\vee\), \(\neg\), \(\gt\),\(\lt\),\(=\),\(+\),\(\times\), \(0\) and \(1\).
Example: For every \(n\), there exists a prime \(p \gt n\) of the form \(p=2^n+1\).
MRDP Thm (Gödel++): \(DIOPHANTINE:\{0,1\}^* \rightarrow \{0,1\}\) is uncomputable, where \(DIOPHANTINE(x)=1\) iff \(x\) is a true statement on natural numbers involving \(\exists\), \(=\), \(+\),\(\times\), \(0\) and \(1\).
Example: There exists \(a,b,c \gt 0\) s.t. \(a^{11} + b^{11} = c^{11}\).
Proof of Gödel’s Theorem
Why care?
- Number theoretic statements more interesting than statements about programs. (or are they?)
- Nerd pride
- Useful technique
- Lesson: Computation can hide in surprising places.
Proof of Gödel’s Theorem
First step: Mixed integer statements: talk about both strings and integers.
Example 1: For every \(n\in \mathbb{N}\) there exists a string \(\alpha\in \{0,1\}^n\) such that every substring \(\alpha'\) of \(\alpha\) has \(|\text{no. zeroes} - \text{no. ones}| \leq 1\).
Example 2: There exists \(C\in \mathbb{N}\) such that for every \(n\in \mathbb{N}\) there exists a string \(\alpha\in \{0,1\}^n\) such that every “arithmetic progression substring” \(\alpha'\) of \(\alpha\) has \(|\text{no. zeroes} - \text{no. ones}| \leq C\).
Thm: \(MIS:\{0,1\}^* \rightarrow \{0,1\}\) is uncomputable
Approaches for \(MIS\) uncomputability
Thm: \(MIS:\{0,1\}^* \rightarrow \{0,1\}\) is uncomputable
Approach 1: Given NAND++ program \(P\), build MIS \(\Phi_P\) s.t. \(\Phi_P(H)\) is true iff \(H\) encodes valid sequence of configurations \(\alpha^0, \ldots, \alpha^{T-1}\) of an execution of \(P\) on \(0\).
Approach 2: Build MIS \(\Phi(E)\) if \(E = e_0,\ldots,e_T\) sequence of reductions of \(\lambda\) expression \(exp\).
Approach 3: Turing machines, cellular automata, …
All cases: Consistency can be checked by local operations
Configurations
Def: Configuration of NAND++ program encodes all the state during a computation: scalar variables, array variables, index variable.
What you need to know:
A configuration is a string.
If \(\beta = NEXT_P(\alpha)\) then they agree in all but \(O(1)\) coordinates.
COROLLARY 1: Find MIS \(\varphi_P\) such that \(\varphi_P(\alpha,\beta)\) true iff \(\beta = NEXT_P(\alpha)\).
COROLLARY 2: Find MIS \(\Psi_P\) such that \(\Psi_P(H)\) true iff \(H\) encodes list \(\alpha^0,\ldots,\alpha^{t-1}\) such that \(\alpha^{i+1} = NEXT_P(\alpha^i)\).
COROLLARY 3: \(MIS\) is uncomputable.
From strings to integers.
Define sequence of primes \(p_0 \lt p_1 \lt p_2 \lt \ldots\) s.t. there is a quantified integer statement \(P(p,i)\) which is true iff \(p=p_i\).
Map \(x \in \{0,1\}^n\) to \(X\in \mathbb{N}\) where \(X= p_0^{x_0}p_1^{x_1}\ldots p_{n-1}^{x_{n-1}}\)
\(x_i\) is mapped into \(\exists_p P(p,i) \wedge DIVIDES(p,x)\)
Sequence is simply \(p_i\) is smallest prime larger than \((C+i)^3\).
\(P(p,i) = PRIME(P) \wedge\)
\(\forall_{q} (PRIME(q) \wedge q\gt(C+i)\times (C+i)\times(C+i)) \Rightarrow q \geq p\)