Stephen Hawking believes that Gödel's Incompleteness Theorem makes the search for a 'Theory of Everything' impossible. He reasons that because there exist mathematical results that cannot be proven, there exist physical results that cannot be proven as well. Exactly how valid is his reasoning? How can he apply a mathematical theorem to an empirical science?
Logic – Does Gödel’s Incompleteness Theorem Affect Theoretical Physics?
incompletenesslogicphysics
Related Solutions
The tricky bit is in step 3, and the distinction between "prove" and "imply". Let $T$ be our theory, and Con($T$) be the statement that $T$ is consistent. It is true that Con($T$) implies that we cannot prove the Gödel statement $G$. This does not immediately imply that the statement "Con($T$) implies $G$ is not provable in T" is provable in $T$. The point of the Second Incompleteness Theorem is to show that that statement is indeed provable in $T$.
Let me phrase the argument in somewhat more modern terms:
Goedel constructs a means of encoding any computer program's source code by an arithmetic formula, such that he can prove that, for any program which eventually outputs "YES", Peano Arithmetic (PA) proves the corresponding formula, and for any program which eventually outputs "NO", PA disproves the corresponding formula.
Then Goedel* constructs a computer program with the code "Search through all the possible proofs in PA till you find either a proof or a disproof of the formula corresponding to my source code. If you find a proof first, output 'NO'; if you find a disproof first, output 'YES'. (If you never find either, just keep on searching forever...)" [This is a recursively defined program, in that it refers to its own source code, but that's ok: we understand well how to write up such recursive programs, and even how to compile them to languages that do not directly support recursion. This compilation is essentially what "diagonalization" does]
Now, let p be the formula corresponding to this program's source code. So long as PA either proves or disproves p, this program will eventually output something. But if this program outputs 'YES', then PA must prove p (by the second paragraph) and also disprove p (this is the only way the program ever outputs 'YES'). Similarly, if this program outputs 'NO', then PA must disprove p (by the second paragraph) and also prove p (this is the only way the program ever outputs 'NO'). Thus, if PA either proves p OR disproves p, it necessarily proves p AND disproves p; they're a package deal. So if PA is "complete", then it is inconsistent.
That is the mechanism of the result. It's quite concrete and doesn't depend on any handwavy arguments about meta-statements. It's just a matter of A) knowing how to construct computer programs which can access their own source code, and B) having an appropriate representation of such programs in PA (or whatever system one is interested in), in the sense of the properties of the second paragraph of this post.
[*: I say Goedel, but I actually mean Rosser, five years later; I've chosen to use his approach (which yields a slightly stronger result than Goedel in this context, albeit one which generalizes less) because I think it might be simpler to discuss for now]
Best Answer
Hawking's argument relies on several assumptions about a "Theory of Everything". For example, Hawking states that a Theory of Everything would have to not only predict what we think of as "physical" results, it would also have to predict mathematical results. Going further, he states that a Theory of Everything would be a finite set of rules which can be used effectively in order to provide the answer to any physical question including many purely mathematical questions such as the Goldbach conjecture. If we accept that characterization of a Theory of Everything, then we don't need to worry about the incompleteness theorem, because Church's and Turing's solutions to the Entscheidungsproblem also show that there is no such effective system.
But it is far from clear to me that a Theory of Everything would be able to provide answers to arbitrary mathematical questions. And it is not clear to me that a Theory of Everything would be effective. However, if we make the definition of what we mean by "Theory of Everything" strong enough then we will indeed set the goal so high that it is unattainable.
To his credit, Hawking does not talk about results being "unprovable" in some abstract sense. He assumes that a Theory of Everything would be a particular finite set of rules, and he presents an argument that no such set of rules would be sufficient.