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?
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.
@Sperners Lemma's comment should really be promoted to an answer. For indeed, it is a fairly gross misunderstanding of what Gödel's theorem says to summarize it as asserting that "there exist mathematical results that cannot be proven", for the reason he briefly indicates.
And incidentally, though it is a quite different issue, a Theory of Everything in the standard sense surely doesn't have to entail that every physical truth could be "proven". Let's bow to the wisdom of Wikipedia which asserts
A theory of everything (ToE) or final theory is a putative theory of theoretical physics that fully explains and links together all known physical phenomena, and predicts the outcome of any experiment that could be carried out in principle.
So NB a ToE is a body of laws which (if we assume that they are deterministic) will imply lots of conditionals of the form "if this happens, then that happens". But a ToE which wraps up all the laws into one neat package needn't tell us the contingent initial conditions, so (even if it is deterministic) need not tell us all the physical facts.
He can't. What would it even mean to "prove" a physical result? A ToE would condense all of the physical laws we've observed into a unified (and preferably compact) form, but as an empirical statement it would not imply, nor be implied (or even affected) by, results in mathematics. No mathematical axiom system has anything more to do with reality than any other one, including e.g. ones to which Godel's theorem does not apply, ones in which Godel's theorem cannot be proven, or even ones which are just inconsistent.
I saw this and thought this argument would not be complete without mentioning the work of david wolpert http://arxiv.org/abs/0708.1362
He shows that a theory of everything is impossible.
The accepted answer is good, but there are several additional interesting ways we can look at the question. (My personal favorite is "it doesn't matter"; see Part 3.)
Part 1: Wait and See
The first important fact is that many mathematical systems are both consistent and complete. Godel's Incompleteness Theorem only applies to systems that are "powerful enough to allow self-referentiality". In fact, Godel essentially proved his theorem by formalizing the self-referential sentence "this sentence is not provable". Consider that sentence for a moment. If that sentence can be written in a consistent mathematical system, then it's either true or else it's false. If it's false, then that means the sentence's claim is wrong, so it must be provable. And if it's provable, then it must be true. That's a contradiction. Therefore the sentence can't be false, so it must be true -- and so the statement's claim must be correct, and the statement itself must not be provable.
But there are plenty of mathematical systems that don't have the ability to express self-referential sentences like this one. In such a system, Godel's proof simply doesn't apply. The most famous two relevant examples are number theory, where Godel's proof holds, and therefore which is incomplete; and the first-order theory of the real numbers (specifically the theory of real closed fields), which is provably both consistent and complete, and in which Godel's proof cannot be formulated. See this answer for some good details.
From this perspective, the truth of Hawking's claim seems to boil down to the question of exactly what mathematics would be involved in a Theory of Everything. Would it only use the theory of real closed fields? Then it could easily be complete. Would it require a theory of integer arithmetic? Then indeed it would be incomplete. There isn't much more we can say here besides "it depends on the underlying math, so we'll have to wait and see".
Part 2: A Clever Argument
Now, it is easy to imagine someone responding to the above with the following kind of clever argument:
Any Theory of Everything would have to model the world in which we live, which includes mathematicians. Anything a mathematician can prove, the Theory of Everything can prove that a mathematician would prove. Therefore, a Theory of Everything has to be able to model all of mathematics, and so must be incomplete.
Although it's clever, it's wrong. Intuitively this is because there's a big difference between what a theory contains, and what it knows about. This is (slightly more than vaguely) analogous to the relationship between a computer and its data. If you stumble across a computer containing some unreadable files, you can still manipulate the bits in that file, or delete the file, or do anything else to it that the computer can do to files in general -- you just can't interpret those files as anything special. Now, it might be that one of the files is an encrypted tool that can hack into government databases. But that won't make any difference to you, since you don't have the extra knowledge necessary to understand and work with the file in that higher context.
As a more precise example, the theory of real numbers, and the theory of arithmetic on the integers, share the same relationship. The real numbers contain the integers, of course -- but the first-order theory of real numbers doesn't have the structure to recognize them as a distinguished set that follows the axioms of Peano arithmetic. Like the computer and its unreadable file, the reals contain the integers, but don't understand how they work.
The clever argument makes the same subtle mistake. Our universe contains mathematicians, so any Theory of Everything, which has to describe the universe in general, has to describe mathematicians in particular. But it doesn't have to describe mathematicians as distinguished entities, and it doesn't have to understand what they do. Just like the computer understood the encrypted file only as a series of bits, a Theory of Everything would likely only understand the mathematicians as a motion of particles and shifting energy gradients, rather than in terms of axioms and theorems. And this description could be entirely compatible with a mathematical framework that is both consistent and complete.
Part 3: It Doesn't Matter
Ok, so our Theory of Everything may or may not end up being mathematically incomplete. But if it were, what would that mean to us as humans? Sure, we'd import some purely-mathematical instances of incompleteness, e.g. the continuum hypothesis, but that wouldn't exactly keep a physicist up at night. So what would incomplete statements about the universe look like?
Well, incompleteness happens when there is a well-formed statement in our system, which is therefore either true or false (assuming a consistent system), but which we cannot prove or disprove. Of course "proof" and "disproof" don't technically exist in the physical sciences, and the closest thing we have is a large amount of evidence for or against. But let's not fuss over this distinction, as Hume's done that enough already. We can reasonably say that the claims we cannot prove or disprove empirically are the claims for which we cannot obtain evidence for or against. The term for such claims is unfalsifiable. Examples include Russell's Teapot, the dragon in Carl Sagan's garage, and many others.
And of course, the reason scientists are dismissive of unfalsifiable claims is that -- by definition -- the predictions they'd generate if true are the same as the predictions you'd get if they weren't true. If you can't see Russell's Teapot, it might be because it doesn't exist, but it might be because it's just too small! You'll often hear that unfalsifiability is a big deal for scientists because if there aren't differences in prediction, there's no way to experimentally decide between the two. This is true, but really short-sells what's going on. Unfalsifiability is a big deal because -- again by definition -- it means that whether or not the claim is true simply doesn't make a difference in any way.
With this in mind, what if we did end up with an incomplete Theory of Everything, and one in which there were physical examples of incompleteness in addition to mathematical examples? It's simple: it just wouldn't matter. By definition of how incompleteness works, these examples would have no empirical bearing on our existence. True, the Theory wouldn't be able to answer all questions that we could put to it -- but it would, again by definition, be able to answer any question that had even the faintest sliver of practical value. After all, a universe in which one of these unanswerable questions happened to be true would be empirically indistinguishable from a universe in which it happened to be false.
I am with Hawking on this one, though perhaps for different reasons.
It is not particularly difficult to show that some theoretical aspects of nature encode arithmetic. That is to say, as an example, that the theory of electrodynamics "contains" a copy of the natural numbers, together with addition and multiplication.
That is enough to satisfy Godel's theorem, to show that the theory of electrodynamics is "incomplete".
Of course, I have only described an argument that a single theory is incomplete, not that every theory is incomplete.
Since "Theory of Everything" needs to be expressed in some kind of proof, which will be partially mathematical and partially observation, it is not clear, how such proof can be validated without the component of mathematics.
Quantum computing might solve this problem for us, as it is able to operate using mathematical constants that are not verifiable or provable after they are executed, just like some theories in mathematics, that we can observe.