5 ms·

Gödel, Turing and Cantor: The Math

132 points by jamesmiller5 13y ago

stanonyime 13y ago
It would be interesting to speculate the consequence of Godel's Incompleteness deductions on the quest for Grand Unified Field Theorems in theoretical physics
mvp 13y ago
This article took me to another from the same author 'http://skibinsky.com/godel-incompleteness-for-startups/#footnote-4' http://skibinsky.com/godel-incompleteness-for-startups/#foot... and I found the below statement and laughed out aloud. Although in the context, this statement makes sense, in general, I trust books that don't belong to human-related matters (technical etc), because in human-related matters it is mostly one's opinion against others. "As soon as these popular books leave the domain of human-related matters you are totally on your own."
wicknicks 13y ago
Oh wow! This is a great write up on Godel's work. Anybody who even vaguely cares about fundamentals of computer science should definitely give it a read, and if possible a thorough read. Slightly related: Although a more technical/deeper discussion, but the book "Godel's Proof"[1] by Nagel and Newman is a very approachable text in this domain, and explains many aspects of the incompleteness theorems. [1] http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814758371 http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814...
- chriswarbo 13y ago
  I found it quite approachable and thorough, although it throws the the diagonal lemma out there without any real explanation even though it's crucial to the reasoning that follows it. Also I disagree with the completely unfounded assumptions at the end that the (terribly named) Reals have something to do with reality. The Reals are a Mathematical curiosity at best, but more often than not they complicate the understanding of subjects to which they have no relevance, eg. fractions (especially their decimal notation), calculus, physics, computing (especially floating point) and so on. It's fine to treat infinite constructs like the Reals declaratively, eg. as functions which can be composed, but it's meaningless to reason about doing things to their 'final results', since there are no such things by definition. In more precise terms, it makes sense to reason about the output of co-terminating functions (which loop forever, spitting out, for example, a never-ending sequence of digits) but not diverging functions (which loop forever without ever getting as far as their first digit).
  - stiff 13y ago
    The real numbers have no relevance to calculus? Is there a way of doing calculus without real numbers that is simpler? What are you talking about?
- hobs 13y ago
  Honorable mention for http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach which has been mentioned many times on HN. Has many different ways of explaining Godel's genius. Though to be fair you could just read this article and be good.
  - hamiltonkibbe 13y ago
    GEB is awesome. David Foster Wallace's Everything and More: A Compact History of Infinity covers Cantor and is an interesting read about... you guessed it.. Infinity. Re: Turing http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html
  - tekromancr 13y ago
    +1 for GEB. I have been reading it on and off for about 2 years. It's a fun book, but every time I finish a reading session, I am exhausted. I am about 25% through.
    - hobs 13y ago
      Yeah it took me about 7 months to finish it, and you are right, every time I just felt beat and my mind was racing, what a great book.
    - laxatives 13y ago
      IMO just finish chapter 14 and you've basically finished the Godel portion of the book. The rest felt more like Hofstadter's random musings on AI, DNA and some other topics (some of which felt outdated). There's some crazy anecdotes of Ramanujin that I had never heard elsewhere though.
      - pachydermic 13y ago
        Well the structure of the book is supposed to be like a JS Bach song - so in the end, what you get is a combining of all the familiar themes and sometimes it feels a bit repetitive and boring. But if you've read that far, it's worth reading the rest. It's much easier to get through than when you're seeing stuff for the first time and really trying to wrap your head around it.
- deleted 13y ago
  [deleted]
Cacti 13y ago
Chaitin is cool, too.
- smosher 13y ago
  Chaitin's work is genius, but one thing bugs me: he uses a Cantor space in exchange for Gödel's countable numbering. I haven't found any commentary on that, but I find it suspicious. The problem with Cantor space is you simply can't even begin to approximate Chaitin's constant, but it seems like you could by using a countable numbering (all else being equal.) Of course that would blow everything up, so the takeaway is there is something very important which I'm not convinced we've learned yet.
- p4bl0 13y ago
  Came here to say that. See [1] my review of his awesome book "The Limits of Mathematics" + HN discussion. [1] https://news.ycombinator.com/item?id=1725936 https://news.ycombinator.com/item?id=1725936
- andyjohnson0 13y ago
  Definitely. I'd recommend his book Meta Math: The Quest for Omega [1]. He posted the full text of the book on arXiv [2]. [1] https://www.amazon.co.uk/Meta-Maths-Gregory-J-Chaitin/dp/184354525X https://www.amazon.co.uk/Meta-Maths-Gregory-J-Chaitin/dp/184... [2] http://arxiv.org/abs/math/0404335 http://arxiv.org/abs/math/0404335
brisance 13y ago
Does this mean that the antivirus industry is nothing but a scam?
- lordmax 13y ago
  it means antivirus industry will never be "complete"
  - chriswarbo 13y ago
    Indeed, many incompleteness results (the most famous being the Halting Problem) are known as "infinite employment theorems". For example, we can always make a compiler perform more optimisations as follows: 1) Every diverging (non-terminating, non-co-terminating) program can be optimised to the following: 10 GOTO 10 2) The Halting Problem tells us that no compiler can spot every diverging program. 3) Hence there is room for more optimisation, by spotting more diverging programs. 4) Hence there is always more work to do for compiler developers.
6ren 13y ago
There's a translation of Gödel's paper linked via his wikipedia entries https://docs.google.com/viewer?url=http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf https://docs.google.com/viewer?url=http://www.research.ibm.c... [google docs viewer] curious facts: he died of starvation; he was a theist http://en.wikipedia.org/wiki/Kurt_G%C3%B6del#Later_years_and_death http://en.wikipedia.org/wiki/Kurt_G%C3%B6del#Later_years_and...
- kybernetikos 13y ago
  I found your semicolon quite confusing there - it seemed to suggest that there was some relationship between being a theist and dying of starvation.
  - Radim 13y ago
    On the contrary. I imagine 6ren went to extra lengths to use a semicolon instead of a simple comma, as semicolons are used to emphasize independent clauses.
    - kybernetikos 13y ago
      Independent clauses can stand by themselves grammatically, that doesn't mean that their meanings are independent. e.g. > I hit him as hard as I could; he laughed at me. Those are 'independent clauses', but the semicolon emphasizes the connection between them.
      - 6ren 13y ago
        Radim is right. I actually tried a couple of other forms ("and" and ","), but they seemed worse. Challenge: can you demonstrate a better way? I think the problem is not syntax but semantics: two unusual facts beg connection. BTW: getting back on topic, his starvation seems due to a lack of faith... if some connection is expected, perhaps the best solution is to supply one, perhaps the poignant He believed in God, yet died from lack of faith.
bitdiddle 13y ago
What I find interesting are the claims Penrose[1] and others make about human versus machine intelligence based on Godel's results. [1] https://en.wikipedia.org/wiki/Philosophy_of_artificial_intelligence#Lucas.2C_Penrose_and_G.C3.B6del https://en.wikipedia.org/wiki/Philosophy_of_artificial_intel...
- chriswarbo 13y ago
  I'm sceptical of Penrose's arguments. We don't see human brains as symbol-manipulating formal systems, but that doesn't mean that aren't (or, more correctly, that doesn't mean that there is no symbol-manipulating formal system which is isomorphic to a particular brain, or brains in general). Brains aren't implementing any known algorithm, but that doesn't mean they aren't implementing any unknown algorithm. It brings to mind Minksky's advice to Sussman http://en.wikipedia.org/wiki/Hacker_koan#Uncarved_block http://en.wikipedia.org/wiki/Hacker_koan#Uncarved_block

132 points by jamesmiller5 13y ago

It would be interesting to speculate the consequence of Godel's Incompleteness deductions on the quest for Grand Unified Field Theorems in theoretical physics

mvp 13y ago

This article took me to another from the same author 'http://skibinsky.com/godel-incompleteness-for-startups/#footnote-4' http://skibinsky.com/godel-incompleteness-for-startups/#foot... and I found the below statement and laughed out aloud. Although in the context, this statement makes sense, in general, I trust books that don't belong to human-related matters (technical etc), because in human-related matters it is mostly one's opinion against others. "As soon as these popular books leave the domain of human-related matters you are totally on your own."

wicknicks 13y ago

Oh wow! This is a great write up on Godel's work. Anybody who even vaguely cares about fundamentals of computer science should definitely give it a read, and if possible a thorough read. Slightly related: Although a more technical/deeper discussion, but the book "Godel's Proof"[1] by Nagel and Newman is a very approachable text in this domain, and explains many aspects of the incompleteness theorems. [1] http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814758371 http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814...

chriswarbo 13y ago
I found it quite approachable and thorough, although it throws the the diagonal lemma out there without any real explanation even though it's crucial to the reasoning that follows it. Also I disagree with the completely unfounded assumptions at the end that the (terribly named) Reals have something to do with reality. The Reals are a Mathematical curiosity at best, but more often than not they complicate the understanding of subjects to which they have no relevance, eg. fractions (especially their decimal notation), calculus, physics, computing (especially floating point) and so on. It's fine to treat infinite constructs like the Reals declaratively, eg. as functions which can be composed, but it's meaningless to reason about doing things to their 'final results', since there are no such things by definition. In more precise terms, it makes sense to reason about the output of co-terminating functions (which loop forever, spitting out, for example, a never-ending sequence of digits) but not diverging functions (which loop forever without ever getting as far as their first digit).
- stiff 13y ago
  The real numbers have no relevance to calculus? Is there a way of doing calculus without real numbers that is simpler? What are you talking about?
hobs 13y ago
Honorable mention for http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach which has been mentioned many times on HN. Has many different ways of explaining Godel's genius. Though to be fair you could just read this article and be good.
- hamiltonkibbe 13y ago
  GEB is awesome. David Foster Wallace's Everything and More: A Compact History of Infinity covers Cantor and is an interesting read about... you guessed it.. Infinity. Re: Turing http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html
- tekromancr 13y ago
  +1 for GEB. I have been reading it on and off for about 2 years. It's a fun book, but every time I finish a reading session, I am exhausted. I am about 25% through.
  - hobs 13y ago
    Yeah it took me about 7 months to finish it, and you are right, every time I just felt beat and my mind was racing, what a great book.
  - laxatives 13y ago
    IMO just finish chapter 14 and you've basically finished the Godel portion of the book. The rest felt more like Hofstadter's random musings on AI, DNA and some other topics (some of which felt outdated). There's some crazy anecdotes of Ramanujin that I had never heard elsewhere though.
    - pachydermic 13y ago
      Well the structure of the book is supposed to be like a JS Bach song - so in the end, what you get is a combining of all the familiar themes and sometimes it feels a bit repetitive and boring. But if you've read that far, it's worth reading the rest. It's much easier to get through than when you're seeing stuff for the first time and really trying to wrap your head around it.
deleted 13y ago
[deleted]

Cacti 13y ago

Chaitin is cool, too.

smosher 13y ago
Chaitin's work is genius, but one thing bugs me: he uses a Cantor space in exchange for Gödel's countable numbering. I haven't found any commentary on that, but I find it suspicious. The problem with Cantor space is you simply can't even begin to approximate Chaitin's constant, but it seems like you could by using a countable numbering (all else being equal.) Of course that would blow everything up, so the takeaway is there is something very important which I'm not convinced we've learned yet.
p4bl0 13y ago
Came here to say that. See [1] my review of his awesome book "The Limits of Mathematics" + HN discussion. [1] https://news.ycombinator.com/item?id=1725936 https://news.ycombinator.com/item?id=1725936
andyjohnson0 13y ago
Definitely. I'd recommend his book Meta Math: The Quest for Omega [1]. He posted the full text of the book on arXiv [2]. [1] https://www.amazon.co.uk/Meta-Maths-Gregory-J-Chaitin/dp/184354525X https://www.amazon.co.uk/Meta-Maths-Gregory-J-Chaitin/dp/184... [2] http://arxiv.org/abs/math/0404335 http://arxiv.org/abs/math/0404335

brisance 13y ago

Does this mean that the antivirus industry is nothing but a scam?

lordmax 13y ago
it means antivirus industry will never be "complete"
- chriswarbo 13y ago
  Indeed, many incompleteness results (the most famous being the Halting Problem) are known as "infinite employment theorems". For example, we can always make a compiler perform more optimisations as follows: 1) Every diverging (non-terminating, non-co-terminating) program can be optimised to the following: 10 GOTO 10 2) The Halting Problem tells us that no compiler can spot every diverging program. 3) Hence there is room for more optimisation, by spotting more diverging programs. 4) Hence there is always more work to do for compiler developers.

6ren 13y ago

There's a translation of Gödel's paper linked via his wikipedia entries https://docs.google.com/viewer?url=http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf https://docs.google.com/viewer?url=http://www.research.ibm.c... [google docs viewer] curious facts: he died of starvation; he was a theist http://en.wikipedia.org/wiki/Kurt_G%C3%B6del#Later_years_and_death http://en.wikipedia.org/wiki/Kurt_G%C3%B6del#Later_years_and...

kybernetikos 13y ago
I found your semicolon quite confusing there - it seemed to suggest that there was some relationship between being a theist and dying of starvation.
- Radim 13y ago
  On the contrary. I imagine 6ren went to extra lengths to use a semicolon instead of a simple comma, as semicolons are used to emphasize independent clauses.
  - kybernetikos 13y ago
    Independent clauses can stand by themselves grammatically, that doesn't mean that their meanings are independent. e.g. > I hit him as hard as I could; he laughed at me. Those are 'independent clauses', but the semicolon emphasizes the connection between them.
    - 6ren 13y ago
      Radim is right. I actually tried a couple of other forms ("and" and ","), but they seemed worse. Challenge: can you demonstrate a better way? I think the problem is not syntax but semantics: two unusual facts beg connection. BTW: getting back on topic, his starvation seems due to a lack of faith... if some connection is expected, perhaps the best solution is to supply one, perhaps the poignant He believed in God, yet died from lack of faith.

bitdiddle 13y ago

What I find interesting are the claims Penrose[1] and others make about human versus machine intelligence based on Godel's results. [1] https://en.wikipedia.org/wiki/Philosophy_of_artificial_intelligence#Lucas.2C_Penrose_and_G.C3.B6del https://en.wikipedia.org/wiki/Philosophy_of_artificial_intel...

chriswarbo 13y ago
I'm sceptical of Penrose's arguments. We don't see human brains as symbol-manipulating formal systems, but that doesn't mean that aren't (or, more correctly, that doesn't mean that there is no symbol-manipulating formal system which is isomorphic to a particular brain, or brains in general). Brains aren't implementing any known algorithm, but that doesn't mean they aren't implementing any unknown algorithm. It brings to mind Minksky's advice to Sussman http://en.wikipedia.org/wiki/Hacker_koan#Uncarved_block http://en.wikipedia.org/wiki/Hacker_koan#Uncarved_block