Busy Beaver and Collatz

General
1

Consider the Collatz-like function:

\begin{array}{l} H(2k) & = & 3k \\ H(2k+1) & = & 3k+1 \\ \end{array}

aka

H(n) = n + \lfloor \frac{n}{2} \rfloor

aka

H(n) = \begin{cases} \frac{3n}{2}&\text{if }n\equiv0\pmod{2},\\ \frac{3n-1}{2}&\text{if }n\equiv1\pmod{2}.\\ \end{cases}

Start at 8 and repeatedly apply H keeping a running total for number of times the number was odd or even. Will you ever reach a point where (the running count of odd numbers) > 2x (the running count of even numbers)?

This problem is simulated by a specific 6-state Turing Machine (called Antihydra) when run on a blank tape and we must solve this problem in order to decide if it will ever halt.

We at bbchallenge recently solved the 5-state Busy Beaver problem. But in order to move on to the 6-state BB problem, we would need to solve Collatz-like problems like this.

Does anyone have any ideas on how to make any sort of progress on this? It seems that it is simpler than the classic Collatz conjecture since all we care about is one single trajectory. But, like the 5x+1 divergent trajectories, this one trajectory is also presumably divergent (non halting) and so it requires showing that the sequence will never have some property across infinite iterations.

Considering this problem probabilistically it is like a random walk. It starts at 0, every time you reach an even number move +2, every time odd, -1. For these sorts of biased random walks, there is an exponentially decaying probability of coming back to 0 from further and further away. We’ve simulated this long enough that the random walk is >1 billion and thus the chance of ever reaching 0 is negligible in this random model. But, of course, that doesn’t prove anything about a single (deterministic) trajectory.

For more details, see: BB(6) is Hard (Antihydra) | sligocki

3 Likes
2

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:

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

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

  1. Another idea, try to find the Antihydra’s sequence of evens and odds somewhere else in the natural computational universe.
1 Like
3

Oh, interesting, aside from the (521n+2) case that Collatz-like rule doesn’t even look toooo contrived :slight_smile:

We call H the Hydra function. Antihydra is the 6-state, 2-symbol TM that simulates it starting from 8 with the 2x more odds than evens halt condition. Hydra is a 2-state, 5-symbol TM that simulates it starting from 3 with the opposite (2x more evens than odds) halting condition.

The Hydra sequence is on OEIS: A061418 - OEIS (starting from 2 (H(2) = 3)) and parities are in A356556 - OEIS where they note it is related to the Josephus problem. The halting condition for Hydra is closely related to this sequence, basically you want to create a new sequence of partial sums of this:

D(n) = \sum_{k=2}^{n+1} A356556(k)

and then the question is: Does there exists an N such that D(N) < N/3?

(Note: The k=2 to n+1 is to “correct” for the fact that A356556 starts from 2 rather than 3. And all these sequences are 1-indexed meaning the first value is A356556(1) and D(1) respectively)

4

One interesting result we know of is that these parity sequences are not Sturmian due to:

Dubickas A. On Integer Sequences Generated by Linear Maps. Glasgow Mathematical Journal . 2009; 51(2): 243-252. doi:10.1017/S0017089508004655

AFAICT, Sturmian sequences are basically sequences that aren’t periodic, but “almost” are.

5

@sligocki Just seems like a typo, but I believe the map should look like

H(n) = \begin{cases} \frac{3n}{2} \quad\quad\quad\quad\quad \text{if } n \equiv 0 \; (\text{mod } 2) \\ \frac{3(n-1)}{2} + 1 \quad\quad \text{if } n \equiv 1 \; (\text{mod } 2) \end{cases}

Edit: actually, I’m probably wrong here, for some reason the first few numbers I tested didn’t work between the two original versions. However the two maps with braces are identical so the proof below will work for both.

Anyhow, this is a simple one to show that diverges always except at the cycle n=1 for all positive inputs of n.

Let n > 1, we show that every n iterates to a larger value

Case 1: n\equiv 0 \text{ (mod } 2)

\frac{3n}{2} > n

Case 2: Proof by induction for n \equiv 1 \text{ (mod } 2)

Base case, n_0 = 3
\frac{3(\mathbf{3-1)}}{2}+1 = 4 > n_0

Induction let k \equiv 1 \text{ (mod 2)} and k iterates to a larger number, then we induct on k + 2
Assume: \frac{3(k-1)}{2}+1 > k
Induction: \frac{3(k+2-1)}{2}+1 = \frac{3(k+1)}{2}+1
Need to show: \frac{3(k+1)}{2}+1 > k + 2 \xrightarrow{\text{subtact 1 both sides}} \frac{3(k+1)}{2}> k + 1 which is true
Therefore all k \equiv 1 \text{ (mod 2)} iterate to a larger number

Therefore every number iterates to a larger number. I suppose the real question for solving Antihydra is specifically are there more odd iterations than even, which I’m fairly certain is an undecidable question in general as you would be asking a question about the states visited during a run, which is a small twist to the halting problem.

Btw, the reason such a proof as above wouldn’t work for the 5x+1 collatz variant is the mixing of the even iterations going to a lower value and the odd iterations going to a higher value, when they are both in the same direction, it almost certainly can always be shown* to always diverge/converge (such as in the x+1 version which always converges)

  • *by “always diverge/converge”, this should be taken as excluding any cycles, only the direction of generally increasing/decreasing should be considered

Back to the question of odd vs even counts, I do have a generalized method to showing this but it can only be used for converging problems as those always end up in cycles. Since they end up in cycles, counting the odd/evens is doable as it repeats forever with a pattern. With (most) diverging problems, they go on infinitely without any repetition so there is no pattern to find. An example of a diverging problem with a diverging cyclic pattern is

C(n) = \begin{cases} \frac{n}{2} \;\;\;\quad\quad\quad \text{if } n \equiv 0 \; (\text{mod } 2) \\ n + 2 \quad\quad \text{if } n \equiv 1 \; (\text{mod } 2) \end{cases}

where all odds iterate to another odd. In parity terms, the trivial diverging problem above has parity 1^\infty at all odd values, where as in the non-trivial diverging problems the parities at no point can use the \infty symbol.

6

Id be looking at combinatoric algebra, and drawing implications from identities implied by the systems behaviour, 2 i notice are

(2^n)Ă—(1.5^n)=3^n
Also…

4(NĂ—3-1)=3(NĂ—4-1)-1

7

Yes, the Hydra sequences always “diverge” in the sense that for all n \ge 2, H(n) > n so this problem is a bit different than the classic Collatz conjecture. In this case it’s all about the properties of the parity sequence! And specifically, the chance of that parity sequence becoming sufficiently far from balanced.

In this sense, I think it actually is very closely related again to the classic Collatz conjecture and 5n+1 problem. Specifically, showing that no number diverges in 3n+1 requires showing that it’s parity sequence remains sufficiently unbalanced forever (way more odds than evens) otherwise it would be bounded).

Similarly, proving that 7 diverges in the 5n+1 problem requires proving that the parity sequence remains mostly balanced forever (if there were enough more even than odd terms at some point, that would force the trajectory to go below 7 (and thus converge to a cycle)).

1 Like
8

@Fumblingnumbers can you help me understand why that second equation is useful? I understand the first: H^n(2^n) = 3^n and we have a similar equation for a long sequence of odds H^n(2^n + 1) = 3^n + 1. But not quite sure how to interpret your equation 4(3N - 1) = 3(4N - 1) - 1.

9

Yes, i havnt put to much thought into this yet, but the equation demonstrates that for any odd number N there is an infinate sequence of other odd numbers (iterate NĂ—4-1) that will guarantee even numbers when following the (Ă—3-1)Ă·2 rule. Also when iterating Ă—4-1 from any odd number youll notice you get a repeating pattern of multiples of 3 every 3 iterations (from the first multiple of 3) this is related as the previous identity shows multiples of 3 is where your even numbers Ă—1.5 merge to.interesting to me, and maybe only me i use nĂ—3-1 in my sequential analysis of the collatz conjecture.it converts the sequential position (s) of any odd (n) so that sĂ—3-1= (nĂ—3+1)Ă·2 https://youtu.be/A0ycHyLrT6s?si=tqzp3rEDZBMMaaG6

Also i converted collatz odd number too odd number movements into this chart, which i believe represents one of these halting problems.(the chart can never be big enough to ablige ots own instructions, but note the pattern https://youtube.com/shorts/yjDXxNzhwf8?si=TxCB_fq7w141UeIO

Theres another identity that shows the same implication in collatz, that is to say that for any base of any exponential fall, there are an infinate sequence of odd numbers that fall to the same base.
4(nĂ—3+1)=3(nĂ—4+1)+1

10

I probably wasn’t clear enough sorry, there is a way to figure out the parity sequence balance for any infinite sequence that is cyclic, but I’m fairly certain it is unsolvable for those that diverge. Hence, since every number including 8 diverges, there is likely no way to solve this in a general sense.

Edit, I’d like to add that it only has to be eventually cyclic for the above to be true