= 27d567bc2d48d9f40e9ccc20ea370b15)
alexflint comments on What independence between ZFC and P vs NP would imply - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (62)
Your post doesn't seem to have anything to do with P vs NP, it's just a statement of indignation at Gödel's incompleteness theorems :-)
Here's a simplified example. Imagine you have an axiomatic "model of reality" that describes computers. Then I can write a computer program that successively generates all valid proofs in that axiom system. If the program stumbles upon a valid proof that 1=0, it halts, otherwise it goes on searching. It seems to be a "prima facie substantive question" whether the program will halt or not, but our axiom system cannot settle it because it cannot prove its own consistency by Gödel's second incompleteness theorem, unless it is inconsistent.
The root of the problem, IMO, is our inability to describe integers. By the Löwenheim–Skolem theorem, you cannot have an axiomatization of the integers that rules out nonstandard integers. I wrote several posts about this.
Good point, evidently I failed to really internalize Godel. I had dismissed Godel sentences as not questions about reality but your example is compelling.
Interestingly, your post on integers seemed to suggest you were also thinking that since our models of integers fail to live up to expectations we've somehow failed to describe them, but that it might yet be possible to do so.