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.

E[Impact]

Robin Hanson talks about how economists signal:

Economists like to point out there’s almost no chance that your vote is going to determine an election. So one of the things an economists like to do to show off that they’re clever economists is to not vote and to say to everybody, hey I’m smarter than all the rest of you! See, I understand that by voting, it’s not going to make any difference, anyway.

I'll trust his analysis that, psychologically, not voting is the economist version of a peacock's tail. But the more interesting question is: are these economists right? Is voting a bad idea?

It's hard to make a consequentialist case for voting in elections, but a related concept - voting with your dollars - doesn't fall victim to the same trap.

Suppose a large chicken producer like Tyson hires farmers to grow as many chickens this year as it sold last year. So if they sold 50k chickens last year, they'll buy 50k chickens to resell this year. Because they are a big company, they only track these numbers to the nearest thousand. So 999 times out of a thousand, your purchases don't even show up on Tyson's radar.

The vast majority of the time, your purchases won't affect anything. So there can't be any moral imperative to not eat chicken, since it will almost certainly have no impact, right?

The problem is: sure, there's only a one in a thousand chance that you'll impact Tyson's chicken production. But if you do have an impact, you'll lower their production by a thousand chickens.

Your expected impact is the likelihood you make any change, multiplied by size of that change. If you have a 1/1000 chance of making an impact, and you impact their production by 1000 chickens, then your expected impact is 1/1000 * 1000 = 1. The same goes for if your odds are one in two or one in a billion - your expected impact is always 1.

So stay home from the polls next November if that will get you into the cool kid crowd in the economics department. But make sure you stay home with a vegan dinner.

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.