3 ms·

Collatz-like behavior of Busy Beavers

78 points by nickdrozd 5y ago

tromp 5y ago
The Collatz like behaviour may be specific to the choice of Turing Machines as computational model. In functional busy beavers we see the emergence of repeated exponentiation [1] at similar sizes (the TM in the article takes 32 bits to describe given the statecount). [1] https://oeis.org/A333479 https://oeis.org/A333479
- R0b0t1 5y ago
  Interesting! I remember seeing some BB program outputs and noticing the structure.
- jerf 5y ago
  What it is is specific to the choice of Turing Machines as a model, and the teeny-tiny small size of Turing Machines that we can afford to analyze by hand for BBB size. It so happens that Collatz-like behavior is simply the most efficient behavior for creating large quasi-halting counts with so few states to work with. One of the ways I think about how large the conventional-BB (two Bs) function is is to think about how large a TM it would take to simulate some other putatively-larger sequence. Consider the famous Tree function, for instance. Tree(3) is wildly larger than BB(3)... BB(3) is 21, Tree(3) is effectively inexpressible. Surely with such a head start, the Tree function is larger than BB? Consider, how many states would it take to program the Tree function? Surely it is a finite number, and even in a very simple TM's restricted notation, let's call it easily less than 10,000 states, where I'm being very generous because I suspect it's probably comfortably fewer than 100, but all I need is for it to be finite. Then, consider two TMs basically smashed together; for one, we use the BB winner to generate its number on the tape, then for the next one, we use that as input to compute "Tree" of that number. (Some math work would be needed to properly weave them together but it's not that hard.) Then we have some number of states after which our BB candidates are computing Tree(BB(1)) vs. Tree(10,005) or so (giving a few states to work with to fold the TMs together), then Tree(BB(2)) vs Tree(10,006), and it's not hard to see that this sequence is going to blow tree away in just a few more iterations and never look back. And these composited "Tree(BB(x))" functions are, by human standards, infinitesimally tiny compared to the real BB(10,006), because the busy beaver function just keeps optimally using every single state you give it to compute some ever-harder and more complex math function. As you scale up in the TM size, the "problems" it will be solving will change as it has the states to represent them, because the BB function (and the BBB function) explore all possible TMs of a given size. So, what seeing Collatz-like conjectures at such tiny TM sizes means is that the Collatz conjecture is essentially the simplest hard problem, by the defensible (albeit not unique) standard of "what it takes to understand the behavior of a Turing machine". It also means, measuring by the complexity of understanding the behavior of a Turing machine that solves the problem, for all Mankind's millennia of mathematical development and problem solving, there is a math problem that we don't fully understand represented a mere four steps into the mathematical thicket. (That is, yes, this particular instance was solved nicely in the linked article, but the generalized version of this problem immediately suggested is not solvable by our math.) Which is sobering.
  - Majromax 5y ago
    > Which is sobering. It's even more sobering than that: we already know that busy beaver functions hit the bounds of decidability. From Scott Aaronson's The Busy Beaver Frontier (https://www.scottaaronson.com/papers/bb.pdf https://www.scottaaronson.com/papers/bb.pdf), BB(748) is already undecidable under ZF set theory if the latter is consistent. Aaronson even conjectures that BB(20) is undecidable under ZF theory and that BB(10) is undecidable under Peano arithmetic -- he's thinks the existing proofs still have lots of room for improvement. If BB(10) is undecidable under Peano arithmetic, then all we're left with for BB analysis is the space of very small Turing machines.
  - confused_teapot 5y ago
    Just wanted to comment that I love your take on this. Especially that "the Collatz conjecture is essentially the simplest hard problem, by the defensible (albeit not unique) standard of "what it takes to understand the behavior of a Turing machine"".
- nickdrozd 5y ago
  When do Collatz-like functions start to show up with lambda calculus programs?
  - tromp 5y ago
    Pretty late, as it seems to require building up binary arithmetic first. A straightforward collatz step function on binary numbers that I just cobbled together weighs in at 282 bits...
nickdrozd 5y ago
The surprising thing about the program discussed in the article is that it isn't complicated at all. It's well-structured and elegant, with no "spaghetti" to speak of. It almost looks like something you could have written yourself, provided you knew the that this specific Collatz-like function takes such a long orbit on the input 2. It could be that larger Busy Beaver programs engage in programming tricks to run up high scores, but it could also be that the champion programs are always elegant, instead winning by exploiting increasingly wild mathematical facts. That's what we might expect based on the results of the Bigger Number Game [1] and the C Bignum Bakeoff [2]. [1] https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html [2] http://djm.cc/bignum-results.txt http://djm.cc/bignum-results.txt
myWindoonn 5y ago
Conway showed that Collatz-like functions are as hard as Halting, by creating a language called FRACTRAN whose programs are Collatz-like functions: https://esolangs.org/wiki/Fractran https://esolangs.org/wiki/Fractran

78 points by nickdrozd 5y ago

The Collatz like behaviour may be specific to the choice of Turing Machines as computational model. In functional busy beavers we see the emergence of repeated exponentiation [1] at similar sizes (the TM in the article takes 32 bits to describe given the statecount). [1] https://oeis.org/A333479 https://oeis.org/A333479

R0b0t1 5y ago
Interesting! I remember seeing some BB program outputs and noticing the structure.
jerf 5y ago
What it is is specific to the choice of Turing Machines as a model, and the teeny-tiny small size of Turing Machines that we can afford to analyze by hand for BBB size. It so happens that Collatz-like behavior is simply the most efficient behavior for creating large quasi-halting counts with so few states to work with. One of the ways I think about how large the conventional-BB (two Bs) function is is to think about how large a TM it would take to simulate some other putatively-larger sequence. Consider the famous Tree function, for instance. Tree(3) is wildly larger than BB(3)... BB(3) is 21, Tree(3) is effectively inexpressible. Surely with such a head start, the Tree function is larger than BB? Consider, how many states would it take to program the Tree function? Surely it is a finite number, and even in a very simple TM's restricted notation, let's call it easily less than 10,000 states, where I'm being very generous because I suspect it's probably comfortably fewer than 100, but all I need is for it to be finite. Then, consider two TMs basically smashed together; for one, we use the BB winner to generate its number on the tape, then for the next one, we use that as input to compute "Tree" of that number. (Some math work would be needed to properly weave them together but it's not that hard.) Then we have some number of states after which our BB candidates are computing Tree(BB(1)) vs. Tree(10,005) or so (giving a few states to work with to fold the TMs together), then Tree(BB(2)) vs Tree(10,006), and it's not hard to see that this sequence is going to blow tree away in just a few more iterations and never look back. And these composited "Tree(BB(x))" functions are, by human standards, infinitesimally tiny compared to the real BB(10,006), because the busy beaver function just keeps optimally using every single state you give it to compute some ever-harder and more complex math function. As you scale up in the TM size, the "problems" it will be solving will change as it has the states to represent them, because the BB function (and the BBB function) explore all possible TMs of a given size. So, what seeing Collatz-like conjectures at such tiny TM sizes means is that the Collatz conjecture is essentially the simplest hard problem, by the defensible (albeit not unique) standard of "what it takes to understand the behavior of a Turing machine". It also means, measuring by the complexity of understanding the behavior of a Turing machine that solves the problem, for all Mankind's millennia of mathematical development and problem solving, there is a math problem that we don't fully understand represented a mere four steps into the mathematical thicket. (That is, yes, this particular instance was solved nicely in the linked article, but the generalized version of this problem immediately suggested is not solvable by our math.) Which is sobering.
- Majromax 5y ago
  > Which is sobering. It's even more sobering than that: we already know that busy beaver functions hit the bounds of decidability. From Scott Aaronson's The Busy Beaver Frontier (https://www.scottaaronson.com/papers/bb.pdf https://www.scottaaronson.com/papers/bb.pdf), BB(748) is already undecidable under ZF set theory if the latter is consistent. Aaronson even conjectures that BB(20) is undecidable under ZF theory and that BB(10) is undecidable under Peano arithmetic -- he's thinks the existing proofs still have lots of room for improvement. If BB(10) is undecidable under Peano arithmetic, then all we're left with for BB analysis is the space of very small Turing machines.
- confused_teapot 5y ago
  Just wanted to comment that I love your take on this. Especially that "the Collatz conjecture is essentially the simplest hard problem, by the defensible (albeit not unique) standard of "what it takes to understand the behavior of a Turing machine"".
nickdrozd 5y ago
When do Collatz-like functions start to show up with lambda calculus programs?
- tromp 5y ago
  Pretty late, as it seems to require building up binary arithmetic first. A straightforward collatz step function on binary numbers that I just cobbled together weighs in at 282 bits...

nickdrozd 5y ago

The surprising thing about the program discussed in the article is that it isn't complicated at all. It's well-structured and elegant, with no "spaghetti" to speak of. It almost looks like something you could have written yourself, provided you knew the that this specific Collatz-like function takes such a long orbit on the input 2. It could be that larger Busy Beaver programs engage in programming tricks to run up high scores, but it could also be that the champion programs are always elegant, instead winning by exploiting increasingly wild mathematical facts. That's what we might expect based on the results of the Bigger Number Game [1] and the C Bignum Bakeoff [2]. [1] https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html [2] http://djm.cc/bignum-results.txt http://djm.cc/bignum-results.txt

myWindoonn 5y ago

Conway showed that Collatz-like functions are as hard as Halting, by creating a language called FRACTRAN whose programs are Collatz-like functions: https://esolangs.org/wiki/Fractran https://esolangs.org/wiki/Fractran