Undecidability for dummies

It's been my experience that many important "complex" theorems are complicated in only one or two parts. Oftentimes, if you're willing to accept a lemma or two without proof, you can understand the entire thing. So this is a post explaining what I think is a fairly complicated topic, but there is a piece I don't try to prove. I hope the result is something that's understandable to anyone with a little programming experience.

One of the things which fascinates me most are "incompleteness" theorems. I understand how we can look at some individual solution and determine that it doesn't solve some problem, but the proof that no solutions exist seems a lot harder.

A foundational result in theoretical computer science is the undecidability of the halting problem. This states that, given some program P, there is no general way to tell if P will run forever or if it will eventually stop. For example, the following program:

for each integer x:
	if x + 1 = x, then halt
	else go on to the next integer

will run forever, because there's not integer which is the same as itself with one added to it. This program:

for each integer x:
	if x + 0 = x, then halt
	else go on to the next integer

will halt immediately.

So how can we prove that there is no general method to tell whether a program will halt? It's a proof by contradiction: suppose we have some method, let's say M, of telling if a program will halt. Consider the following program:

if M says *this program* will halt, then run forever
else if M says this program will run forever, then halt

For any method M, it will fail to correctly predict the behavior of our program. So for any method M, there must be at least one program whose behavior it fails to predict, which proves our theorem.

---

When I first learned this, I felt (and to a certain extent still feel) that it was kind of a cheap trick. In retrospect, I think this was due to the program's ability to refer to itself. This is the complexity that I left out of the post, but the basic idea isn't that hard: we can assign a natural number to every program (i.e. there's a "first" program, a second program, ...). Once we've done that, a program "referring to itself" can be accomplished via these numbers, e.g. program 12345 referring to program 12345.

One simple yet important extension to the halting problem is Rice's Theorem, which basically says that you can never prove anything about a program. Want to prove that your program won't crash? Tough. Someone asks you to prove your algorithm always gives the right answer? No can do.

If you're interested, you can see a list of undecidable problems, the most famous of which is Hilbert's tenth.

Divisible by 3

You probably know the rule of thumb to check if a number is divisible by three: add the digits and see if that number is divisible by three. E.g. 3627 is divisible by three since 3+6+2+7=18, which is divisible by three.

Here is a short proof of this, as well as some extensions. Note that $3627=3*10^3+6*10^2+2*10+7$; if we consider $p(x)=3x^3+6x^2+2x+7$, then $3627=p(10)$. Finding the sum of the digits is equivalent to finding $p(1)$. Our claim is that $p(10)$ is divisible by three if and only if $p(1)$ is divisble by three.

A more general theorem holds, in fact: if $a\equiv b \bmod m$ then $p(a)\equiv p(b) \bmod m$ for any polynomial $p$. A colloquial phrasing is "if a and b have the same remainder after dividing by m, then $p(a)$ and $p(b)$ have the same remainder after dividing by m." In our case, we're just interested in the case where the remainder is zero. The proof of this follows directly from the properties of modular arithmetic, so I won't bore you with it.

Using this theorem, we find that $10\equiv 1 \bmod 3$, so $p(10)\equiv p(1) \bmod 3$, just like we wanted. Note that $10\equiv 1\bmod 9$ as well, so the same "add up the digits" shortcut works with division by 9.

We can extend this to more complicated shortcuts. You might know the trick for divisibility by 11: alternately add and subtract the digits. For example, $1-2+1=0$ so $121$ is divisible by 11.

This is just another instance of our theorem. Since $10\equiv -1 \bmod 11$, $p(10)\equiv p(-1)\bmod 11$ and $p(-1)$ is just alternately adding and subtracting the digits.

Wikipedia has an extensive list of divisibility "shortcuts", some of which seem more complex than just doing long division, but hopefully this illuminates the reasoning behind some of them.