Gödel’s First Incompleteness Theorem for Programmers

Gödel’s incompleteness theorems have been hailed as “the greatest mathematical discoveries of the 20th century” — indeed, the theorems apply not only to mathematics, but all formal systems and have deep implications for science, logic, computer science, philosophy, and so on. In this post, I’ll give a simple but rigorous sketch of Gödel’s First Incompleteness Theorem. Formally, it states that:

Any consistent formal system $S$ within which a “certain amount of elementary arithmetic” can be carried out is incomplete; i.e., there are statements of the language of $S$ which can neither be proved nor disproved in $S$.

This is a rigorous proof with a focus on software engineers and programmers. I based this post on this excellent lecture I found on YouTube a little while ago. When I first learned how to prove Gödel’s incompleteness theorems, it was in the context of a metalogic class that dealt with all kinds of confusing and deep topics like Henkin construction and transfinitary logic. But as it turns out, Gödel can be understood without much fanfare!

Introduction

We start on this journey by defining a couple of things. First, we define $F$ as a function that takes a positive integer and returns either 0 or 1. Here’s an example of such an $F$:

$$isOdd\left(x\right)=\{\begin{array}{cc}0& x\text{is even}\\ 1& x\text{is odd}\end{array}$$

So, we see that $isOdd\left(2\right)=0$ or that $isOdd\left(38943981\right)=1$. We can define $F$ however we want — as long as the output will either be a 0 or a 1. Let $Q$ be the set of all such functions $F$.

We say that $F$ is computable if there exists a computer program (or proof) $P$ that takes as input $x$ and returns $F\left(x\right)$. It goes without saying that $P$ must complete within finite time and must be correct. So let’s look at some code. Is $isOdd\left(x\right)$ computable?

function isOdd(x) {
  return (x % 2);
}

Looks like it! This program will always return 0 when $x$ is even and 1 when $x$ is odd. What about a more complicated example:

$$isPrime\left(x\right)=\{\begin{array}{cc}0& x\text{is not prime}\\ 1& x\text{is prime}\end{array}$$

Is $isPrime$ computable?

function isPrime(x) {
  if(x < 2) return 0;
  if(x == 2) return 1;
  for(var i = 2; i < x; i++) {
    if(x % i === 0) return 0;
  }
  return 1;
}

Courtesy of this Stack Overflow answer, it looks like it is. Let $A$ be the set of all computable functions in $Q$. We just found out (the hard way) that $isOdd$ and $isPrime$ are in $A$ — that is, they are computable.

But here’s the big question: are all functions in $Q$ computable? Or, equivalently:

$$A\stackrel{?}{=}Q$$

If $A=Q$, then Gödel was wrong, so we need to figure out a clever way to show that $A\subset Q$. In other words, we need to show that there are some functions that take positive integers $x$ as input and return either a 0 or a 1 that we simply cannot implement.

The Set-up

So how do you show that some functions $F$ are not computable? Well, let’s do it the old-fashioned way. Since we’re already using JavaScript, let’s just print out every single JavaScript program. Ever. To make things easy, we can order them alphabetically and by length (in lexicographical order). To make things even easier, we can just throw out programs that loop infinitely or don’t return a 1 or a 0. When all is said and done, we’re left with an infinite number of programs that probably start out like this:

function F1(x) {
  return 0;
}

function F2(x) {
  return 1;
}

And further down the line…

function Fn(x) {
  return 1 - 1;
}

And further down the line…

function Fn(x) {
  return x / x;
}

And further down the line…

function Fn(x) {
  return (x % 2); // hey, this is the isOdd function from before!
}

And even further down the line…

function Fn(x) {
  return (x % 2) / 1;
}

And even further down the line…

function Fn(x) {
  let someRandomVariable = x ^ x;
  let abcd = someRandomVariable / y;
  if (abdc > -12) return 0;
  return 1;
}

You get the picture. Now we have every single possible program written in JavaScript that outputs 0 or 1. In other words, we just populated $A$: we now have a program that goes with every single computable function. Let’s put them in a big table called $T$. The column headings indicate inputs (positive integers) and the rows indicate computable functions (and, implicitly, the programs that implement them).

	1	2	3	4	5	6	7	…	n	…
$f_1$	$f_1\left(1\right)$	$f_1\left(2\right)$	$f_1\left(3\right)$	$f_1\left(4\right)$	$f_1\left(5\right)$	$f_1\left(6\right)$	$f_1\left(7\right)$	…	$f_1\left(n\right)$	…
$f_2$	$f_2\left(1\right)$	$f_2\left(2\right)$	$f_2\left(3\right)$	$f_2\left(4\right)$	$f_2\left(5\right)$	$f_2\left(6\right)$	$f_2\left(7\right)$	…	$f_2\left(n\right)$	…
…
$f_o$	1	0	1	0	1	0	1	…	$f_o\left(n\right)$	…
…
$f_p$	0	1	1	0	1	0	1	…	$f_p\left(n\right)$	…
…
$f_i$	$f_i\left(1\right)$	$f_i\left(2\right)$	$f_i\left(3\right)$	$f_i\left(4\right)$	$f_i\left(5\right)$	$f_i\left(6\right)$	$f_i\left(7\right)$	…	$f_i\left(n\right)$	…
…

You’ll notice that $isOdd$ and $isPrime$ also made it in our table (as fo and fp, respectively). So far, so good. It seems that we thought of everything. But let’s define a new function:

$$\overline{f}\left(i\right)=1-f_i\left(i\right)$$

Where $f_i$ is the $i$th function in table $T$. First, let’s make sure we’re convinced that $\overline{f}$ is well-formed. The input $i$ is an integer. $f_i\left(i\right)$ will return either a 0 or a 1, given that $f_i$ has a row populated in $T$. And finally, $1–0=1$ or $1–1=0$, so both cases are well-formed.

$$\overline{f}\left(i\right)=\stackrel{\text{will return}0\text{or}1}{\stackrel{}{1-\underset{\text{will return 0 or 1}}{\underset{}{f_i\left(i\right)}}}}$$

Therefore, $\overline{f}$ is in $Q$, but is it in $T$?

The Proof

Seeing why $\overline{f}$ can’t be in $T$ is pretty straightforward. Suppose $\overline{f}$ is $f_2$. Like we’ve seen so far, $f_2\left(2\right)$ can either be 0 or 1. But if $f_2\left(2\right)=0$, then $\overline{f}\left(2\right)=1-f_2\left(2\right)=1-0=1$. So, we have:

$$f_2\left(2\right)\ne \overline{f}\left(2\right)$$

Whoops. Okay, so it wasn’t $f_2$. That would be too easy. What about $f_{421}$? If $f_{421}\left(421\right)=1$, then $\overline{f}\left(421\right)=1-f_{421}\left(421\right)=1-1=0$. So, we have:

$$f_{421}\left(421\right)\ne \overline{f}\left(421\right)$$

As it turns out, any computable function we pick out of $T$ (and implicitly $A$) will disagree with $\overline{f}$ at at least one output. And therefore, we have the amazing finding that:

$$A\subset Q$$

Conclusion

In other words, there are some things, like $\overline{f}$, we can’t prove or disprove in formal systems. Given that we’ve been working with JavaScript in this post, it makes sense that it’s impossible to reference the program’s own lexicographic index in $T$. With that said, you might be tempted to think that there might be a way to “get around” this limitation; if your language was clever enough, perhaps. I’ll eventually write about Gödel’s Second Incompleteness Theorem, which drives the nail in the coffin: there’s no way to get around this.