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

The Busy Beaver numbers express a limitation of classes of axiomatic systems, not merely of Turing Machines.

It's not merely that computers aren't guaranteed to be able to calculate these. BB(n) for some n <= 745 is independent of the ZFC axioms of set theory.

Furthermore, Gödel's theorem and Turing's problem are related. It is undecidable whether a Turing machine halts, it's not just that you can't write a Turing machine that decides whether another Turing machine halts.

Without Gödel's theorem, you could try to enumerate all possible proofs in your complete and consistent axiomatic system until you find one that proves whether an arbitrary Turing machine of your choosing halts, and you'd have conceptually solved the halting problem. (Then, you could encode that whole algorithm in a Turing machine (TM), and have that new TM be your decider that solves the halting problem, if you wanted).

Because of Gödel you can't do this, whether on paper, with a TM, or even in principle. Your axiomatic system is not complete, so there are things it simply cannot prove. Like the halting problem, or in the case of ZF the value of BB(745).




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

Search: