martix
- 167
- 5
- TL;DR
- It is said that the busy beaver function is noncomputable. I want to understand what that means.
An ill advised late night plunge into a math rabbit hole left me confused. It started with Graham's number and ended with me trying to understand what noncomputable numbers and functions are. I'm not ready to tackle things like Rayo's number or SGC(n), but I did come across something that seemed fairly simple - the busy beaver game.
It is said that the busy beaver function is noncomputable. I want to understand what that means.
My current understanding is that the function is noncomputable because the halting problem is embedded within.
Here is my current understanding, gleaned from the wikipedia article:
We have n - the number of states in a 2-symbol turing machine (0 and 1)
Σ(n), the busy beaver function gives us that turing machine that outputs the most 1s out of all n-state 2s machines.
The number of 2s machines with n states is finite - (4n + 4)^2n.
Based on the definition of the game, these finite machines can be split in 2 categories/sets:
Machines that halt
Machines that don't halt.
From this point alone, it seems clear to me why Σ(n) is noncomputable - while the categories are valid, a general way to decide which machine goes into which set is impossible to construct.
(Anything wrong with my reasoning so far?)
Here is where my confusion starts.
Wikipedia states that an algorithm to decide whether a given machine is a busy beaver cannot exist ("general algorithm" being the precise wording, don't know if it matters).
But... what if we take all (4n + 4)^2n machines with n states and run them in parallel. We already have infinite tape - what's stopping us from running them for an infinite amount of time? Doesn't this qualify as an algorithm? Or is there something about requiring infinite time that disqualifies something from being an algorithm, whereas requiring infinite space does not?
Or, even if we don't run them for an infinite amount of time, just a sufficiently large amount of time, I would expect to end up in one of 2 situations in a finite amount of time:
1. Machine halts
2. Machine enters a loop
At the point where we determine the loop of each machine that has one, we have "computed" the busy beaver function.
The one hiccup I can think of here is, if it's possible to run forever without entering some sort of loop, but I personally can't conceive how.
Another final confusion is what is meant by "state" of a turing machine. It's not the arrangement of 1s and 0s on the tape so far as I can determine. My current best guess is that a "state" is 1 row in the transition table of the machine.
It is said that the busy beaver function is noncomputable. I want to understand what that means.
My current understanding is that the function is noncomputable because the halting problem is embedded within.
Here is my current understanding, gleaned from the wikipedia article:
We have n - the number of states in a 2-symbol turing machine (0 and 1)
Σ(n), the busy beaver function gives us that turing machine that outputs the most 1s out of all n-state 2s machines.
The number of 2s machines with n states is finite - (4n + 4)^2n.
Based on the definition of the game, these finite machines can be split in 2 categories/sets:
Machines that halt
Machines that don't halt.
From this point alone, it seems clear to me why Σ(n) is noncomputable - while the categories are valid, a general way to decide which machine goes into which set is impossible to construct.
(Anything wrong with my reasoning so far?)
Here is where my confusion starts.
Wikipedia states that an algorithm to decide whether a given machine is a busy beaver cannot exist ("general algorithm" being the precise wording, don't know if it matters).
But... what if we take all (4n + 4)^2n machines with n states and run them in parallel. We already have infinite tape - what's stopping us from running them for an infinite amount of time? Doesn't this qualify as an algorithm? Or is there something about requiring infinite time that disqualifies something from being an algorithm, whereas requiring infinite space does not?
Or, even if we don't run them for an infinite amount of time, just a sufficiently large amount of time, I would expect to end up in one of 2 situations in a finite amount of time:
1. Machine halts
2. Machine enters a loop
At the point where we determine the loop of each machine that has one, we have "computed" the busy beaver function.
The one hiccup I can think of here is, if it's possible to run forever without entering some sort of loop, but I personally can't conceive how.
Another final confusion is what is meant by "state" of a turing machine. It's not the arrangement of 1s and 0s on the tape so far as I can determine. My current best guess is that a "state" is 1 row in the transition table of the machine.