3 ms·

I'm absolutely out of the loop and didn't even remember what a BB game is (that's why I clicked, TBH), but when reading your post the first thing that came to m

by krick 5y ago

I'm absolutely out of the loop and didn't even remember what a BB game is (that's why I clicked, TBH), but when reading your post the first thing that came to my mind was hydra games, as in "Goodstein's theorem". Goodstein sequences are known to reach 0, eventually (unlike the Collatz function, ironically), but that requires some absoulutely astronomical number of steps. I have no idea how complicated it is to encode, though. So, was it used in generating BBs as well?

throwaway81523 5y ago
The two most interesting facts about the Goodstein algorithm are 1) that it always halts (Goodstein's theorem); and that 2) in a certain narrow technical sense of the word "difficult", it is difficult to prove that the Goodstein algorithm always halts. The proof of this "difficulty" is called the Kirby-Paris theorem, described in the Wikipedia article about Goodstein's theorem. Goodstein proved the first of these two facts, and Kirby & Paris proved the second one some years later. There are ways to concoct algorithms along the lines of Goodstein's, that are even harder to prove always halt, and that take even longer / grow even faster. I haven't heard of anyone using any of these as BB champions but it seems like an unsatisfying answer, since you already know they halt. What is nicer about the Collatz and similar iterations is that you don't know whether they halt. So maybe your current champion takes 123456789 steps before halting, and you've got a Collatz parameter that you experimentally find runs for even more steps, but does will it eventually halt and become your new champion, or will it never halt? The only way to find out is keep running it, and similar keep running all the other parameters that, in your current knowledge, might or might not halt. See https://googology.wikia.org https://googology.wikia.org for some fast-growing functions, such as the Buchholz hydra which grows much faster than Goodstein's.
tromp 5y ago
While Goodstein sequences do get really long quite fast, they're not that easy to code. This binary lambda calculus program [1] may be the shortest possible, but still takes 351 bits. Meanwhile, in a mere 215 bits, we can encode a Laver table program [2] that potentially grows so much faster than Goodstein, that it's not even provable in ZFC [3]. [1] https://github.com/tromp/AIT/blob/master/goodstein.lam https://github.com/tromp/AIT/blob/master/goodstein.lam [2] https://github.com/tromp/AIT/blob/master/laver.lam https://github.com/tromp/AIT/blob/master/laver.lam [3] https://codegolf.stackexchange.com/questions/79620/laver-table-computations-and-an-algorithm-that-is-not-known-to-terminate-in-zfc https://codegolf.stackexchange.com/questions/79620/laver-tab...

by krick 5y ago

throwaway81523 5y ago

The two most interesting facts about the Goodstein algorithm are 1) that it always halts (Goodstein's theorem); and that 2) in a certain narrow technical sense of the word "difficult", it is difficult to prove that the Goodstein algorithm always halts. The proof of this "difficulty" is called the Kirby-Paris theorem, described in the Wikipedia article about Goodstein's theorem. Goodstein proved the first of these two facts, and Kirby & Paris proved the second one some years later. There are ways to concoct algorithms along the lines of Goodstein's, that are even harder to prove always halt, and that take even longer / grow even faster. I haven't heard of anyone using any of these as BB champions but it seems like an unsatisfying answer, since you already know they halt. What is nicer about the Collatz and similar iterations is that you don't know whether they halt. So maybe your current champion takes 123456789 steps before halting, and you've got a Collatz parameter that you experimentally find runs for even more steps, but does will it eventually halt and become your new champion, or will it never halt? The only way to find out is keep running it, and similar keep running all the other parameters that, in your current knowledge, might or might not halt. See https://googology.wikia.org https://googology.wikia.org for some fast-growing functions, such as the Buchholz hydra which grows much faster than Goodstein's.

tromp 5y ago

While Goodstein sequences do get really long quite fast, they're not that easy to code. This binary lambda calculus program [1] may be the shortest possible, but still takes 351 bits. Meanwhile, in a mere 215 bits, we can encode a Laver table program [2] that potentially grows so much faster than Goodstein, that it's not even provable in ZFC [3]. [1] https://github.com/tromp/AIT/blob/master/goodstein.lam https://github.com/tromp/AIT/blob/master/goodstein.lam [2] https://github.com/tromp/AIT/blob/master/laver.lam https://github.com/tromp/AIT/blob/master/laver.lam [3] https://codegolf.stackexchange.com/questions/79620/laver-table-computations-and-an-algorithm-that-is-not-known-to-terminate-in-zfc https://codegolf.stackexchange.com/questions/79620/laver-tab...