Re:The Busy Beaver Problem
by btilly on Thursday October 29, 2009 @11:38AM
(#910192)
Here is a fun thought.
There is no possible consistent axiom system understandable by humans in which it is possible to prove a specific number to be an upper bound for BB(1000000)!
Here is why. Suppose you have an axiom system. We can write a Turing machine that searches for proofs and disproofs of the consistency of this axiom system. If the axiom system is consistent the program will run forever. But if it is proven that BB(size of machine) has an upper limit then the program will eventually prove that the limit exists, and it has run past it, and therefore it will never halt, and therefore it will never find an inconsistency, and therefore the axiom system is consistent.
For the rest of my claim I claim that an axiom system that can be understood by humans can always be encoded in a Turing machine of size at most a million. I obviously have no proof of that, but it seems extremely likely to me.
For another fun thought, there is a school of mathematical philosophy in which BB(n) is not a well-defined function at all! (Look up the constructivists.)
There is no possible consistent axiom system understandable by humans in which it is possible to prove a specific number to be an upper bound for BB(1000000)!
Here is why. Suppose you have an axiom system. We can write a Turing machine that searches for proofs and disproofs of the consistency of this axiom system. If the axiom system is consistent the program will run forever. But if it is proven that BB(size of machine) has an upper limit then the program will eventually prove that the limit exists, and it has run past it, and therefore it will never halt, and therefore it will never find an inconsistency, and therefore the axiom system is consistent.
For the rest of my claim I claim that an axiom system that can be understood by humans can always be encoded in a Turing machine of size at most a million. I obviously have no proof of that, but it seems extremely likely to me.
For another fun thought, there is a school of mathematical philosophy in which BB(n) is not a well-defined function at all! (Look up the constructivists.)