3 ms·

I still don't think we have grasped the importance of Gödel's incompleteness theorem. For example, indirectly it means that we can't ever solve the halting prob

by amix 18y ago

I still don't think we have grasped the importance of Gödel's incompleteness theorem. For example, indirectly it means that we can't ever solve the halting problem. Personally, I also think it applies to physics, especially the idea to find a theory of everything. I think theory of everything won't be possible simply because the incompleteness theorem states that "given any system of axioms that produces no paradoxes, there exist statements about X which are true, but which cannot be proved using the given axioms." (where X can be numbers, computer programs or ...)

wingo 18y ago
My instincts agree with you, but the rational part of my mind can't distinguish statements that are affected by Gödel's theorem from those that are not.
deleted 18y ago
[deleted]
antiform 18y ago
This is exactly the kind of thinking that the article argues against. Remember that Goedel is speaking within the context of formal systems, so there is relatively little impact to any area outside of the small field of philosophy of mathematics. Anybody who tries to extrapolate beyond those bounds is either mistaken or misled as to what Goedel's incompleteness theorems actually imply. There is a much more thorough and eloquent explanation in the following link. [http://www.ams.org/notices/200604/fea-franzen.pdf http://www.ams.org/notices/200604/fea-franzen.pdf] Hell, even Einstein, who was close friends with Goedel and familiar with the result, was searching for a more fundamental physical theory than quantum mechanics, so clearly he did not believe it was a lost cause.
- jmatt 18y ago
  There is a much more thorough and eloquent explanation in the following link. [http://www.ams.org/notices/200604/fea-franzen.pdf http://www.ams.org/notices/200604/fea-franzen.pdf] Thanks for the link.
- yters 18y ago
  Do you know of anyone who has rigorously determined how Goedel's theorems apply to anything outside of mathematics? While his theorems show the shortcomings of a certain approach to math, I don't think math is the only area where this approach is applied. For instance, granting Goedel has shown math is Platonic, i.e. it is about independently existing entities, not formal structures, then why does it make sense to say the mind that can grasp math is itself a formal system, i.e. the assumption behind strong AI? So, it is more accurate to say Goedel's work is restricted to domains where formalization (of the correct sort) is applied, which covers more ground than just the philosophy of mathematics.
  - antiform 18y ago
    What you say in your last statement is true and helps to clarify a subtle point. I tend to shove all of that stuff (logic, set theory, problems of undecidability, etc) into the nondescript box labeled "philosophy of mathematics." When I meant a field was "small," it was not meant to be pejorative. Philosophy of mathematics is a rich and productive field with many applications within its varied fields. The main problems I see are the ones described the article I linked, in that people attempt to apply the theorems to things like physics, politics, law, or postmodern philosophy. Of course Goedel's theorems do not totally exist in a bubble that only contains arcane mathematical incantations. For instance, Goedel's theorems imply (like the halting problem) that you cannot create a compiler that would be able to determine whether a program will not terminate and reject it, by considering what happens when you feed it a Goedel statement. However, this problem is something that I would also classify under "philosophy of mathematics." Also, I hope I did not provide any implication that my view (or any view, for that matter), is the final word on the subject. I'm not dead-set in my own beliefs on incompleteness and if you can provide a convincing argument of a rigorous, nonmathematical application of Goedels theorems, I'd be more than happy to change my mind. There is considerable discussion as to what exactly the incompleteness theorems imply, and there are many eminent minds on the many different sides of the argument. For instance, I believe Stephen Hawking is somebody who believes that physics cannot ultimately be formulated into a final number of finite principles. Do I believe this to be a rigorous application of Goedel's incompleteness theorems? No. Do I believe that this can be applied to fields outside a relatively restricted problem space? No. Does this mean I'm right? Of course not. As to your point about Strong AI, I don't want to open that can of worms in this thread. I'm not yet convinced that the human mind is equivalent to any finite state machine, so I'm afraid that we don't even agree upon its the basic premises. However, I would love to discuss it any time outside of the thread.
- amix 18y ago
  Finding better models and understanding things at a deeper level is never a lost cause and even if we know that we can't find a complete set of axioms for all existing math theories, we still try to understand math better. For example, the string theory people are trying to find an answer for everything (and it seems to be much more complex than 42 :-p). In this context, David Hilber tried to do the same for math (namely find a set of axioms for all existing theories) and Gödel proved that this was a lost cause. Does Gödel's incompleteness theorem apply to physics as well? I can't really grasp it, but my intuition says it does - because why would the formal system of TEO have more simple properties than the formal systems for arithmetic or Turing machines...?
miloshh 18y ago
I think physics would be very happy to come up with a theory of "almost everything", like set theory is for mathematics. That would be a huge step forward, and would be completely unaffected by Godel's theorem. Also, the halting problem's insolvability is straightforward to see without knowing any of Godel's work. :)
alan-crowe 18y ago
It is easy to exhibit an uncomputable function, the busy beaver function is the standard, easy example. It is immediately obvious that a solution to the halting problem make the busy beaver problem computable: just stick to running the programs that halt and pick the largest output. The unsolvability of the halting problem is way easier than Godel.
yters 18y ago
Chaitin agrees with you: http://www-2.dc.uba.ar/profesores/becher/ns.html http://www-2.dc.uba.ar/profesores/becher/ns.html Note, the article is for the lay reader, but the gist is a correct representation of Chaitin's views. For more rigor, see: http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant Chaitin wrote a freely available book about his views: http://plus.maths.org/issue37/features/omega/feat.pdf http://plus.maths.org/issue37/features/omega/feat.pdf A bit more discussion here: http://news.ycombinator.com/item?id=378658 http://news.ycombinator.com/item?id=378658
schtog 18y ago
Does it really mean that a theory can't be found or just like with "everything else", we can only be 99.99999999% sure and never reach 100%? Does it necessarily mean that the imcompleteness theorem extends to all systems? The article linked somewhere else in this thread: http://www.ams.org/notices/200604/fea-franzen.pdf http://www.ams.org/notices/200604/fea-franzen.pdf seems to say that it doesn't extend to other "systems".

by amix 18y ago

wingo 18y ago

My instincts agree with you, but the rational part of my mind can't distinguish statements that are affected by Gödel's theorem from those that are not.

deleted 18y ago

[deleted]

antiform 18y ago

This is exactly the kind of thinking that the article argues against. Remember that Goedel is speaking within the context of formal systems, so there is relatively little impact to any area outside of the small field of philosophy of mathematics. Anybody who tries to extrapolate beyond those bounds is either mistaken or misled as to what Goedel's incompleteness theorems actually imply. There is a much more thorough and eloquent explanation in the following link. [http://www.ams.org/notices/200604/fea-franzen.pdf http://www.ams.org/notices/200604/fea-franzen.pdf] Hell, even Einstein, who was close friends with Goedel and familiar with the result, was searching for a more fundamental physical theory than quantum mechanics, so clearly he did not believe it was a lost cause.

jmatt 18y ago
There is a much more thorough and eloquent explanation in the following link. [http://www.ams.org/notices/200604/fea-franzen.pdf http://www.ams.org/notices/200604/fea-franzen.pdf] Thanks for the link.
yters 18y ago
Do you know of anyone who has rigorously determined how Goedel's theorems apply to anything outside of mathematics? While his theorems show the shortcomings of a certain approach to math, I don't think math is the only area where this approach is applied. For instance, granting Goedel has shown math is Platonic, i.e. it is about independently existing entities, not formal structures, then why does it make sense to say the mind that can grasp math is itself a formal system, i.e. the assumption behind strong AI? So, it is more accurate to say Goedel's work is restricted to domains where formalization (of the correct sort) is applied, which covers more ground than just the philosophy of mathematics.
- antiform 18y ago
  What you say in your last statement is true and helps to clarify a subtle point. I tend to shove all of that stuff (logic, set theory, problems of undecidability, etc) into the nondescript box labeled "philosophy of mathematics." When I meant a field was "small," it was not meant to be pejorative. Philosophy of mathematics is a rich and productive field with many applications within its varied fields. The main problems I see are the ones described the article I linked, in that people attempt to apply the theorems to things like physics, politics, law, or postmodern philosophy. Of course Goedel's theorems do not totally exist in a bubble that only contains arcane mathematical incantations. For instance, Goedel's theorems imply (like the halting problem) that you cannot create a compiler that would be able to determine whether a program will not terminate and reject it, by considering what happens when you feed it a Goedel statement. However, this problem is something that I would also classify under "philosophy of mathematics." Also, I hope I did not provide any implication that my view (or any view, for that matter), is the final word on the subject. I'm not dead-set in my own beliefs on incompleteness and if you can provide a convincing argument of a rigorous, nonmathematical application of Goedels theorems, I'd be more than happy to change my mind. There is considerable discussion as to what exactly the incompleteness theorems imply, and there are many eminent minds on the many different sides of the argument. For instance, I believe Stephen Hawking is somebody who believes that physics cannot ultimately be formulated into a final number of finite principles. Do I believe this to be a rigorous application of Goedel's incompleteness theorems? No. Do I believe that this can be applied to fields outside a relatively restricted problem space? No. Does this mean I'm right? Of course not. As to your point about Strong AI, I don't want to open that can of worms in this thread. I'm not yet convinced that the human mind is equivalent to any finite state machine, so I'm afraid that we don't even agree upon its the basic premises. However, I would love to discuss it any time outside of the thread.
amix 18y ago
Finding better models and understanding things at a deeper level is never a lost cause and even if we know that we can't find a complete set of axioms for all existing math theories, we still try to understand math better. For example, the string theory people are trying to find an answer for everything (and it seems to be much more complex than 42 :-p). In this context, David Hilber tried to do the same for math (namely find a set of axioms for all existing theories) and Gödel proved that this was a lost cause. Does Gödel's incompleteness theorem apply to physics as well? I can't really grasp it, but my intuition says it does - because why would the formal system of TEO have more simple properties than the formal systems for arithmetic or Turing machines...?

miloshh 18y ago

I think physics would be very happy to come up with a theory of "almost everything", like set theory is for mathematics. That would be a huge step forward, and would be completely unaffected by Godel's theorem. Also, the halting problem's insolvability is straightforward to see without knowing any of Godel's work. :)

alan-crowe 18y ago

It is easy to exhibit an uncomputable function, the busy beaver function is the standard, easy example. It is immediately obvious that a solution to the halting problem make the busy beaver problem computable: just stick to running the programs that halt and pick the largest output. The unsolvability of the halting problem is way easier than Godel.

yters 18y ago

Chaitin agrees with you: http://www-2.dc.uba.ar/profesores/becher/ns.html http://www-2.dc.uba.ar/profesores/becher/ns.html Note, the article is for the lay reader, but the gist is a correct representation of Chaitin's views. For more rigor, see: http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant Chaitin wrote a freely available book about his views: http://plus.maths.org/issue37/features/omega/feat.pdf http://plus.maths.org/issue37/features/omega/feat.pdf A bit more discussion here: http://news.ycombinator.com/item?id=378658 http://news.ycombinator.com/item?id=378658

schtog 18y ago

Does it really mean that a theory can't be found or just like with "everything else", we can only be 99.99999999% sure and never reach 100%? Does it necessarily mean that the imcompleteness theorem extends to all systems? The article linked somewhere else in this thread: http://www.ams.org/notices/200604/fea-franzen.pdf http://www.ams.org/notices/200604/fea-franzen.pdf seems to say that it doesn't extend to other "systems".