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

How many steps does it take to halt?

Shawn’s program gives the below final config, step count, and nonzero tape symbol count:

[justinb@husk busy-beaver]$ pypy3 Code/Quick_Sim.py <(echo 1LC1RA_---0RA_1RD0LA_1LC1RE_1RD0RB)

Transition table:

       +-----+-----+
       |  0  |  1  |
   +---+-----+-----+
   | A | 1LC | 1RA |
   +---+-----+-----+
   | B | --- | 0RA |
   +---+-----+-----+
   | C | 1RD | 0LA |
   +---+-----+-----+
   | D | 1LC | 1RE |
   +---+-----+-----+
   | E | 1RD | 0RB |
   +---+-----+-----+


BF: Searching for optimal block size
BF: Least compressed tape at step 44 : 11011110111
BF: Optimal tape compression block size 1 tape size 6
BF: Searching for optimal mult for block size 1

         Steps:                     Times Applied:
Total:                                           0
Macro:                                           0
Chain:                                           0
Rule:                                            0
Rules proven: 0
Failed proofs: 0
Prover num past configs: 0
Tape copies: 0
Elapsed time: 0.0026869773864746094
0^inf (0) A> 0^inf
Num Nonzeros:   0

         Steps:                     Times Applied:
Total:   10^4.3                                195
Macro:   10^2.3                                162
Chain:   10^3.4                                 26
Rule:    10^4.3                                  7
Rules proven: 1
Failed proofs: 0
Prover num past configs: 2
Tape copies: 24
Elapsed time: 0.21816611289978027
0^inf 1^160 0^1 (1) Z> 0^inf
Num Nonzeros: 10^2.2  161

Turing Machine reached Undefined transition
State:  1
Symbol: 0

Steps:    20711
Nonzeros: 161
1 Like

Thanks very much! Will look at that tool.