Hacker News new | past | comments | ask | show | jobs | submit login

What are the practical implications of the incompleteness theorem?

Mathematics is postmodern; there's no single formal system which is the concrete bedrock of mathematics, and there will always be some true-but-unprovable theorems in consistent formal systems.

Cynics might take this to mean that maths is meaningless. On the contrary, I'd like to suggest that maths is the canonical emergent pattern; any formal system with sufficient complexity to represent itself will automatically exhibit some algebraic structure, and maths emerges naturally from there.

The biggest implication for computer scientists is that, combined with results of Church and Tarski, we should expect that meta-languages are more powerful than object-languages, whether this is by preprocessing and macros like in C/C++ and CL, or by avoiding using meta-features except when necessary like in Python and Ruby.

There will always be more math to be discovered, because there will always be theorems you can state but not prove within the confines of the existing systems.

You cannot ever know for sure that your software is bug free, because no finite system of logic is both true and complete.

At least, that’s my understanding of it.

Not exactly.

For any sufficiently powerful system (Turing completeness is definitely powerful enough) there are statements which are true but cannot be proven by that system. Secondarily, no system can demonstrate its own consistency.

However, if you limit your software enough, you can prove that every possible input is handled correctly. That involves removing Turing completeness. E.g. once you accept a language as a configurator, you can no longer prove that. CSS3 is Turing complete. JSON is not.

One requirement is limiting the size of inputs.

Afaik this is all related to relativity. No good or bad unless unrelated like ++ or -- and we're in a system where, at least humans, only perceive reality as it relates to us. You need air, so do I, together we have a similar need but also together we occupy each other's space and resource

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