Gödel's Incompleteness Theorem explained

http://www.miskatonic.org/godel.html

by simonbrown • 14 years ago

111 58 14 years ago

The BBC had a 45 minute radio panel with Marcus du Sautoy and some other mathematicians going through Godel's theorems: http://www.bbc.co.uk/programmes/b00dshx3 (I believe people outside of the UK can listen to it.. if not, sorry! For some reason the 'listen' image does not appear for me, but is to the left of '(45 minutes)').

(And if you like it, the whole set of math and science episode of In Our Time are similarly excellent.)

lotharbot• 14 years ago

It should be noted that Godel gave two Incompleteness Theorems.

The first says that, in a system based on a list of axioms, there will always be some statements that aren't provable. (Remember Mr. Spock confusing a computer by telling it "I am lying"? "This statement can't be proved" behaves the same way -- it's true, but you can't prove it, because if you did then you couldn't prove it.) In other words, there is always truth the system can't account for.

The second theorem builds on the first. It says a system can't prove itself consistent, and that if a system includes the claim "this system is consistent" then it is necessarily inconsistent. (In essence, you can construct a more complex version of the "I am lying" statement in any system that includes a claim of "I am telling the truth".) In other words, the only way to prove something consistent is from outside of it.

dmfdmf• 14 years ago

> "This statement can't be proved"

This statement (and Godel's mathematical equivalent) does not assert anything to be proved, it is contentless, which is why logical, axiomatic systems choke on it, essentially due to recursion or self-reference. Logically there are only two fundamental ways to err; by contradiction and by circular reasoning.

> In other words, the only way to prove something consistent is from outside of it.

This is what I take from Godel's theorems but this is a poor formulation of the idea. A better way to say it is that proof presupposes consistency and more specifically the law of identity which is a metaphysical law that has to be validated not proved (since proof depends on it).

gburt• 14 years ago

A "strange loop", perhaps.

vgm• 14 years ago

Interestingly, Godel gave a presentation somewhere within 5 - 7th September at Koningsberg presenting the first incompleteness theorem. At this time, he did not have the second. [1]

Von Neumann was in attendance and he wrote a letter to Godel on November 20th announcing his discovery of the second incompleteness theorem. As it turns out, Godel had just sent a paper for publication on November 17th with the proof of the second incompleteness theorem. In reply to Godel, finding out he had just been scooped, von Neumann wrote:

"As you have established the theorem on the unprovability of consistency as a natural continuation and deepening of your earlier results, I clearly won't publish on this subject." [2]

[1] http://goo.gl/uJH9Q [2] http://goo.gl/AXfQV

(Links are very long, hence the shortner. They take you to Google Books.)

mappu• 14 years ago

By using a UTM as a metaphor for the axioms themselves, the UTM must run itself, essentially describing an infinite loop over the finite program, which is another point to consider; with any axiomatic system, is it possible to describe a UTM which you can guarantee halts in finite time? Probably not necessarily.

It seems to be a solid notion that if a paradox can be constructed, then the space is unverifiable, but in this case it feels like the paradox results only from a poorly specified question (the correct answer exists, and is an acknowledgement that the input is meaningless).

The important part to take away is that Gödel himself exists in a logical space where he is able to understand and deal with the absurdity of his paradox, which is outside the scope of the UTM. Every logical system containing a paradox, is a subset of a logical system wherein the absurdity of the paradox is understood. So, perhaps a logical system which explicitly recognises paradoxes as absurd, can be complete. Like NaN in IEEE754, or int|null in dynamic languages.

The result clearly only applies to logical spaces where the paradox is translatable, so i'd be interested to see if a version exists for only basic arithmetic.

A similarly interesting related discussion is the total, abject, and infinite unavailability of a "quadratic formula" for polynomials in x^5 or greater.

kmm3• 14 years ago

> the UTM must run itself, essentially describing an infinite loop over the finite program,

Exactly. I came up with this counterargument not so long ago. It's why neither Gödel's theorems nor the Halting problem ever really impressed me. I don't doubt their validity but the conclusion that no system can be complete is only true for very stringent definitions of "complete". I still believe the Halting problem can be solved in some sense of the word solve. But perhaps I'm being too pragmatic.

> So, perhaps a logical system which explicitly recognises paradoxes as absurd, can be complete.

Gödel explicitly counters this with his second incompleteness theorem which says that no consistent system can provide a proof of its own consistency. In other (but equivalent) words, I might be confident that my mind works correctly but there's technically no way to be completely sure. In fact if I were sure of it, my mind wouldn't be working fine.

keeperofdakeys• 14 years ago

> I still believe the Halting problem can be solved in some sense of the word solve. But perhaps I'm being too pragmatic.

While its true there are some forms of functions that can be found to either halt or not, some can't. For example, ask the user for a boolean, and do a while loop based on this value. You can't say whether this will halt or not, but it does contain unspecified variables.

Then consider the Collatz Conjecture. We can't prove any other number then 1 actually reaches 1 without simulating the process. Since we don't even know if the next step will reach the destination, we can't make any decision about when it will halt. If we can't even decide it for such a simple function, then I don't think we can 'solve' it, even for a general 'solve'.

buu700• 14 years ago

Relevant: http://www.reddit.com/r/explainlikeimfive/comments/j8yq3/can...

icandoitbetter2• 14 years ago

Its relevance in philosophy/epistemology/science/computing has been inflated out of proportion by the confused arguments of Hofstadter, Penrose, etc. Just because it's difficult to understand doesn't mean that it will tell you the meaning of life. Of course it's a mathematical theorem of profound importance, but it has absolutely nothing to do with the limits of rational thought.

brudgers• 14 years ago

Well...I think about Godel's theorem as the mathematical implementation of Kant's ideas about the limits of reason based upon human experience, i.e. there are some truths which are inaccessible because time and space are preconditions of all human experience.

Not to dwell on arguments about whether or not time and space actually exist independently of human experience, what Kant was getting at is that the way in which humans experience the world limits our ability to draw conclusions to a particular subset of all truths.

If Godel's theorem is true, then from a Kantian perspective, mathematics no longer enjoys a uniquely privileged place in regards to human rationality. That's pretty important philosophically - at least to some people.

Positivists may take a different view.

icandoitbetter2• 14 years ago

Godel doesn't talk about space, time, human experience, truths that exist independently of human experience. I fail to see how he's relevant.

rcthompson8• 14 years ago

I've just spent about an hour trying to explain how the comparision between Godel's incompleteness theorem and the ideas of Kant is flawed, but I couldn't come up with anything, because they have nothing to do with each other. It's like trying to explain how the number 2 is different from a rhinoceros; there's no explanation that would satisfy anyone who already believes that the number 2 and a rhino are comparable.

helpmep532• 14 years ago

I haven't read Hostadter or the other's arguments, but this comment got me thinking. If the incompleteness theorem is about the limitations of an axiomatic system, why wouldn't it apply to rational thought. If (and it's by no mean certain) rational thought and the human brain have certain rules built into it to process, interpret, and act on information from the outside world, then couldn't these hardwired rules be considered axioms? These axioms are clearly powerful enough to express the integers and so one would conclude that there are certain propositions that are true but cannot be proven by the human brain. Of course, the brain and it's wiring is still a matter of research, and the fact that the brain is a dynamic system with neural connections in constant flux means that the system is not static nor are these "axioms".

I don't know, I'm just thinking out loud....

duaneb• 14 years ago

Penrose's The Emperor's New Mind addresses this idea. Basically, Penrose assumes that:

1. Gödel's Incompleteness Theorems are equivalent to the halting problem (provable)

2. If the human mind is deterministic, it can be modeled with a deterministic algorithm (provable).

3. The human mind seems to be capable of proving arbitrary things about all algorithms (debatable; I'm extremely skeptical).

4. Therefore, the human mind is not bound by the halting theorem, and therefore the human mind is not deterministic.

He then draws several possible speculations. 1, the human mind is driven by quantum mechanics. He explains this more in Shadow of the Mind, the "sequel" to this book, and goes on to postulate specifically that "microtubules" allow quantum mechanics to have far-reaching effects that are indistinguishable from consciousness. Other people, most notably and substantially Max Tegmark, disagree[1], arguing, "we ﬁnd that the decoherence timescales (∼10^−13 to 10^−20 seconds) are typically much shorter than the relevant dynamical timescales (∼10^−3 to 10^−1 seconds), both for regular neuron ﬁring and for kink-like polarization excitations in microtubules. This conclusion disagrees with suggestions by Penrose and others that the brain acts as a quantum computer, and that quantum coherence is related to consciousness in a fundamental way." Since then, quantum effects, especially quantum teleportation, appear to be crucial at the molecular level in processes like photosynthesis[2], suggesting that, perhaps, quantum mechanics may play a role.

However, even if quantum mechanics do play a role in human consciousness, I don't see how trading a deterministic brain for a random one is an improvement. Personally, I don't think that quantum mechanics do provide a crucial level to the extent that our brains are somehow not bound by logical axioms; I still believe there's a fundamental "algorithm" that drives the biological brain, though it may be difficult to conceive of, and I tend to agree with Tegmark in ideas of consciousness. Still, I'm open to any evidence on either side of the table, but I think we're a few decades away from key discoveries about the way our brains work that will shed any serious light on the subject.

-------------------------------------------------------------

[1] http://arxiv.org/abs/quant-ph/9907009

[2] http://www.nature.com/nature/journal/v446/n7137/abs/nature05...

Extra reading: see [wikipedia](http://en.wikipedia.org/wiki/Orch-OR)

Dn_Ab3• 14 years ago

I agree with your sentiment. Gödel's work applies only to formal axiomatic systems of a specific strength. There are formal systems that are so weak they can prove their own truth and every statement is decidable (every true statement can be proved as true). And if your theory makes no claim to an axiomatic basis then Gödel really does not have jurisdiction.

But if a person accepts the Church Turing Thesis, then the human brain is not doing any computation that can't be modeled by a Turing Machine. In fact, the brain is at least a Turing Machine. Gödel's limitations will apply to it.

If we accept the Church Turing Thesis and replace the brain with a Turing machine, I argue that the mind is a program that runs on that Turing machine. The program embodies a particular formal system sufficient to encode mathematical statements and leverage itself to prove statements. From this argument one can infer that there are some mathematical truths that some minds will not find. And that if each human mind represents a different formal system, it is in their best interest to work together.

Disclaimer - The above is me thinking out loud not something from a peer reviewed paper

rcthompson8• 14 years ago

It's a fallacy to think of a human brain as a distinct entity. If you are viewing the human brain as "just" a bunch of matter interacting in interesting ways to produce what we call consciousness (as opposed to viewing consciousness as something separate from the physical processes of the brain), then there is nothing really distinguishing your brain from the rest of you, and indeed from the rest of the universe. (Practically speaking, a good bit of decision-making happens in neurons outside of your brain.) So if you want to argue that the mind is equivalent to (or can be simulated by) a Turing machine, then you really want to argue that the whole universe could be simulated on a Turing machine.

Which is not necessarily a bad position to take. http://xkcd.com/505/

michael_dorfman• 14 years ago

> But if a person accepts the Church Turing Thesis, then the human brain is not doing any computation that can't be modeled by a Turing Machine. In fact, the brain is at least a Turing Machine. Gödel's limitations will apply to it.

That's not the case. If one accepts the Church Turing Thesis, then those functions the brain performs on effectively calculable functions can be performed on a Turing Machine. The brain is at least a Turing Machine, but may be greatly more than one, and Gödel's limitations will only apply to that portion doing calculations. The brain may very well be doing a great deal more than simple computation.

Thus, when you write I argue that the mind is a program that runs on that Turing machine, you're leaping off into wild speculation.

Confusion• 14 years ago

The false conclusions philosophers, computer scientists and many others draw due to misunderstanding, or misapplying, the Church-Turing thesis are every bit as problematic as those false conclusions that result from misunderstanding or misapplying the incompleteness theorems. See http://plato.stanford.edu/entries/church-turing/

In both cases the problem is insufficiently respecting the rigorous boundaries on what the theorems actually say and apply to. Neither theorem has anything to say about consciousness and the human mind, unless a lot of currently unproven preconditions, some of which seem unlikely, get proven first.

yequalsx2• 14 years ago

But computers can only work with recursively ennumerable axiom systems. Humans do not have this limitation. The Incompleteness result shows that the natural numbers as defined by the second order Peano Axioms is different than the natural numbers defined by any first order system. Doesn't this have to with thought and rationality?

xyzzyz4• 14 years ago

>But computers can only work with recursively ennumerable axiom systems. Humans do not have this limitation.

I don't think this is true, at least not in the way you put it. I for one surely cannot work with the True Arithmetic system, because I cannot distinguish axioms from non-axioms. Maybe you could expand it a bit?

derrida2• 14 years ago

"It has absolutely nothing to do with the limits of rational thought."

One implication of GIT is that there are true sentences that cannot be proved.

I'm sorry, but I can't manage to see how "It has absolutely nothing to do with the limits of rational thought."

It saddens me that I am the first one that had to point this out on this comment that is over 15 hours old. On HN. :-(

ropz• 14 years ago

The referenced page doesn't deliver on the hype of the HN headline, it merely offers:

"... some selections that will help you start to understand it."""

flurie• 14 years ago

The greatest explanation I've ever seen for the Incompleteness Theorems comes from Palle Yourgrau in his book A World Without Time. He gives an excellent introduction to his explanation: "To appreciate Godel's theorem is your birthright; let no one, including the mathematical police, deprive you of what you have a right to enjoy."

derleth• 14 years ago

Who in the world are the 'mathematical police'?

keithpeter• 14 years ago

A rhetorical and shadowy group who discourage ordinary people from reading about or becoming interested in mathematics. A lot of popular science authors invoke this underground organisation, so it must exist.

rcthompson8• 14 years ago

Think of it kind of like the Sieve of Eratosthenes, but for provability instead of primeness. You start with one axiom and prove everything you can based on that. Then you pick one of the statements you couldn't prove and add it as a second axiom (thereby expanding your axiomatic system), then prove everything that you can with those two axioms. The pick another unproven statement as your third axiom and repeat. Godel's incompleteness theorem is equivalent to saying that you will never run out of axioms, and that you will be able to continue this process indefinitely (just like there are an infinite number of primes).

It's not an exact comparison, but it gives you the idea.

bjornsing3• 14 years ago

An interesting comparison. Just one important difference though if I understand correctly: In Gödel's world you will sooner or later ruin your axiomatic system by adding an axiom that is inconsistent with one or several of your earlier axioms. There's no way to know (from within the system) when that happens, except perhaps that it gets a whole lot easier to prove weird stuff. :)

rcthompson8• 14 years ago

I guess I should have said that you pick as your new axiom a statement that you couldn't prove and also couldn't disprove. Though I'm not sure if even that is the same as logical independence, which is what you really want.

xyzzyz4• 14 years ago

I think your comparison misses an important point. If you pick in every step a sentence that is non-provable from your current axioms, but not contradictory with them either, after infinitely many steps[1] you will have picked all of them, and get a system called True Arithmetic, in which every true sentence is provable, essentially by definition. The reason why Goedel's incompleteness theorem does not work here is that your set of axioms is not recursively enumerable, and this is a necessary assumption of GIT.

[1] - If "after infinitely many steps" sounds fishy to anyone, please keep in mind that you start with an infinite list of axioms anyway -- first order Peano arithmetic theory has an induction axiom schema Ind that basically says that for every sentence f, Ind(f) (the sentence you get by substituting every occurrence of a single free variable in Ind with f) is an axiom of PA.

rcthompson8• 14 years ago

The "infinitely many steps" does sound fishy to me, because I wonder whether the number of axioms in True Arithmetic is countably infinite or uncountably so, and whether it makes a difference (I think it does).

But yes, the comparison is an analogy, certainly not correct at every level.

cop359• 14 years ago

Seems like a silly paradox. Why is it important?

Also it seems very similar to this famous paradox: (from 600BC btw.) http://en.wikipedia.org/wiki/Epimenides_paradox

rcthompson8• 14 years ago

Constructing the paradox is just the means of proving the theorem. The paradox itself is not particularly important. Also, the paradox in Godel's theorem is "This statement is unprovable" not "This statement is false".

hammock• 14 years ago

Gödel showed that provability is a weaker notion than truth

This, to me, is a great summation and one of the most important conclusions we can draw. When you reflect on it it's easy to see how Godel's theorems reach beyond computer science and into philosophy, ethics and religion.

erichocean• 14 years ago

Not that easy, because it only applies to truths represented in a system of symbols. Very abstract stuff, and in fact, trivial to overcome – use two sets of symbols.

The theorem was important at the time because it ended one pursuit (one single-level system to rule them all), but its actual impact on anything of importance in the wider world of, well, anything, is vastly overrated.

rcthompson8• 14 years ago

I believe you would need to establish some sort of equivalence between arithmetic on the set of natural numbers and philosophy, ethics, and religion in order to apply Godel's incompleteness theorem to any of them, since Godel's theorem applies to sets of axioms used to prove things about the natural numbers.

tumes• 14 years ago

While it might not be the most technically accurate, the ways in which David Foster Wallace touches on Gödel in Everything and More are worth a look for interested parties.

bjornsing3• 14 years ago

I of course have no proof, but I sometimes get a feeling that Gödel does have something to do with the limits of rational thought.

To me it seems humans have found a way to cope with Gödel's incompleteness: we accept that some of our axiomatic systems are inconsistent and adapt by simply discounting the value of proofs.

It's difficult to explain, but let me give an example. Among engineers you can often reason along very long logical chains and have your conclusions accepted. Among (some) business people you can't. They seem to refuse the validity of logic itself, being nervous about trusting logical conclusions. I think that's because they know their axiomatic systems are self-inconsistent. :)

By observing business people I have come to the conclusion that the best you can do in an a self-inconsistent axiomatic system is to look for "nuggets of truth" and never wonder too far from them. You can hear people say stuff like "limiting tweets to 140 characters will brings out creativity - people are less afraid to create when they are constrained" and similar. If you accept that as truth then you can wonder a short short distance from it and reason about business opportunities, but you can't combine that nugget with some other nugget and be sure to come to a correct conclusion.

Perhaps it is so, that the likelihood of "proving" an untrue statement in a self-inconsistent system increases with the number of axioms you are basing your proof on. That's perhaps why many people are very skeptical of "proofs" that seam to involve a lot of axioms? :)

mjw• 14 years ago

Surely a simpler explanation for that is that business people don't usually work with crisp, binary data. Instead they're (implicitly) doing some kind of statistical inference on noisy data.

Propositional logic might be an acceptable approximation to this kind of inference in certain narrow situations, but the approximation breaks down quicker when the chain of inference gets longer.

bjornsing3• 14 years ago

That could certainly be a simpler (and therefore better) explanation. :) When your "axioms" are fuzzy so to speak, and not real axioms, it's of course dangerous to draw conclusions from several of them (because the risk of one of them being false increases exponentially).

But I still have a feeling there's something there... :) For example, I remember reading here on hacker news about this CS professor who had found a way to predict performance in entry level programing courses: http://www.eis.mdx.ac.uk/research/PhDArea/saeed/. Basically, they just tested their students ability to form a self-consistent model of how programming works. If they could they did well in the course. If they couldn't they did poorly, and it was very difficult to help them.

That experiment leads me to believe that about 50% of the population is in the habit of constructing self-inconsistent systems of hypothesis (provisional axioms you could say). :) If that's true I'm not sure yours is a simpler explanation... ;)

batista2• 14 years ago

With regards to the "Rucker, Infinity and the Mind" except that says:

>The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows: (...)

Actually, Godel's theorem is not that simple at all. It involves lots of hard math. And it's not about some hazy "Universal Truth Machine", it's about a specified axiomatic mathematical system with certain specific properties.

The "simple" thing that RI&TM describes is a variation of the Liar's paradox. Which is somewhat like what Godel used, but he did not use it in a simplistic way, not at that level of coarseness, and surely not "embarrassingly simple to relate".

powertower• 14 years ago

> The implication is that all logical system of any complexity are, by definition, incomplete; each of them contains, at any given time, more true statements than it can possibly prove according to its own defining set of rules.

Here is an even simpler explanation:

A description of a thing is not the thing itself, it's just a description that allows you to: interact with that thing and place that thing into a framework.

And an even more accurate description of a thing is still not the thing itself, it's just a more accurate description.

Add more layers, and you still have just a description, and never the thing itself.

It's like an onion, and each layer gets more distant from the core.

Then those layers begin to interact with other descriptions of other things. So more layers are added to explain those interactions.

It goes on and on until you've simulated the universe.

The problem is it's exponential, and even if it was not, you're still just stuck with just a description, and not the thing itself.

Some people will claim otherwise here, so just ask them if a description of a thing is the same as the thing itself and go back to the start of all this.

derrida2• 14 years ago

If I'm not mistaken, one way of seeing GIT is just as a reductio ad absurdum on the idea that truth is just that which is proved.

Perhaps you should consider that talking about ontology clouds the water here, this explanation might have some analogical value, but isn't 'simpler'.

Gödel's Incompleteness Theorem explained

Related Stories