The implications of Gödel’s Theorem are profound. A full understanding of its implications is not restricted to math professionals, however – there are numerous books that have addressed Gödel, aimed at a layman audience. Of these the most famous is Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas R. Hofstadter. That’s a book that every geek needs to have on their bookshelf. However, there are many more, and short excerpts from many of these books on the topic of Gödel have been compiled in one place.
The most powerful explanation of Gödel is to simply restate its proof in general terms. That proof, originally published in Infinity and the Mind by Rudy Rucker, is reproduced below (courtesy of Miskatonic.org).
1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
3. Smiling a little, Gödel writes out the following sentence: “The machine constructed on the basis of the program P(UTM) will never say that this sentence is true.” Call this sentence G for Gödel. Note that G is equivalent to: “UTM will never say G is true.”
4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.
5. If UTM says G is true, then “UTM will never say G is true” is false. If “UTM will never say G is true” is false, then G is false (since G = “UTM will never say G is true”). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
6. We have established that UTM will never say G is true. So “UTM will never say G is true” is in fact a true statement. So G is true (since G = “UTM will never say G is true”).
7. “I know a truth that UTM can never utter,” Gödel says. “I know that G is true. UTM is not truly universal.”
As Rucker says, think about that a bit. It grows on you. Rucker goes on to explain,
With his great mathematical and logical genius, Gödel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics …
Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth … But, paradoxically, to understand Gödel’s proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Gödel’s name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.
The castle to which he refers is Reason itself.
Or, as The Hoft put it:
Gödel showed that provability is a weaker notion than truth, no matter what axiom system is involved.
(for more on the limitations of reason, and the false promise of what Hofstadter called “super-rationality”, see Super-Rational blog.)
Well I read Hofstadter’s GEB not long after it came out.
I know I am as rusty as all hell on this subject.
At the time I can remember thinking something like:
Godel is a very deep abstraction. It is never going to be encountered in real life. Serious philosophers will love it and debate it for ever because it implies some sort of ultimate limit to our ability to construct intellectual systems like theories and theorems.
I didn’t think it would have any impact on physics as such, because, if one particular theoretical model breaks down at some point, because it encounters an unprovable proposition, there is nothing stopping you from developing an alternative theoretical model – that could cover that point well – though that new theory would then have some other weakness elsewhere.
With luck two theories could cover everything. As long as their unprovable parts didn’t overlap.
If we’re really lucky or really clever, maybe we can design a single theory, where the unprovable propositions are all somewhere harmless in explanation space – preferably somewhere where the system you are modelling never goes, or hardly ever goes.
It’s a bit like, when Intel designs a processor, with an obscure bug in the microcode. As long as the circumstances that evoke the bug never occur in real-life applications – in that combination – then no-one will ever encounter the bug and there is no problem. That’s what the ideal theory would be like.
I am still waiting for the first scientific theory to fail because it encountered a Godel-unprovable proposition. I am not expecting we’ll be encountering them very often – maybe once every trillion years or so.
(I will now cease honoring the umlaut.)
Godel is a very deep abstraction. It is never going to be encountered in real life.
Godel’s theorem is invoked in computer science: see Turing’s “halting problem”. Here are class notes from a CS course at Stanford explaining it and the connection to the Big G (PDF link).
As far as physics, no less an august personage than Stephen Hawking has pointed directly to Godel and argued,
and points at M-Theory’s refusal to be pinned down by empiricism as exhibit A.
Suffice it to say that string theorists are quite taken with Godel – the G shows up all over the place in the hardcore literature (behold, just one of many examples from Nuclear Physics B. Over your head and mine.)
I think you are still not understanding the scope of Godel, Dan. You simultaneously declare it to be all-powerful and sweep it under the rug as tangential.
No I sweep it under the rug as tangential to progress in physics. It doesn’t stop us from understanding the world.
Look, let’s say you have theory X and theory X explains 30% of the phenomena in the physical world.
And with Godel’s theorem that drops to 29.9%
I can understand that Godel is a problem for people who are trying to develop a ToE. Maybe that will not be possible. But to suggest that reason has failed just because we can’t find a ToE is total hype.
There is no reason why physics can’t continue with multiple theories for ever. Or one major theory, with patches and workarounds, whenever we run into problems. Isn’t that how we do things now? Physicists invent new theories and subtheories on the fly all the time.
It is a far bigger problem for mathematics or philosophy than it is for day-to-day physics.
I can understand that Godel is a problem for people who are trying to develop a ToE. Maybe that will not be possible. But to suggest that reason has failed just because we can’t find a ToE is total hype.
Dan, I wouldnt be a scientist if I wasnt convinced that reason is something important, useful, and geneuinely of merit in and of itself as an abstract. I don think you can point to anything i have written that says I believe reason ot be “total hype” or that we can know nothing about anything. I am saying we cant know everything about everything, which is the opposite of a ToE. I don’t believe a ToE can exist.
Now, if you say you are a rationalist, and you then qualify that to say you believe reason can account for %50 of all Truth, then I hate to break it to you but you are no rationalist at all. (I gave you a 20.1% upgrade).
The rationalist says that reason is sufficient. It is the rationlaist, and only the rationlaist, who will fight tenaciously against the idea that Godel has application beyond rarefied mathematics. Frankly I dont know where you stand because on one hand you refuse to even acknowledge the evidence that Godel has direct application (the proof itself makes no distinction between math and physics, and I gave you plenty of links in the previous comment as supplementals). And yet on the other you are content for reason to describe 30% of the universe.
I did not say that reason can only understand 30%. I said that reason can understand 30% with theory A another 20% with a theory B that covers a different aspect of the natural world, another 25% with theory C
This is the world as we see it today. I am not sure it is an achievable goal (after Godel) to believe in one explanation for everthing.
But if your physics is empirically driven – to conduct experiments and observations – to explore the world and to keep coming up with better and better understandings, as our knowledge grows, then I don’t see Godel as a problem.
Physics can live with a Godel-incomplete world. After all we’ve been doing it all along – we just didn’t know until the theorem was proved.
BTW I just had a hoot of a thought.
If one explanation for everything is impossible.
Then God does not exist.
Godel’s theorem disproves God.
After all God is the ultimate TOE!!!
You are going to have to become a polytheist.
A Godel universe is a type of time-loop cosmology which Godel described in his final days, while he was hanging out with Einstein. Its continuing appearance in the physics literature does not indicate any connection to Godel’s theorems in logic.
I’m an atheist. I’m also a profound skeptic of “theories of everything”. But my reason for that has nothing to do with Godel. I’m not a physicist; my field is computer science and system theory.
And I think the consequences of chaos theory are enough to demonstrate that a “theory of everything” won’t happen. By which I mean a theory that makes it possible to predict everything. We may come up with retroactive explanations for everything that’s happened up to now, but that won’t help us with the future.
A lot of the future will be predictable. A lot is predictable now. But the chaos fog prevents us from making anything more than very general predictions a long way out. The further we try to see, the worse the detail and the more error. That is the nature of cumulative error in an iterative simulation of a system: the error expands exponentially as the number of generations increases, and eventually it swamps the signal, leading to a model which is no better than chance of being correct.
In any case, the fundamental principle of scientific epistemology is that burden of proof is on those who make substantial claims. Until such time as someone genuinely proposes a “theory of everything”, and it survives initial scrutiny, I’m not inclined to spend much time worrying about it.
Daniel, what you’re saying is, “Well, it might happen.” Yeah, it might. And maybe someday UFOs will land. And maybe there really is a Bigfoot out there. But until I see more evidence, I’m not particularly interested in spending much effort worrying about it.
Speaking of chaos, there are some cosmologies where the universe begins out of some random fluctuation event, and the laws of physics are “frozen in”, in some random configuration. as the universe expands and cools through all the levels of symmetry breaking.
In such a cosmology, I would say there is no overwhelming reason to believe that the laws of nature should cohere into one super law of laws. There may well be multiple disjoint laws.
I’m surprised to see chaos brought up as an objection to a “theory of everything”. You already have chaos in celestial mechanics, based on nothing more than Newton’s law of gravitation. It did not make the law undiscoverable or wrong or unusable.
I am certainly with Dan in objecting to this interpretation of Godel\’s theorem as somehow constituting a critique of rationality itself. But I think he has obscured matters by talking about undecidability in physics.
Consider some factual claim which you are simply not in a position to decide, e.g. that Julius Caesar had raisinbread for breakfast on the last day of his life. You weren\’t there; no one who was, wrote about it; Romans did eat raisins, so it cannot be dismissed as absurd. Here we have a true-or-false proposition which reason cannot decide for us.
Does this \”limitation\” mean that rationality is \”flawed\”? And if it doesn\’t – what\’s different about the Godelian situation? Once again, we find that certain propositions (the Godel sentences) are undecidable – out of reach of a particular epistemic method.
It would make far more sense to say that Godel\’s theorem falsifies a particular theory of what rationality is – namely, the theory that rationality consists in following some mechanized decision procedure – the argument being that \”we\” can decide the truth of the Godel sentences, when the mechanized decision procedure can not. There are further counterarguments, so it\’s far from the end of the discussion. But I think it is at least more of a discussion.
The theory about the raisin bread fails for lack of evidence.
Given the right evidence (say, fossilized raisinbread crusts with Julius’s teeth marks in it, wrapped in a letter from Brutus dated to the previous day, and a note scribble on the back saying, “To Morning House Slave. I will eat the rest of this when I get back home from the senate”)… and there would be no problem proving it.
With Godel the theories that you have every reason to believe would work, and model the right behaviour, don’t.
Something else has just occured to me.
You know that in Newtonian Gravity theory, “The Three Body Problem” has no analytical solution. You are forced to use approximation schemes to generate solvable subtheories.
I wonder if this is already a manifestation of Godel’s theorem in classical physics?
Because this is exactly what I would expect Godel to look like. Something that should work (you would think, naiively)… But it just doesn’t work – and you can prove it.
I may have to withdraw that jibe, about Godel only affecting us once every trillion years.
Now I’m sure you’re just using doubletalk. The unsolvability of the “three body problem” has nothing to do with Godel completeness.
OK, explain, because I don’t understand why that is so.
Godel predicts that there are propositions that are true but can’t be solved.
The TBP is clearly Newtonian gravity- there’s nothing else involved. But the math is unsolvable.
Where’s the “true” part? What Godel says is that there will be cases where we know the answer but cannot prove that the answer is correct.
But in the Three Body Problem, we don’t actually know the answer, and have no way of figuring it out.
The true part is the truth of the axioms. Newton’s gravity and the laws of motion.
We have no reason to believe they don’t work at this scale and speed.
In fact, the fact that you can find approximation schemes that are able to solve the physical problem to arbitrary accuracy, numerically on a computer say, proves that the underlying laws of physics are OK.
Now it is the laws of physics that are the axioms that are used to create the dynamic equation of the Three Body Problem. It’s just that the equations have no analytical solution, at least not internally from within the theory.
You have to jump out of the system and use an approximation scheme to get around this absolutely intractible roadblock.
If anyone knows why this is wrong please forgive. Like I said I am very rusty with this stuff.
The three body problem isnt a Godelian statement of unknown truth because we understand the laws which govern it completely. however, an analytic solution is not possible, but that doesnt mean the underlying theorems that govern it are false. fundamentally the three body problem is just F = G*Mi*Mj/(Rij)^2 but its the problem of applying it to all pairs i,j that is where we get tripped up.
A godelian example might be that we observe the orbit of a planet and find that taking everything into account the planet should be at position X,Y,Z but instead appears to be offset by dX,dY,dZ. That actually happened, but then we used relativity to reduce the delta to zero. ut suppose we do a more fine grained measurement and find again some offset that cannot be explained. All godel says is that there is no guarantee that we will find another theory to fill in the gap and again reduce the deltas to zero. Personally i would be predisposed to believe that a theory does exist simply because things are always easier at the macroscopic level. Its when you drill down to microscopic scale and below that theres more potential for running into fundamental limits. This is why string/M theory may be closer to some godelian truth than mere celestial mechanics. The latter are really just the integral of the former, in a sens e- an aggregate behavior, like a mob.
Aziz, I don’t agree with your example. An example of a Godelian statement would be a result we arrived at using a Monte Carlo simulation, but which we can’t explain formulaically.
There are a lot of problems like that in fluid dynamics. We can run simulations, with controlled random components. We can rerun them hundreds of times and statistically examine the results and determine what reality probably will look like. (Assuming the simulation isn’t flawed, a really big assumption.) But we cannot derive formulas which will directly predict the result. So we know what the answer is, and we know that the answer is right, but we can’t prove it within the system.
I agree with Steven, Otaku,
It is not “a Godelian statement of unknown truth”
It is a statement of known truth that can’t be proved.
Steven/Dan
we have to be careful not to confuse “statements of truth” with “computation”. Godel addresses the provability of statements. Statements are things like “There are infinitely many primes” or “even numbers are the sum of two primes”. These may or may not be true. The provability of these statements, according to Godel, is the thing we cannot take for granted. (Euclid proved the first above. The second is Goldbach’s conjecture, for which I am not sure if a proof has yet been found.)
A computation on the other hand is a process whereby inputs are fed into a function, and the result are outputs. The function must be finite, can not be magical, and can only perform basic operations. The definition of these operations relies heavily on the “space” in which the function operates – in the example of Monte Carlo simulations, which incidentally is just a fancy term for “randomize the inputs”, the basic operations are simple arithmetic. I have used Monte Carlo extensively in my own research and training and its nothing magical.
However! not every function is necessarily computable. In fact that statement is called Turing’s undecidability Theorem. It is tempting here to simply say “Godel = Turing!” and that functions equal statements but these concepts are not homomorphic, let alone isomorphic.
Now, you could define the n-body problem as a series of statements (including Theorem Duck: Planet X is at Position Rho at Time Tau). Let us call this collection of statements the N Body Problem System. If you do this, then yes, the solution to the N body problem will be outside that set of statements describing it. And yes that is due to godel – but that is because we have defined a very specialized subset of the Universe, focused soely on the N body problem. So of course Theorem Duck’s provability *within the N Body problem System* is not guaranteed. However that doesnt have any bearing on whether the N Body problem itself, in general, is godelian in hte much larger system called the Universe, which contains the N Body problem as a subset, and which Theorem Duck might well be contained within, and thus provable. Or maybe not.
The reason we can solve the N Body problem in the real universe using Monte Carlo is because classical mechanics can be described using Turing Machines, such as the MATLAB programming language. Or slide rules. Both qualify. Practically every single physical theory meets the conditions for computation (the “Church-Turing Thesis”) and so we can do numerical simulations to model them (though our simulations are never as perfect as the Real Thing, because to do a perfect simulation, we would need a simuation of the same complexity as the actual system, namely a pocket Universe like you might find in Zarniwoop’s office. So we can’t really “solve” the N Body problem anyway, but we can get as arbitrarily close to figuring out what we need to know for pragmatism’s sake.
I am so not a theoretical physicist, so everything i said above might as well be Godelian. It certainly may be true.
“However that doesnt have any bearing on whether the N Body problem itself, in general, is godelian in hte much larger system called the Universe, which contains the N Body problem as a subset, and which Theorem Duck might well be contained within, and thus provable. ”
To me as an empiricist, this is mysticism. We know nothing about “the Universe”, except what we know from observation, and the theories that we construct and have worked so far.
What that wider reality consists of, we gradually discover by exploration. That is not a Godelian problem it is a Bayesian one. Godel is only telling us that no one theory we invent will be able to solve every problem. It can be the simplest little theory (almost) or subtheory, or the most complex.
Unless a theory is so simple that it is Godel-complete, then somewhere within the theory there are true statements that cannot be proved from within the theory. i.e. We will never reach the point when we don’t need new theories – unless we find a ToE which is so simple that it is indeed G-complete, and from that (finally) we will be able to find (hack) emergent theories that can explain everything.
I can’t emphasise this strongly enough: Physics is a creation myth. A very good creation myth – one that agrees with all the known evidence. Some of us find it a very exciting creation myth. But it is first and foremost a narrative we are building as we go. And we, as storytelling humans know nothing, except what we observe, and the myths (models) we construct to explain what we see.
Two excellent links I just came across that shed some more light on the connection between Turing and Godel. First is a paper: “Gödel’s Theorem and Information” – International Journal of Theoretical Physics 21 (1982), pp. 941-954, Gregory J. Chaitin. Yes, THAT Gregory Chaitin. The abstract:
He proves Godel’s Theorem using Turing’s Halting Problem.
The other is a powerpoint presentation by Avi Widgerson at the Institute for Advanced Study in Princeton, titled “Proof, Randomness, Computation, Games” that provides a nice high level overview.