It must be true that the number of instructions of the code that finds the Busy Beaver (e.g. all that hard work done to find BB(5)) cannot be the size of BB you are looking for.
If we assume it is equal you'd need to work out if your code stopped, and hence the value of the BB in order to find the value. A contradiction.
From that there is no general solution or magic pattern to this, which is kind of obvious.
Which makes the sequence of BB values uncomputable.
String those together into a decimal and that is an uncomputable number.
===
We can also say something about the general problem.
There is a machine Mn which spits out the Busy Beaver number for n (BBn)! Its the machine that replaces all the manual work so far to find BB(1...5). So e.g. M5 = 47176870. And if we are going to solve this there must be a master MM(n) which takes any number of instructions and gives the corresponding BB number for machines with that many instructions. MM is the projected sum of all the work on Busy Beavers. Assume MM has a finite number of instructions itself say N. So we can ask what is the busy-beaver for MM(N) and it would need to decide if it itself halted or not. Now we're in trouble. Assume MM(N) gives a number BBN to do this it would already need to know that it halted and so would already know the answer which is a contradiction. SO there is no finite set of instructions that will solve MM(n) and so the problem is unsolvable.
Obviously doesn't stop us doing it for particular size Turing machines, but there is no magic master pattern or set of instructions to solve in general.
No comments:
Post a Comment