2 ms·

Summary: brute force search of the space of 4-state TM programs yielded a BB champion with an initially mysterious structure. Careful examination and reverse e

Summary: brute force search of the space of 4-state TM programs yielded a BB champion with an initially mysterious structure. Careful examination and reverse engineering showed that the program turns out to compute a variant of the Collatz function, where instead of C(n:odd)=3n+1, we have L(3k)=0 and L(3k+r)=L(5k+r+3). There is discussion of a "spaghetti conjecture" that BB champions are likely to be "messes" (i.e. have complete control flow graphs), but this Collatz example doesn't satisfy that criterion. Thus the author suggests that the spaghetti conjecture is false. Discussion: the whole thing is very encoding dependent, but if you figure the BB machine on N states is randomly distributed on all the N-state machines, then for the types of encodings being discussed, for large N, the flow graph has (I think) a high chance of being complete but that is not guaranteed. So that's a reason to think the conjecture is strictly false but approximately true. The BB champ being a Collatz variant is iirc a well known approach to manually constructed BB champs. That is inspired by an old result (Conway's?) found in Jeff Lagarias's book on the 3n+1 problem. It says the generalized Collatz conjecture is Pi-0-2 complete so specific instances sound like a good place to look for functions that are on the edge of undecidability. I wonder if anything is known about the arithmetic (not computational) complexity of random programs like that. I'm imaginging e.g. Shannon's theorem that most boolean functions on N inputs require exponentially many gates to compute. The analogy would be with the likelihood of functions on some parameter, expressed as N-state programs, being Pi-0-2 complete.

wizzwizz4 5y ago
> we have L(3k)=0 and L(3k+r)=L(3k+r+3) L(3k+r)=L(5k+r+3)
- throwaway81523 5y ago
  Oops, fixed.
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...
Zababa 5y ago
Thank you for that, the article is nice and your pragmatic summary goes very well with it.
Pet_Ant 5y ago
> There is discussion of a "spaghetti conjecture" that BB champions are likely to be "messes" (i.e. have complete control flow graphs) Sorry, but can someone unpack this? "complete control flow graphs"? That sounds like it means that the states are some form of Kn and that from any state you can get to any other state with the appropriate symbol.
- throwaway81523 5y ago
  Yes, that is what it means. It is described in the page linked from where the article refers to the spaghetti conjecture.

wizzwizz4 5y ago

> we have L(3k)=0 and L(3k+r)=L(3k+r+3) L(3k+r)=L(5k+r+3)

throwaway81523 5y ago
Oops, fixed.

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...

Zababa 5y ago

Thank you for that, the article is nice and your pragmatic summary goes very well with it.

Pet_Ant 5y ago

> There is discussion of a "spaghetti conjecture" that BB champions are likely to be "messes" (i.e. have complete control flow graphs) Sorry, but can someone unpack this? "complete control flow graphs"? That sounds like it means that the states are some form of Kn and that from any state you can get to any other state with the appropriate symbol.

throwaway81523 5y ago
Yes, that is what it means. It is described in the page linked from where the article refers to the spaghetti conjecture.