May 18 2009
In 1942, the logician Kurt Gödel and Albert Einstein became close friends; they walked to and from their offices every day, exchanging ideas about science, philosophy, politics and the lost world of German science in which both had grown up. By 1949, Gödel had produced a remarkable proof - “ In any universe described by the Theory of Relativity, time cannot exist.“
Einestein endorsed this result reluctantly, but he could find no way to refute it, and in the half -century since then, neither has anyone else. Among all the contributions of Gödel - this one is certainly the Queen and most of the times goes unnoticed.
In case, you are intersted to know more about this particular result of Gödel – refer “The Forgotten Legacy of Gödel and Einstein” by Palle Yourgrau.
——-
For those readers, who are unaware of Gödel’s contributions to Computer Sciences and Mathematics; I compose this brief overview about Gödel’s result from Aaronsons’ lectures.
There’s an amazing result called Gödel’s Completeness Theorem, which says that these rules are all you ever need. In other words: if, starting from some set of axioms, you can’t derive a contradiction using these rules, then the axioms must have a model (i.e., they must be consistent). Conversely, if the axioms are inconsistent, then the inconsistency can be proven using these rules alone.
Well, alright, I guess a year later he proved the Incompleteness Theorem. See, the Completeness Theorem was his Master’s thesis, and the Incompleteness Theorem was his PhD thesis. Apparently, one of his PhD examiners didn’t want to give him a degree because the PhD thesis was “too similar to the Master’s thesis.”
The Incompleteness Theorem says that, given any consistent, computable set of axioms, there’s a true statement about the integers that can never be proved from those axioms. Here consistent means that you can’t derive a contradiction, while computable means that either there are finitely many axioms, or else if there are infinitely many, at least there’s an algorithm to generate all the axioms. (If we didn’t have the computability requirement, then we could simply take our “axioms” to consist of all true statements about the integers! In practice, that isn’t a very useful set of axioms.)
Once you have Turing’s results(there doesn’t exist a computer to solve the Halting problem), Gödel’s results fall out for free as a bonus. Why? Well, suppose the Incompleteness Theorem was false — that is, there existed a consistent, computable proof system F from which any statement about integers could be either proved or disproved. Then given a computer program, we could simply search through every possible proof in F, until we found either a proof that the program halts or a proof that it doesn’t halt. (This is possible because the statement that a particular computer program halts is ultimately just a statement about integers.) But this would give us an algorithm to solve the halting problem, which we already know is impossible. Therefore F can’t exist.
By thinking more carefully, we can actually squeeze out a stronger result — if a system is consistent, then it can’t prove its own consistency!!
Let P be a program that, given as input another program Q, tries to decide whether Q halts by the strategy above (i.e., searching through every possible proof and disproof that Q halts in some formal system F). Then , suppose we modify P to produce a new program P’ that
- runs forever if Q is proved to halt given its own code as input, or
- halts if Q is proved to run forever given its own code as input.
Now suppose we feed P’ its own code as input. Then we know that P’ will run forever, without ever discovering a proof or disproof that it halts. For P’ finds a proof that it halts, then it will run forever, and if it finds a proof that it runs forever, then it will halt, which is a contradiction.But there’s an obvious paradox: why isn’t the above argument, itself, a proof that P’ will run forever given its own code as input? And why won’t P’ discover this proof that it runs forever — and therefore halt, and therefore run forever, and therefore halt, etc.?
The answer is that, in “proving” that P’ runs forever, we made a hidden assumption: namely that the proof system F is consistent. If F was inconsistent, then there could perfectly well be a proof that P’ halts, even if the reality was that P’ ran forever.
But this means that, if F could prove that F was consistent, then F could also prove that P’ ran forever — thereby bringing back the above contradiction. The only possible conclusion is that if F is consistent, then F can’t prove its own consistency. This result is sometimes called Gödel’s Second Incompleteness Theorem.
