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

71–74 of 74 posts

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

#71

Post by pfdietz »

GoblinSlayer wrote: post #70
pfdietz wrote: post #68

Earlier quoted context omitted.

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.

> Paradox is a statement that can't be proved true or false

No it isn't.

> execution of a Turing machine can't be expressed as a Gödel number

Yes it can.

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

#72

Post by [deleted] »

matherial wrote: post #9

> However, although G is undecidable, it’s clearly true. That's... not really true; it's surprising to see it in Quanta, of all places. Godel's (separate) completeness theorem says that in first-order logic, anything that's semantically true in all possible scenarios can be syntactically proved. So, if G is "clearly true", that ought to make it provable. The theorems don't contradict each other because in FOL, G is n…

[deleted]

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

#73

Post by jpulgarin »

matherial wrote: post #9

> However, although G is undecidable, it’s clearly true. That's... not really true; it's surprising to see it in Quanta, of all places. Godel's (separate) completeness theorem says that in first-order logic, anything that's semantically true in all possible scenarios can be syntactically proved. So, if G is "clearly true", that ought to make it provable. The theorems don't contradict each other because in FOL, G is n…

G says: "I am not provable". As shown by Gödel, that's a true statement about G, ergo G is true. That first-order logic cannot prove it to be true is an indictment on the power of deduction, not on the truthiness of G.
Post reply on HN