CS 121, Lecture 11 Godel's Incompleteness Theorem

N or Space for next slide, P for previous slide, F for full screen, M for menu

Lec 11: Godel’s Incompleteness Theorem

Boaz Barak (instructor), Salil Vadhan (co-instructor), Juan Perdomo (Head TF).

Team: Aditya Mahadevan, Brian Sapozhnikov (surveys), Chan Kang (extension), Gabe Abrams (Ed Tech), Gabe Montague (NAND web), Jessica Zhu (proof workshops), John Shen, Juan Esteller (NAND implementation), Karl Otness, Katherine Binney, Mark Goldstein (clicker expert), Stefan Spataru, Susan Xu, Tara Sowrirajan (mushroom forager), Thomas Orton (Advanced Section)

http://tiny.cc/cs121

Slides will be posted online.

Laptops/phones only on last 3 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 proof is a piece of text whose existence certifies a statement is true.

What is a proof?

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. Why?

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$.

Godel’s Incompleteness Theorem: If a proof system is sound, effective, and sufficiently rich, then it is incomplete.

Godel’s Incompleteness Theorem: Proof idea

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 impossbile

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 impossilbe; 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$”

If $x$ is true, then it has no proof.

If $x$ is false, then it has a proof, and then it is true ,and then it has no proof ,…

Roughly speaking:

Use quantifiers to simulate computation.

Find a program that can print its own code

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 algortithm 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$ 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: $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}} \neg DIVIDES(a,p-1) \vee (a \neq 2) \vee (a \neq 1) \vee (a \neq p-1))$

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$”.

Example: For every $n$, there exists a prime $p \gt n$ of the form $p=2^n+1$.

MRDP Thm: $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.

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.

$x$ = “There are strings and integers that satisfy some locally checkable properties”

Example 1: For every $i$ in which the string contains the pattern $000$, there is a $j \gt i$ so that the string contains the pattern $111$.

Example 2: $\alpha \in \{0,1\}^*$ and $\beta \in \{0,1\}^*$ are equal to each other except that one instance of $110011$ in $\alpha$ is replaced with $000111$ in $\beta$

Example 3: $\alpha \in \{0,1\}^n$ satisfies that for every $i \in [n]$, $\alpha_i = 1 - \alpha_{\lfloor i/2 \rfloor}\alpha_{\lfloor i/3 \rfloor}$

Thm: $MIS:\{0,1\}^* \rightarrow \{0,1\}$ is uncomputable

Three approaches for $MIS$ uncomputability

Thm: $MIS:\{0,1\}^* \rightarrow \{0,1\}$ is uncomputable

Approach 1: Build MIS $\Phi(\Delta)$ is true iff $\Delta$ encodes “deltas” of halting compututation of $P$ on $z$.

Approach 2: Build MIS $\Phi(C)$ if $C=c_0,\ldots,c_T$ sequence of configurations of halting computation of $P$ on $z$.

Approach 3: Build MIS $\Phi(E)$ if $E = e_0,\ldots,e_T$ sequence of reductions of $\lambda$ expression $exp$.

All cases: Consistency can be chacked by local operations

From strings to integers.

Define sequence of primes $p_0\ltp_1\ltp_2\lt\ldots$ s.t. there is a quantified integer statement $PRIMESEQ(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 PRIMESEQ(p,i) \wedge DIVIDES(p,x)$ $DIVIDES(a,b)=\exists_c b=a\times c$

Sequence is simply $p_i$ is smallest prime larger than $(i+C)^3$.

Lec 11: Godel’s Incompleteness Theorem

Uncomputability

A brief history of math

A brief history of math (2)

What is a proof?

What is a proof?

Godel’s Incompleteness Theorem: Proof idea

Nothing is Impossible (Chris Harris)

Gödel statement

CS version of Gödel Theorem

High level lesson

High level lesson

Proof of Gödel’s Theorem

Proof of Gödel’s Theorem

Three approaches for \(MIS\) uncomputability

From strings to integers.