cosmo
September 26, 2022, 7:49pm
1
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
jwg4
November 5, 2023, 11:24pm
3
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
jwg4
November 5, 2023, 11:48pm
5
Thanks very much! Will look at that tool.