4 ms·

Maybe I’m just an unsophisticated code monkey, but I read a little about Busy Beaver from time to time and I just don’t get it. Why is this an interesting probl

Maybe I’m just an unsophisticated code monkey, but I read a little about Busy Beaver from time to time and I just don’t get it. Why is this an interesting problem? What do we hope to learn from it?

lkuty 2y ago
IMO, because it gives you a way to know if a program will terminate or not. If it consists of 5 states and goes beyond 47176870 steps of execution, then it will never halt. However, we are currently limited to 1 to 5 states Turing programs. And you can make correspondance between some Turing machines and some theorems in Mathematics thus it gives you a way to prove them I guess.
- suzzer99 2y ago
  The one thing I didn't understand is the distribution 1s and 0s on the tape. Does each Turing machine have to be solved for all possible combinations of 1s and 0s?
  - ropejumper 2y ago
    The game is defined to start with an infinite all-zeroes tape.
    - chmod775 2y ago
      An important observation is that it doesn't really matter what you start with, because you have two ways to "reduce" each Turing machine to one that can start with all zeroes: - You can "flip" rules/initial tape values, trying to get a machine that can start with all 0s. This is not always possible. A trivial case where it is possible is a machine that wants to start with all 1s (just flip everything). - You can insert more rules to set the tape up as needed. This makes it an BBn+x busy beaver candidate, but at least it's not your problem at BBn now. The last way can get a bit complicated because you need to insert ad-hoc logic, since the tape is infinitely long. So it's not a just a case of inserting setup at the beginning of the program (because you can't setup an infinite tape in finite steps). Also to be fair this second point is a non-trivial assertion and requires proof that it is actually possible to do in every case. It is obviously possible to do for every machine that runs in finite steps though (since it can only consider a finite amount of tape). Luckily actual computers have finite memory which is generally initialized with 0 anyways.
- DowsingSpoon 2y ago
  Thank you! I’m trying to read up on it now also because this is definitely not something I know much about.
MrCheeze 2y ago
https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html
GTP 2y ago
> Why is this an interesting problem? What do we hope to learn from it? Because it's a complicated puzzle, not necessarily because we hope to learn something from it. Which could happen, but it's definitely not the primary goal here.

lkuty 2y ago

IMO, because it gives you a way to know if a program will terminate or not. If it consists of 5 states and goes beyond 47176870 steps of execution, then it will never halt. However, we are currently limited to 1 to 5 states Turing programs. And you can make correspondance between some Turing machines and some theorems in Mathematics thus it gives you a way to prove them I guess.

suzzer99 2y ago
The one thing I didn't understand is the distribution 1s and 0s on the tape. Does each Turing machine have to be solved for all possible combinations of 1s and 0s?
- ropejumper 2y ago
  The game is defined to start with an infinite all-zeroes tape.
  - chmod775 2y ago
    An important observation is that it doesn't really matter what you start with, because you have two ways to "reduce" each Turing machine to one that can start with all zeroes: - You can "flip" rules/initial tape values, trying to get a machine that can start with all 0s. This is not always possible. A trivial case where it is possible is a machine that wants to start with all 1s (just flip everything). - You can insert more rules to set the tape up as needed. This makes it an BBn+x busy beaver candidate, but at least it's not your problem at BBn now. The last way can get a bit complicated because you need to insert ad-hoc logic, since the tape is infinitely long. So it's not a just a case of inserting setup at the beginning of the program (because you can't setup an infinite tape in finite steps). Also to be fair this second point is a non-trivial assertion and requires proof that it is actually possible to do in every case. It is obviously possible to do for every machine that runs in finite steps though (since it can only consider a finite amount of tape). Luckily actual computers have finite memory which is generally initialized with 0 anyways.
DowsingSpoon 2y ago
Thank you! I’m trying to read up on it now also because this is definitely not something I know much about.

MrCheeze 2y ago

https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html

GTP 2y ago

> Why is this an interesting problem? What do we hope to learn from it? Because it's a complicated puzzle, not necessarily because we hope to learn something from it. Which could happen, but it's definitely not the primary goal here.