Introduction
In our last post, we defined computation as following a recipe, or an algorithm, to get from a problem to a solution. For centuries, mathematicians believed that with enough brainpower and the right set of rules (axioms), they could create a perfect, complete system of mathematics - a system that could prove or disprove any mathematical statement imaginable.
They dreamed of a “master recipe” for all of math.
Then, in 1931, a quiet, brilliant Austrian logician named Kurt Gödel came along and proved that this dream was impossible. He didn’t just find a problem math couldn’t solve yet; he proved that there would always be problems it could never solve.
The Dream of a Perfect System
Imagine you have a set of fundamental truths in mathematics, like "" or “a straight line is the shortest distance between two points.” These are your axioms. From these axioms, you can use the rules of logic to build up more complex truths, called theorems.
The hope was that this system would be:
- Consistent: It would never produce contradictions. You could never prove that and .
- Complete: It could prove or disprove any statement you could possibly phrase in the language of math.
Everyone assumed this was not only possible but the ultimate goal of mathematics. It was just a matter of finding the right axioms.
Gödel’s Bombshell: The Incompleteness Theorems
Gödel turned this entire idea on its head. He did it by creating a mathematical statement that was brilliantly paradoxical. In simple terms, the statement he constructed said:
“This statement cannot be proven.”
Think about that for a second. Let’s call this statement ‘G’.
- What if ‘G’ is false? If it’s false, then its claim (“This statement cannot be proven”) must be wrong. That would mean the statement can be proven. But if you can prove it, it must be true. This is a contradiction. So ‘G’ cannot be false.
- What if ‘G’ is true? If it’s true, then it’s exactly what it says it is: a statement that cannot be proven.
So here we have it: a statement, ‘G’, that is true, but it is impossible to prove using the very system of mathematics it’s written in.
This was Gödel’s First Incompleteness Theorem. It says that for any consistent formal system of mathematics powerful enough to describe basic arithmetic, there will always be true statements that are unprovable within that system.
Math, by its very nature, is incomplete.
Why This Matters for Computers
Gödel published this before modern computers even existed, but he had unknowingly discovered a fundamental limit of what they could ever hope to achieve.
Remember, computation is just executing an algorithm - a set of logical steps. Computers are machines that run on formal systems, just like the one Gödel was studying.
His work implied that you could never create a computer program that could solve all mathematical problems. No matter how clever your algorithm, there would always be questions it simply couldn’t answer. It’s not a matter of not having enough processing power or time; it’s a fundamental wall built into the fabric of logic itself.
Math alone wasn’t going to be enough to build the all-powerful thinking machines people might have imagined. The search was on for a new way to think about what is, and isn’t, computable. This search would lead others, like Alonzo Church and Alan Turing, to invent their own models of computation, which we’ll explore next.