1RB1RE 1LC0RA 0RD1LB ---1RC 1LF1RE 0LB0LE

Unsolved problem:

Does this TM run forever?

1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE (bbch)

A BB(6) TM which is modeled by

A(a, b) -> A(a-b, 4b+2) if a > b
A(a, b) -> A(2a+1, b-a) if a < b
A(a, b) -> Halt if a = b

Start A(1, 2)

for A(a, b) = 0^inf 10^{a-1} 0 1^b E> 0^inf. The configuration is always valid because $a\geq 1$ is always maintained. It is a possible Cryptid since it seems hard to predict whether we could ever end up in A(n, n), but investigations are ongoing on Discord as of 27 Jun 2024.

Analysis from Discord

@-d 25 Jun 2024 2:29 AM ET:

Let f(a,b) represent (10)^a D> 1^b. By inspection, the machine visits f(0,3) f(2,2) f(1,7) f(4,5) f(0,19) f(2,18) f(6,15) f(14,8).

I got these rules for f(a,b) and verified them up to 0<=a<=100 and 1<=b<=100.
f(a,b) -> f(a-b+1,4b-1) if b < a+2
f(a,a+2) -> halt
f(a,b) -> f(2a+2,b-a-1) if b > a+2


I ran these rules from f(0,3) and gave up after reaching a,b > 2^1000000. It looks like halting becomes less and less likely. Is there a way to show this runs forever (or miraculously halts)?

@Shawn Ligocki — 25 Jun 2024 at 11:56 PM ET:

I can confirm roughly the same rules (I chose a slightly different standard config):
1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE

E(a, b, c)  =  0^inf 10^a 0 10^b 1^c E> 0^inf

Base Rules:
  E(a+1, b, c+2) -> E(a, b+2, c+1)
  E(a+1, b, 1)   -> E(a, 0, 2b+6)
  E(0,   b, c+2) -> E(b+2, 0, c+1)
  E(0,   b, 1)   -> Halt(b+4)

High-level Rules:
  E(a, 0, c+1)  -->  E(a-c-1, 0, 4c+6)  if a > c
  E(a, 0, c+1)  -->  E(2a+2, 0, c-a)    if a < c
  E(a, 0, c+1)  -->  Halt(2c+4)         if a = c


Connecting to your notation @-d : f(a, b+2) -> E(a, 0, b+1) 

@Shawn Ligocki — 26 Jun 2024 at 12:25 AM

Hm, this is interesting. I decided to track "spread" akin to what @savask and I have been looking at for the similar 3x3 TM we're looking at in ⁠bbxy . Here I define spread = abs(a - c) in config E1(a, c) = E(a, 0, c+1). Here's the results I have so far:
          1  E1(2, 0) spread: [2, 2] (0.06s)
    100_001  E1(10^6_557, 10^6_555) spread: [1, 10^6_557] (0.44s)
    200_001  E1(10^13_124, 10^13_125) spread: [10^6_557, 10^13_125] (1.27s)
    300_001  E1(10^19_670, 10^19_669) spread: [10^13_123, 10^19_670] (2.52s)
    400_001  E1(10^26_235, 10^26_237) spread: [10^19_668, 10^26_237] (4.23s)
    500_001  E1(10^32_799, 10^32_799) spread: [10^26_235, 10^32_799] (6.39s)
    600_001  E1(10^39_350, 10^39_352) spread: [10^32_799, 10^39_352] (8.98s)
    700_001  E1(10^45_930, 10^45_930) spread: [10^39_350, 10^45_930] (12.06s)
    800_001  E1(10^52_486, 10^52_486) spread: [10^45_929, 10^52_486] (15.54s)
    900_001  E1(10^59_046, 10^59_047) spread: [10^52_485, 10^59_047] (19.57s)
  1_000_001  E1(10^65_613, 10^65_612) spread: [10^59_045, 10^65_613] (24.05s)
  1_100_001  E1(10^72_154, 10^72_153) spread: [10^65_609, 10^72_154] (28.92s)
  1_200_001  E1(10^78_728, 10^78_729) spread: [10^72_153, 10^78_729] (34.21s)
  1_300_001  E1(10^85_288, 10^85_289) spread: [10^78_729, 10^85_289] (40.03s)
  1_400_001  E1(10^91_830, 10^91_829) spread: [10^85_288, 10^91_829] (46.40s)
  1_500_001  E1(10^98_394, 10^98_393) spread: [10^91_829, 10^98_394] (53.11s)
  1_600_001  E1(10^104_961, 10^104_959) spread: [10^98_393, 10^104_961] (60.18s)
  1_700_001  E1(10^111_523, 10^111_523) spread: [10^104_958, 10^111_523] (67.75s)
  1_800_001  E1(10^118_088, 10^118_088) spread: [10^111_523, 10^118_088] (75.77s)
  1_900_001  E1(10^124_631, 10^124_630) spread: [10^118_088, 10^124_631] (84.39s)
  2_000_001  E1(10^131_185, 10^131_185) spread: [10^124_630, 10^131_185] (93.41s)
...
  3_000_001  E1(10^196_733, 10^196_733) spread: [10^190_163, 10^196_733] (217.87s)

Here spread: [X, Y] means that the spread values (since last print) had min X, max Y
So notice that the spread is basically uniformly increasing. In fact these [X, Y] intervals hardly even overlap!
That makes me think there's something about this that makes small spread impossible (and thus halt impossible)
Or that it's like Bigfoot and it ... could go back to zero, but the chances are infinitesimal!

savask — 26 Jun 2024 at 1:02 AM

Maybe we can simplify a little bit more. Set (a, c) = E(a, 0, c+1) then the rules are
(a, c) -> (a-c-1, 4c+5) if a > c
(a, c) -> (2a+2, c-a-1) if a < c
(a, c) -> Halt if a = c

I like that this way they are more symmetrical with a-c-1 vs c-a-1

Shawn Ligocki — 26 Jun 2024 at 2:33 AM

FWIW, there is a value x ~= 1.76 such that as c -> inf: (xc, c) -> (xyc, yc) via path "rll" (right->0 [ie a > c], left->0 [ie a < c], left->0). Which would repeat forever if it were exact, but it is an unstable cycle so any slight deviation and it gets further and further away, so that doesn't seem like a reasonable proof direction :/

dyuan01 — 26 Jun 2024 at 2:32 PM

If we let A(a, c) = (a-1, c-1), we can get these rules:
```
A(a, c) -> A(a-c, 4c+2) if a > c
A(a, c) -> A(2a+1, c-a) if a < c
A(a, c) -> Halt if a = c
```
And we start with (1, 2)

I'm not sure if it even helps, but at least the rules look slightly more "human-manageable"