Does Godel's incompleteness theorem entail that the physicist's dream of a Theory of Everything (ToE) is impossible? It's a question which, curiously, has received scant attention in the philosophy of physics literature.
To understand the question, first we'll need to introduce some concepts from mathematical logic: A theory T is a set of sentences, in some language, which is closed under logical implication. In other words, any sentence which can be derived from a subset of the sentences in a theory, is itself a sentence in the theory. A model M for a theory T is an interpretation of the variables, predicates, relations and operations of the langauge in which that theory is expressed, which renders each sentence in the theory as true. Theories generally have many different models: for example, each different vector space is a model for the theory of vector spaces, and each different group is a model for the theory of groups. Conversely, given any model, there is a theory Th(M) which consists of the sentences which are true in the model M.
Now, a theory T is defined to be complete if for any sentence s, either s or Not(s) belongs to T. A theory T is defined to be decidable if there is an effective procedure of deciding whether any given sentence s belongs to T, (where an 'effective procedure' is generally defined to be a finitely-specifiable sequence of algorithmic steps). A theory is axiomatizable if there is a decidable set of sentences in the theory, whose closure under logical implication equals the entire theory.
It transpires that the theory of arithmetic (technically, Peano arithmetic) is both incomplete and undecidable. Moreover, whilst Peano arithmetic is axiomatizable, there is a particular model of Peano arithmetic, whose theory is typically referred to as Number theory, which Godel demonstrated to be undecidable and non-axiomatizable. Godel obtained sentences s, which are true in the model, but which cannot be proven from the theory of the model. These sentences are of the self-referential form, s = 'I am not provable from A', where A is a subset of sentences in the theory.
Whilst the application of mathematics to the physical world may be fairly untroubled by the difficulties of self-referential statements, undecidable statements which are free from self-reference have been found in various branches of mathematics. For example, it has been established that there is no general means of proving whether or not a pair of 'triangulated' 4-dimensional manifolds are homeomorphic (topologically identical).
Any theory which includes Number theory will be undecidable, hence if a final Theory of Everything includes Number theory, then the final theory will also be undecidable. The use of Number theory is fairly pervasive in mathematical physics, hence, at first sight, this appears to be highly damaging to the prospects for a final Theory of Everything in physics.
However, it is still conceivable that a final Theory of Everything might not include Number theory, and in this case, a final Theory of Everything could be both complete and decidable. In addition, even if a final Theory of Everything is incomplete and undecidable, it is the models M of a theory which purport to represent physical reality, and whilst the theory of a model Th(M) may be undecidable, it is guaranteed to be complete. That is, every sentence in the language of the theory will either belong or not belong to Th(M).