Tag Archives: undecidability

Unpredictable enough

Gödel proved that within any formal system sufficiently powerful to include ordinary arithmetic, there will always be  undecidable statements that cannot be proved true, yet cannot be proved false. Turing proved that within any formal (or mechanical) system, not only are there functions that can be given a finite description yet cannot be computed by […]