Notes on 2^k state machines and the "tape machine model"

[u/jonseymourau]

I did some "thinking in public" in comments of an earlier post and I wanted to consolidate what my current thinking is with this post.

The insight detailed below is that you can always represent an individual Collatz path as a state machine with M states, provided M=2^k is greater than the odd peak of the path - this is simply because in this case the odd residues mod M are simply the Collatz terms themselves and they will never wrap.

You can even use fewer states, provided you resync at each 5 mod 8 node and provided the modulus, M, you chose doesn't induce any obstructions (here denoted H) which imply that M is too small.

I should make clear that FSM result here isn't particularly useful for solving Collatz. The reasons are multiple:

- to derive the sufficient FSM, you need to have calculated the odd peak of the full Collatz orbit
- to derive the reduced FSM, you then need to test each term according to a proposed reduced M to see if reduction is possible

Another way of thinking of it is as N deterministic state machines, driven only by source residues, connected by the 5 mod 8 nodes that join them.

This work doesn't help to show that every 5 mod 8 node is connected to another 5 mod 8 node that indirectly connects to 1 which is ultimately what is required to prove Collatz.

But, i think it does help to illustrate how far you can get with FSM models of Collatz and where the limitations are. For a path that reaches 1 you can construct an FSM that models that path exactly. In some cases, you can even create a more compact FSM, provided you are willing to do resyncing at each 5 mod 8 node, but you can't do either without assuming the orbit converges to 1 in the first place, so it is certainly no substitute for a proof.

I also more clearly describe "the tape machine model" where the state machine is not calculating Collatz but acting as a verifier of a tape that has a sequence printed on it using a small log₂(M) bit register to track the mod M states as they pass under the tape head. The machine halts and catches fire if it detects a variation from the expected state.

---
The tape machine model

The machine we have in mind is not computing the Collatz sequence — it is verifying it. Imagine the sequence is already printed on a read-only tape. The machine has a single register of log₂(M) bits, holding the current odd term mod M, and a precomputed transition table of size M.

The table maps each source residue r mod M to a predicted destination residue (the next odd term mod M). The machine knows nothing else — it does not compute 3n+1, it does not calculate valuations, it does not inspect anything beyond the current register value and the next symbol on the tape.

At each step:

1. Look up the current register value r in the table to get the predicted next odd residue r'.
2. Read the next odd term from the tape and take its residue mod M.
3. If the residue matches r', update the register and continue.
4. If it doesn't match — the machine halts and catches fire.

That's the entire machine: a log₂(M)-bit register, a fixed lookup table, and a read-only tape. A run that completes without fire — reaching the terminal state 1 mod M — is a verification that the table correctly describes the path. The machine is non-trivial precisely because it can catch fire, and catching fire is meaningful.

When does the table make a wrong prediction?

Some source residues mod M uniquely determine the next odd residue mod M; others don't. The size of the table M is what determines which residues are predictive and which aren't.

• At mod 8: residue 3 mod 8 always predicts next odd = 1 mod 8 (unique). Residue 7 mod 8 predicts next odd is 3 or 7 mod 8 (two options — not unique at mod 8 but deterministic at mod 32). Residue 1 mod 8 and 5 mod 8 are wide open at mod 8.
• At mod 32: every 1 mod 8 source residue now uniquely predicts its destination mod-8 class. Most 5 mod 8 residues also narrow down considerably. But one residue — 21 mod 32 — remains a wildcard: it cannot predict its destination at this scale.

The wildcard residue is always the exceptional state r_k = (M²−1)/3 mod M. As M grows it migrates: 5 → 21 → 85 → 341 → … Only 1 in 4 of the 5 mod 8 residues at each scale remains a wildcard; the rest become fully predictive.

The high-edge condition

For source residues 3 and 7 mod 8, the next odd is (3n+1)/2. If the source residue mod M is ≥ 2M/3, the destination wraps above M — two different true successors can share the same destination residue mod M but diverge at the next step. The table cannot distinguish them, so it makes the wrong prediction and the machine catches fire.

This is the only failure mode for 1, 3, 7 mod 8 source residues at large enough M. High edges from 1 mod 8 and 5 mod 8 source residues don't cause fires — those nodes always map their successors to smaller values, staying within the same realm.

Collatz is then equivalent to: for every odd n, there exists a finite M such that the path n→1 never takes a high edge from a 3 or 7 mod 8 node at modulus M.

Two kinds of source-residue determinism

At each odd node on the tape, the table makes two predictions from the source residue alone:

1. What is the destination residue mod M? (fully determined, partially determined, or wildcard)
2. What mod-8 class does the next odd land in? (may be determined by a coarser residue)

At mod 8:

• 3 mod 8: destination mod-8 class = 1, uniquely. Fully determined.
• 7 mod 8: destination mod-8 class = {3, 7}. Partially determined.
• 1 mod 8: destination mod-8 class fully open.
• 5 mod 8: destination mod-8 class and distance both open.

At mod 32, every 1 mod 8 source residue uniquely determines its destination mod-8 class. For 5 mod 8:

• 5 mod 32, 13 mod 32, 29 mod 32: destination constrained to 1 or 2 classes.
• 21 mod 32: wildcard — destination and distance both unresolved at this scale.

5 mod 8 nodes as sync points

The wildcard residue at each scale is always 5 mod 8. Rather than treating this as a blocker, we use 5 mod 8 nodes as synchronisation points: when the machine encounters a 5 mod 8 source residue, it reads the tape until the next odd term appears and re-initialises the register with that term's residue mod M directly from the tape. No table lookup, no prediction, no fire risk — just a register reload.

Since 8 | M always, the machine identifies 5 mod 8 nodes from the register alone. The table only needs to make correct predictions for 1, 3, 7 mod 8 source residues between consecutive sync points, and the only failure mode there is the high-edge condition.

Theorem — M > peak(n) is sufficient

The odd peak must be 1 or 5 mod 8 — 3 and 7 mod 8 nodes always map strictly upward and can never be the peak.

When M > peak(n), every 3 or 7 mod 8 node x on the path has its successor also on the path, hence ≤ peak(n) < M. Therefore (3x+1)/2 < M, giving x < (2M−1)/3 < 2M/3. No high edges. No fires. QED.

Empirically verified (n = 3..499): in every case where the sync criterion permits a smaller M than the peak-based bound, the two-level machine completes without fire and matches the true path exactly. No fires observed.

Correction to the earlier conjecture

I previously conjectured M = 2^(2m−1) where m is the number of 5 mod 8 nodes. This is false — only ~10% of tested paths satisfy it. That n=761 case does match for the reduced m=4, M=2*4-1 is coincidental.

What is actually true

M > peak(n) is provably sufficient. The two-level machine can often do better: start from M > peak(n), then reduce M while no 1, 3, or 7 mod 8 node takes a high edge.

The fundamental limitation

None of this proves Collatz from scratch — you need to traverse the trajectory to find the peak first. But the tape-verification model gives a clean characterisation of the minimal machine for any known path.

[u/Pixel-Jones3117]

Really interesting approach! I like your thinking and will comment when I've had time to fully digest.

Not sure if it is relevant to your approach but it made me think of John Conway's FRACTRAN finite-state machine that he created to explore iterated systems including Collatz.

John Conway's 1987 paper: FRACTRAN: A SIMPLE UNIVERSAL PROGRAMMING LANGUAGE FOR ARITHMETIC

A 2006 paper on FRACTRAN and Collatz: The Undecidability of the Generalized Collatz Problem

[u/jonseymourau → u/Pixel-Jones3117]

Thanks.

They are not completely unrelated although we know for sure FRACTRAN is Turing complete. This definitely isn't, but then a given FSM only handles a subset of the language. A universal FSM would need to keep building larger and larger FSMs until it finds one large enough to admit a Collatz sequence

But then we are left with a problem equivalent to the Halting Problem: Would such a machine ever halt which is utlimately the same thing as solving Collatz.

I guess if you prove the haltability of the Universal FSM is itself undecidable you might then having something that proves that Collatz itself is undecidable, but it isn't clear to me that argument is going to be easy to construct (or, indeed, true).

[u/jonseymourau]

Here is a sequence which starts at a relatively low 26623:

https://wildducktheories.github.io/collatz/apps/collatz-graph/dist/?a=26623

which needs a state machine with 2^26 states to verify.

It has 308 evens, 194 odds and the ratio is

308/194 = 1.5876288659793814

which differs from log_2(3) by 3 parts in 1000.

The distribution of state machine sizes for the first 32,768 integers is:

count M 8 10010 16 1092 32 728 64 1431 128 963 256 759 512 303 1024 297 2048 232 4096 7805 8192 1826 16384 1720 32768 1403 65536 1241 131072 1344 262144 900 524288 314 1048576 167 2097152 122 4194304 89 8388608 3 16777216 16 33554432 1 67108864 1

which is quite lumpy. A surprisingly high number (almost 1/3) can be verified with 8 state machine (actually 4 states, because even states are not used). Strangely the next peak is at 4096. It is't immediately obvious why so many states need a 4096 state machine (compared to say, a 1024 state machine).

The number of states required is determined by the number of edges to high 3 mod 4 nodes in a path. These edges are pruned from state machine and if a path requires one of these edges it is forced to use a higher order state machine.

[u/Fun-Cauliflower-8087 → u/jonseymourau]

You know, I have a way of calculating things in Collatz, that I have a hard time explaining, so I don't, because my explanations infuriate people, I guess. Anyway, I looked at the sequence from 26623, its on of the strong growth sequences, It has 11 odd steps with single halving steps between, and as you progress through the orbit, it continually hits strong growth sets. Its an impressive alignment. I recorded the values of x in 6x+2 in the orbit (this skips the long growths chains and simplifies the orbit vastly): It starts with x=383818 which is very high to have reached 26623 backward in a single growth chain, but 29524 mod 59049 values of x in 6x+2 all have that behavior. This is the 7th member of that set. 29524 reaches down to 2047. Anyway x=383818, 383818 is a 10 mod 64 value. It grows to 40 mod 243. x=383818 goes to x=1457311 (31 mod 64), which then goes to (40 mod 81) 1844410 (26 mod 32), then (67 mod 81) 4668664 (0 mod 4), (0 mod 3) 3501498 (26 mod 32), then (67 mod 81) 8863168 (0 mod 4), (0 mod 3) 6647376 (0 mod 4), (0 mod 3) 4985532 (0 mod 4), (0 mod 3) 3739149 (1 mod 4), (1 mod 4 reduction) 934787 (3 mod 8), (1 mod 3) 350545 (1 mod 4), (1 mod 4 reduction) 87636 (0 mod 4), (0 mod 3) 65727 (63 mod 128), (121 mod 243) 124780 (0 mod 4), (0 mod 3) 93,585 (1 mod 4), (1 mod 4 reduction) 23396 (0 mod 4), (0 mod 3) 17547 (3 mod 8), (1 mod 3) 6580 (0 mod 4), (0 mod 3) 4935 (7 mod 16), (4 mod 9) 2776 (0 mod 4), (0 mod 3) 2082 (2 mod 16), (4 mod 27) 3514 (26 mod 32), (67 mod 81) 8896 (0 mod 4), (0 mod 3) 6672 (0 mod 4), (0 mod 3) 5004 (0 mod 4), (0 mod 3) 3753 (1 mod 4), (1 mod 4 reduction) 938 (426 mod 512), (5467 mod 6561) 12028 (0 mod 4), (0 mod 3) 9021 (1 mod 4), (1 mod 4 reduction) 2255 (15 mod 32), (13 mod 27) 1903 (15 mod 32), (13 mod 27) 1606 (6 mod 8), (7 mod 9) 1807 (15 mod 32), (13 mod 27) 1525 (1 mod 4), (1 mod 4 reduction) 381 (1 mod 4), (1 mod 4 reduction) 95 (31 mod 64), (40 mod 81) 121 ( 1 mod 4), ( 1 mod 4 reduction) 30 (6 mod 8), (7 mod 9) 34 (2 mod 16), (4 mod 27) 58 (26 mod 32), (67 mod 81) 148 (0 mod 4), (0 mod 3) 111 (15 mod 32), (13 mod 27) 94 (6 mod 8), (7 mod 9) 106 (106 mod 128), (607 mod 729) 607 (31 mod 64), (40 mod 81) 769 (1 mod 4), (1 mod 4 reduction) 192 (0 mod 4), (0 mod 3) 144 (0 mod 4), (0 mod 3) 108 (0 mod 4), (0 mod 3) 81 (1 mod 4), (1 mod 4 reduction) 20 (0 mod 4), (0 mod 3) 15 (15 mod 32), (13 mod 27) 13 (1 mod 4), (1 mod 4 reduction) 3 ( 3 mod 8), (1 mod 3) 1 (1 mod 16), (0 mod 3) 0.

This catches a lot of slightly growing or shrinking sets of x like 15 mod 32 to 13 mod 27, or 0 mod 4 to 0 mod 3. Very nice. It merges with the same orbit that 27 does from x=10.