Gödel's Incompleteness Theorem explained
miskatonic.org
miskatonic.org
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.
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).
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.)
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.
I don't know, I'm just thinking out loud....
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 find 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 firing 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)
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
Which is not necessarily a bad position to take. http://xkcd.com/505/
Gödel's Theorem has been used to argue that a computer can never be as smart as
a human being because the extent of its knowledge is limited by a fixed set of
axioms, whereas people can discover unexpected truths
Ever stopped to think that the very "obviousness" of it might just be a product of professional bias as IT persons?
Trivially you can, with perfect information and sufficient technology, modelling neuron by neuron, create an electronic brain. The catch is, you would only prove humanOS runs on silicon as well as it does on carbon.
Having a powerful enough computing device does not imply it can compute anything a different type of computing device can. We have the turing-completeness that indeed says this is valid for a subset of our current programming languages and hardware, but turing-completeness does not trivially apply to our brain.
As an analogy, a ruler is a drawing device, but you can't draw a circle with it as with a compass. You can somewhat simulate drawing a circle by taking it very slowly using a certain clever algorithm, but it will never be perfect or else require infinite or virtually infinite time/space to do so.
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.
If the universe is not calculable on a Turing machine then some physical processes including those going on in the brain are not computations but can only be expressed using superrecursive algorithms. If those processes in the brain were computations then the human brain would be a hypercomputer. I do not believe in the existence of that latter. This opens the possibility that even if the brain operates via non computable means, its behaviour could be fully captured by a Turing Machine. I also think the theory that the universe has non computable things going on and the brain harnesses them in a non algorithmic way is more complex than the theory that the universe is merely Turing equivalent and so is the human brain.
My basis for this belief is the unrelated fact that there are some strict limitations in reality. Finite Speed Limit, 2nd Law, Maximum Force, Maximum Information per square meter, Quantum Indeterminacy; Compuational Indertermincancy of various facets: Diophantine, Church, Godel, Turing, Chaitin. Also the prudent belief that P <> NP and more importantly, lack of any evidence of Nature doing P in NP. Also: No Free Lunch in Search and its counter (okay no free lunch but the universe has structure exploitable by turing machines - see M Hutter). To me, saying the universe is just a turing machine fits this pattern.
Other patterns are the various links which occur in: physics, topology, logic and computation; the unifying power of category theory (e.g colgebras/algebras:objects---analysis as tagged unions---algebra), the link between physical and information entropy, the possibility of a Holographic Principle, the possibility of a discrete theory of quantum gravity, the relationship between a complex probability theory and Quantum Mechanics and the informational nature of QM. To me all these are very suggestive of a simple underlying nature which is informational and that digital physics may not be correct but it is in the right direction.
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.
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?
I would like to know the flaw in my reasoning.
[1] - http://en.wikipedia.org/wiki/Orch-OR#The_Penrose.E2.80.93Luc...
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. :-(
It's not an exact comparison, but it gives you the idea.
[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.
But yes, the comparison is an analogy, certainly not correct at every level.
It does not make any difference, though, since what matters here is, as I said, recursive enumerability of axioms. Anyway, transfinite induction lets one use "pick next element" arguments even on uncountable sets.
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.
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.
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.
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.
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'.
I don't think that's an issue. The Halting Problem ask the question whether a program will halt when supplied with a given input. Nothing is stopping us from providing a separate proof for every single program for every possible that it'll stop.
If you're being pragmatic, rest assured that for any machine/program we can construct in this universe, we can decide the halting problem, as it is bound to be finite state, i.e. it will have a bounded amount of states it can be in and repeat itself. Less technical, there is practically no infinite search space, even if theoretically there is - memory of a physical computer can only count up to a certain number, even if very large.
The halting problem, or undecidability in general is the application of a very basic intuition. If I give you infinite space, and ask you to find me a certain something in that space, there is no way I can be sure whether or not you will succeed. Diophantine equations for example, to solve them requires you to search infinitely through the complex plane, and is analogous to the halting problem.
Now in which sense of the word 'solve' could you possibly believe these can be solved? Yes - our problems and machines are finite, so in that sense maybe.
It's quite similar to Cantor's diagonal argument. Both proofs are completely correct and use a very similar reasoning. The difference is that I'm not interested in almost denumerating the real numbers (I can do that with the rational numbers anyway), but I would be interested in almost solving the Halting Problem.
(And if you like it, the whole set of math and science episode of In Our Time are similarly excellent.)
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? :)
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.
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... ;)
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.
Perhaps you should consider that talking about ontology clouds the water here, this explanation might have some analogical value, but isn't 'simpler'.
Also it seems very similar to this famous paradox: (from 600BC btw.) http://en.wikipedia.org/wiki/Epimenides_paradox
"... some selections that will help you start to understand it."""
>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".