What does Godël’s Incompleteness Theorem actually mean and imply? I just saw Ted-Ed’s video on this topic and didn’t fully understand what it means or what the implications of this are.
In: 742
The dream of math is to be able to say “if a fact is true, then we can prove it”. By which I mean, write a mathematical proof using the rules of math and logic. This would make the math “complete”. Every true thing can be proven and every provable thing is true. Beautiful.
Godël came along and laughed at this idea. He demonstrated that it is not true, and the proof is demonstrating that you can build a statement that must be true, but for which the math cannot prove. Thus no matter what type of math you’re using, you can just build your unprovable statement. Ergo, “if it’s true, then we can prove it” is already incorrect.
One of the most common real-world examples is the computing halting problem. No computer program can consistently, reliably and correctly answer the question “will this program halt?” (as opposed to getting stuck in an infinite loop). The proof builds a program which is self-contradictory, but only assuming that the halting problem can be solved. Ergo, the problem cannot be solved. However, intuitively you can imagine that yes, some programs will never finish running, so in theory it should be possible to perform such classification. However we cannot reliably give a thumbs-up/down verdict using computing to make that decision. It’s a little example of incompleteness in computing. A computer program cannot analyse a computer program and figure it out while being limited to the confines of what we define a computer as.
Latest Answers