Portrait of Kurt Gödel ca. 1926
In the early 20th century, some huge nerds came up with a question, a legendary problem, the math problem to end all math problems: "das Entscheidungsproblem", or in English, "the decision problem".
The actual problem is disarmingly simple given its scary German name:
Can you make an algorithm that can take any statement and tell you if it's true or false?
Think about that for a moment. You might wonder what led them to this question. You might also wonder what the answer is. (It's "no", but read on to understand why.)
It's important to know what's true and what's false, isn't it? But saying what's true and what's false isn't always so simple. We know that the Pythagorean Theorem is true, and we know that Darwin's theory of natural selection is true, but are they the same *amount* true, or perhaps true in different ways? Is there a way to say things are true or false that's *completely independent* of the way human beings think about the world?
Humans aren't infallible; any human knows that we're wrong sometimes. Even today, some people don't "believe in" natural selection. I feel confident in saying they're wrong, but *why*? Are they wrong just because I said so? Would an alien from another planet, brought up to speed on all the relevant information, agree with me? In fact, what *would* we expect aliens to agree with us about? Seems reasonable to expect they'd agree with us about the Pythagorean Theorem at least - but *why*? Are there truths so universal that they are *irrefutable*, truths so universal that for a person to disagree with them is sufficient grounds to dismiss everything that person says?
Seems like "mathematics" would be a pretty good candidate for such irrefutable truth. In math, we have a concept of "proving" something that gets really close to the level of universality we're going for. When some theorem has been "proven" in mathematics, it means that theorem isn't just true, it has *always* been true and always will be, eternally. Not just independent of humans, but seemingly independent of and transcending *the physical universe*.
But how do we *know* that our proofs are right? How do we know that mathematic theorems are true?
Huge nerds were very interested in this problem. A mathematician named David Hilbert thought that we should be able to find a small, finite handful of "axioms": truths that are held to be self-evident. The axioms would be very simple and abstract, but anything else that could be proven true in mathematics would base its truth on these axioms. If you could show that something contradicted the axioms, that'd mean that it can't possibly be true. The project/goal to find this set of axioms and use them to show the correctness of the rest of math, everything from 2 + 2 = 4 to Fermat's Last Theorem, was called "Hilbert's Program". (The word "program" here is not in the same sense as in the phrase "computer program".)
So that's where das Entscheidungsproblem came from: it's really the question of whether Hilbert's Program is actually possible. Given a small set of self-evident axioms, can we make some kind of equation or fixed series of steps that could show whether *any* statement is true or false?
Actually, as huge nerd Kurt Gödel was able to show, we can't. He showed that for *any* set of axioms, if those axioms were enough to show that arithmetic is true (that 2 + 2 = 4), then they *could not* allow you to classify *every* statement as true or false. The best you could do is classify statements as true, false, or "undecidable". The classic example of an "undecidable" statement is, "This statement is false". If it's true that that statement is false, well, that means it's false, actually. Which means it's true, because it says that it's false. Trying to tell if "This statement is false" is true takes you in a loop.
He demonstrated that any system that's powerful enough to describe numbers *had* to be powerful enough to make such self-contradictory statements. This is because you can encode statements *with* numbers, and if you can encode statements with numbers, then you can do math... to statements. If you're such a huge nerd that that's intrinsically interesting to you on its own, you can read more about it here:
It wasn't enough that these huge nerds had both aspired to universal truth and conclusively shown that it was unattainable. Alan Turing, a huge *gay* nerd like myself, was interested in deciding undecidability. If you can't sort everything into true and false, but you could conceptualize everything as true, false, or undecidable, then could you *find out* if a given statement is undecidable?
In other words, can you tell if trying to find the truth or falsehood of a statement will put you in an infinite loop?
This is what's known as the "Halting problem". To find the answer to the halting problem, Turing tried to imagine what would be the simplest possible system that could do math. If you could find the simplest possible system that could do anything that's possible to work out in mathematics, then anything true about that system would be true about everything in mathematics. Turing was the first to come up with the idea of a "Turing machine". His idea of a Turing machine consisted of
He showed that anything that wasn't undecidable could be calculated by this abstract system. He also showed that, given a Turing machine, including its tape and its states, it was not possible to tell whether that machine would halt or keep running forever. This settled the matter forever: not only can't you always tell if a given statement is true or false, you can't even always tell if a given statement is true, false, or undecidable, because the question of whether or not a Turing machine is going to loop forever is itself undecidable.
That's a lot to take in. One thing that Turing's work shows is a clear, resounding answer to das Entscheidungsproblem: "no". There is no universal way to tell if statements are true or false.
But there's another thing that Turing's work shows, which is more interesting to people who *aren't* huge nerds obsessed with mathematics for its own sake: you can construct a machine that does math. Not only that, you can construct a *very simple* machine that can do *any* math that's possible to do at all. And it just so happened that World War Two was going on at the time, and the British government, under which Turing lived, was very interested in the idea of building such a machine, because they actually had a specific reason to want a machine that could do complex mathematics much faster than humans could. As some of you may have heard, they commissioned Turing to build a math-doing machine, the first thing that we would now point at and call a "computer" without any footnotes or qualifications, codenamed "the Bombe". Which takes us to our next chapter:
