Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How Gödel's Proof Works (2020)

quantamagazine.org

Post reply on HN
Print view View original

61–70 of 74 posts

Re: How Gödel's Proof Works (2020)

#61

Post by pfdietz »

GoblinSlayer wrote: post #52
pfdietz wrote: post #26

You can also obtain incompleteness from the unsolvability of the halting problem, by noting that if every statement in (say) Peano arithmetic were provable, one could solve the halting problem. Encode a halting execution of a TM as an integer using Gödel numbers and write a statement that the execution halts. Either that statement or its negation would be provable, so search for proofs for each at the same time. An a…

That won't work. Gödel number encodes a paradox, but a halting execution of a TM is not a paradox, so can't be written as a Gödel number.

Your word salad is not even wrong. For example:

> Gödel number encodes a paradox

WTF do you mean by this?

Re: How Gödel's Proof Works (2020)

#62

Post by [deleted] »

erichocean wrote: post #35
reliablereason wrote: post #33

Gödels incompleteness is just an example of the fact that you cant determine the outcome of infinite regression (in the general case). The same as me asking you to give me the last digit of pi. I am a bit annoyed by pop science always twisting it to sound so convoluted.

I thought it was sorting an infinite set of infinite strings as the first step in the "algorithm" that seemed sketchy. [0] It's definitely not a constructive proof, even though it pretends to be; none of the mathematical objects can be constructed, nor can any of the algorithmic steps be executed. That said, it's far less well-known that the workaround (if you find it to be true) is trivially easy (from Alfred Tarski…

[deleted]

Re: How Gödel's Proof Works (2020)

#63

Post by Maxatar »

reliablereason wrote: post #33

Gödels incompleteness is just an example of the fact that you cant determine the outcome of infinite regression (in the general case). The same as me asking you to give me the last digit of pi. I am a bit annoyed by pop science always twisting it to sound so convoluted.

There is no infinite regression involved in any of Godel's theorems.

Re: How Gödel's Proof Works (2020)

#64

Post by seanhunter »

quaverquaver wrote: post #7
gavinsyancey wrote: post #3

If you find this interesting, I highly recommend reading "Gödel, Escher, Bach: an Eternal Golden Braid"

while it is a groovy into to recursion and other cool ideas, GEB annoys me in that I feel like the three figures in the title are ill matched. Godel proves a super important result in math, sure... Escher was a skilled draughtsman who had a feel for tesselation. An OK artist IMO but no special insights. Bach on the other hand was an expressive genius who in the volume, power and beauty of his productions just seemed…

Yeah. My brother was really into GEB but for the exact reason you laid out I never even gave it a chance because just from the title it really seems to trivialise the artistic achievements of Bach to have him be included in that list.

The only mathematical figure I feel you could reasonably compare to Bach would be Euler. I would read that book if someone wrote it.

Re: How Gödel's Proof Works (2020)

#65

Post by seanhunter »

bobson381 wrote: post #14
quaverquaver wrote: post #7

Earlier quoted context omitted.

while it is a groovy into to recursion and other cool ideas, GEB annoys me in that I feel like the three figures in the title are ill matched. Godel proves a super important result in math, sure... Escher was a skilled draughtsman who had a feel for tesselation. An OK artist IMO but no special insights. Bach on the other hand was an expressive genius who in the volume, power and beauty of his productions just seemed…

the linking thread for all three is self-reference, either in the form of a fugue or in a painting showing its own creation. Doug is a loop guy

And Bach did indeed write variations on B-A-C-H[1]. But lots of composers have self-referencing cryptograms and other riddles in music. You would find far more in Scriabin, Bartok or Alban Berg for example.

It also doesn’t fit the narrative but the idea of self-reference in art didn’t start with Escher either. For example the Arnolfini wedding portrait by van Eyck[2]

[1] Bb A C B in modern notation https://en.wikipedia.org/wiki/BACH_motif

[2] https://en.wikipedia.org/wiki/Arnolfini_Portrait The artist can be seen in a reflection in the central mirror that he has ostentatiously signed his name above. It’s an incredible painting and worth a trip to the National Gallery to see if you’re ever in London.

Re: How Gödel's Proof Works (2020)

#66

Post by reliablereason »

Maxatar wrote: post #63
reliablereason wrote: post #33

Gödels incompleteness is just an example of the fact that you cant determine the outcome of infinite regression (in the general case). The same as me asking you to give me the last digit of pi. I am a bit annoyed by pop science always twisting it to sound so convoluted.

There is no infinite regression involved in any of Godel's theorems.

Yes there is. The use of Gödel numbers to represent a system that contain itself is infinite regression.

Re: How Gödel's Proof Works (2020)

#67

Post by GoblinSlayer »

pfdietz wrote: post #61
GoblinSlayer wrote: post #52

Earlier quoted context omitted.

That won't work. Gödel number encodes a paradox, but a halting execution of a TM is not a paradox, so can't be written as a Gödel number.

Your word salad is not even wrong. For example: > Gödel number encodes a paradox WTF do you mean by this?

A statement that can't be proved true or false and thus demonstrates incompleteness of logic.

Re: How Gödel's Proof Works (2020)

#68

Post by pfdietz »

GoblinSlayer wrote: post #67
pfdietz wrote: post #61

Earlier quoted context omitted.

Your word salad is not even wrong. For example: > Gödel number encodes a paradox WTF do you mean by this?

A statement that can't be proved true or false and thus demonstrates incompleteness of logic.

How is that a paradox? And how does that imply the correct argument I gave doesn't work? (It doesn't imply that.)

Re: How Gödel's Proof Works (2020)

#69

Post by gregfjohnson »

rramadass wrote: post #56
gregfjohnson wrote: post #31

Show HN: I recently gave a talk on the incompleteness theorem, specifically expressed in the language of software. It starts with a bit of historical background and a discussion of some of the philosophical context in which he carried out his work. The second half of the talk is my attempt to show the beautiful essential idea at the core of Godel's idea, pitched to a technically knowledgeable general audience. These…

Very Nice; Thank You! Is there a way to get a pdf of the slides?

Glad to! I put them on https://gregfjohnson.com/godel_incompleteness.pdf

Re: How Gödel's Proof Works (2020)

#70

Post by GoblinSlayer »

pfdietz wrote: post #68
GoblinSlayer wrote: post #67

Earlier quoted context omitted.

A statement that can't be proved true or false and thus demonstrates incompleteness of logic.

How is that a paradox? And how does that imply the correct argument I gave doesn't work? (It doesn't imply that.)

Paradox is a statement that can't be proved true or false; "this statement is false" is an example of Gödel statement. The argument doesn't work, because execution of a Turing machine can't be expressed as a Gödel number.
Post reply on HN