I’d be interested in what others have to say. The Busy Beaver project is amazing; anyone who hasn’t should definitely check it out!
My two cents:
- The “Antihydra non-halting conjecture” sounds just as hard as the “5n+1 diverges on 7” conjecture, or the “Conway rule diverges on 8” conjecture.
All kinda seem easier than the Collatz conjecture, because they’re about single trajectories rather than all trajectories … though maybe cracking a single trajectory would answer the whole thing.
I guess something could go awry in Antihydra after zillions of steps, like how \pi(x) > li(x) only at some very large, unsimulatable x. But in the latter case, the heuristics said it should happen eventually (confirmed with proof), whereas for Antihydra, the heuristics say it shouldn’t happen (not yet confirmed with proof).
- It seems like Antihydra shouldn’t have enough “information” (loosely) to suddenly reverse course way down the road. But I guess the scratch-space of the TM lets it record so much stuff. Consider this Collatz-like rule:
(1 n + 0) / 5 when n \equiv 0 (mod 5)
(2 n + 3) / 5 when n \equiv 1 (mod 5)
(3 n + 4) / 5 when n \equiv 2 (mod 5)
(521 n + 2) / 5 when n \equiv 3 (mod 5)
(1 n + 1) / 5 when n \equiv 4 (mod 5)
3’s trajectory goes like
3 - 313 - 32,615 - 6523 - 679,697 - 407,819 - 81,564 - 16,313 - 1,699,815 - 339,963 - 35,424,145 - 7,084,829 - 1,416,966 - 566,787 - 340,073 - 35,435,607 - 21,261,365 - 4,252,273 - 443,086,847 - 265,852,109 - 53,170,422 - 31,902,254 - 6,380,451 - 2,552,181 - 1,020,873 - 106,374,967 - 63,824,981 - 25,529,993 - 2,660,225,271 - 1,064,090,109 - 212,818,022 - 127,690,814 - 25,538,163 - 2,661,076,585 - 532,215,317 - 319,329,191 - 127,731,677 - 76,639,007 - 45,983,405 - 9,196,681 - 3,678,673 - 383,317,727 - 229,990,637 - 137,994,383 - 14,379,014,709 - …
which looks like it’s diverging, but if you keep going, nope, it’s a loop:
… - 2,875,802,942 - 1,725,481,766 - 690,192,707 - 414,115,625 - 82,823,125 - 16,564,625 - 3,312,925 - 662,585 - 132,517 - 79,511 - 31,805 - 6361 - 2545 - 509 - 102 - 62 - 38 - 3960 - 792 - 476 - 191 - 77 - 47 - 29 - 6 - 3
The Matthews-Watts heuristic correctly predicts, for this rule, that almost all start numbers should diverge (because the heuristic notes that 1 \cdot 2 \cdot 3 \cdot 521 \cdot 1 > 5^5). But the rule is “barely diverging” (3126 > 3125), so tons of human-sized numbers like 3 get snared in loops, unlike the 5n+1 rule (5 > 4) or Antihydra (9 > 4).
It might be possible to build a larger rule that induces some really vast divergent-looking trajectory that turns out to be a loop in the end, after some almost-unsimulatable number of steps?
- Another idea, try to find the Antihydra’s sequence of evens and odds somewhere else in the natural computational universe.