Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

A few parts of this are inaccurate.

Undecidability is about the impossibility of predicting what programs will do. You have proven that there are functions from integers to integers that we cannot program, but that is not at all the same thing. Deciding whether a Turing machine will halt is one of these functions, but proving that is different than just proving that such functions exist.

Your proof that there are unprovable statements also doesn't work, as can be seen from the fact that some theories are decidable, such as Presburger arithmetic, which is the theory of the natural numbers without multiplication. The flaw here is your correspondence between propositions about naturals and functions from the naturals to the booleans. It's not clear how you want to set up this bijection, but there is actually no way of doing so, as the set of propositions about the naturals expressible in any alphabet is the same size as the naturals, by the same argument you use in your second paragraph. It therefore must be smaller, rather than the same size as, the set of functions from ℕ to the booleans.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: