Halting Collatz-like machine

Pointed out by @savask on discord, the following machine https://bbchallenge.org/1LC1RA_---0RA_1RD0LA_1LC1RE_1RD0RB (or https://bbchallenge.org/1RB1LA_1LC0RA_1RB1LD_1LC0LE_---0LA in bbchallenge’s reordering of the states and L/R symmetrization) does halt (hence it is not in the seed database) and is marked “Collatz-like” by Skelet’s program.

It would be interesting to analyse its behavior to understand why it is Collatz like.

Let C(a, b) = 0^inf 1^a <C 1^b 0^inf,

It looks like this TM satisfies the following rules (this is a quick-and-dirty analysis and might be slightly off):

C(a + 4, b) -> C(a + 1, b + 4)
C(1, b) -> C(b+2, 3)
C(2, b) -> Halt(b+2)
C(3, b) -> C(b+1, 7)

or in Collatz form:

C(3k+1, b) -> C(4k+b+2, 3)
C(3k+2, b) -> Halt(4k+b+2)
C(3k+3, b) -> C(4k+b+1, 7)

And the orbit from blank tape (starting at step 8) is:

C(3, 3) -> C(4, 7) -> C(13, 3) -> C(21, 3) -> C(28, 7)
 -> C(45, 3) -> C(60, 7) -> C(84, 7) -> C(116, 7) -> Halt(161)

As with many of these effective Collatz machines, it gets very “lucky” and avoids hitting the 3k+2 transition for longer than “expected” after 9 transitions. If it was randomly choosing a transition each time, you’d expect it to hit 3k+2 in about 3 transitions.

1 Like