View source for 1RB0RE 1LC0RA 1LA1LD 1LC1LF 0LC0LB 1LE---

{{machine|1RB0RE_1LC0RA_1LA1LD_1LC1LF_0LC0LB_1LE---}}{{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}

{{TM|1RB0RE_1LC0RA_1LA1LD_1LC1LF_0LC0LB_1LE---}} is a [[BB(6)]] holdout TM analyzed by @-d on August 2025. @-d believes that this TM is probviously halting because it chooses 3 rules seemingly at random, and there is a path of 108 rules that cause the TM will halt.

== Analysis by @-d ==

Message sent on Aug 13 2025: [https://discord.com/channels/960643023006490684/1400456788955893840/1405116468168888423]
<pre>
A(n,r) = 0^inf <F 1^n r 0^inf
 n >= 2 (n <= 1 causes the tm to have setup issues)
 r is "" or starts with 0

start at A(9,"")

start from A(n,r) and simulate until the head reaches r. the config depends on n%3:
 for n%3==2, 0^inf 11 (01)^? B> r 0^inf
 for n%3==0, 0^inf 11 (01)^? 0 A> r 0^inf
 for n%3==1, 0^inf 11 (01)^? 00 E> r 0^inf
 in all 3 cases, the machine will reach a new config A(n',r')
 call these 3 changes B, A, E

B makes r shorter
A is harder to analyze. A usually makes r shorter, but sometimes makes r longer.
A can halt on certain values of r. for example, A(3,"011011011") halts.
E usually makes r longer
E can halt on certain values of r. for example, A(4,"011011") and A(4,"01011011") halt.

A(n,r) --> A(n',r') always happens, regardless of n%3. given r, the next possible r' can be found by simulating A(3k,r), A(3k+1,r), A(3k+2,r) and recording r'. do a bfs starting at r="". the bfs visited ~235000 different values of r. the shortest path to halt has length 108:
EEBBEBEEBEEEBBEBBEEBBEBEEBBEBBEEEBBEBBEBBEEBBEEEBBEBEEEBBEBBEEBBEBEEBBEBBEEEBBEBBEBBEEBBEBEEBBEBBEEEBBEBBEBE
(somehow, A was useless in the bfs. i'm not sure why.)

these configs will reach halt:
A(3^108 * k + 1975700577069254261393123959451562008800234946348086, "")
(i didn't formally prove this. it is likely to be true.)

open question: starting from A(9,""), will the config eventually become A(3^108 * k + 1975700577069254261393123959451562008800234946348086, "")?

there are 3 likely outcomes for my open question:
1. the config is impossible to reach.
2. the config is possible to reach, but the tm needs ~3^108 attempts to reach it. each attempt looks like A(n,r) --> A(~ 8n/3,r'). the config before halting will be A(~(8/3)^(3^108),?) = A(~10^10^51,?).
3. the tm halts, but in another way. i.e. the length 108 path is unused.
</pre>

Message sent on Aug 25 2025: [https://discord.com/channels/960643023006490684/1400456788955893840/1409086365244854377]

@-d has a formal proof that <math>A(3^{108} * k + 1975700577069254261393123959451562008800234946348086)</math> will halt, for all <math>k \ge 0</math>. It is in [https://github.com/int-y1/proofs/blob/1929f57df4dd7afcc11c3f458e20526fd1f991e0/BusyLean/Individual/1RB0RE_1LC0RA_1LA1LD_1LC1LF_0LC0LB_1LE---.lean#L321-L322].

<pre>
from my previous post, i gave a path of length 108 that causes the tm to halt. there might be 1057916215296 paths of length 108 that cause the tm to halt. the chance of using a length-108 path to halt is around 1057916215296/3^108 (about 10^-39). warning: the tm can still halt in another way.

A(n,*) transitions to A(~8n/3,*). it's possible that the tm is unlucky and it needs 10^39 transitions to halt.

i simulated the tm and looked at A(*,*). the 1st A(*,*) is A(9,""). i ran the simulation up to the 2728570th A(*,*) (i.e. A(~2^3861031,"0111111111111111111111111")). the tm never came close to finishing the length-108 path. the closest attempt was 21 out of 108 steps, and this happened at the 2379364th A(*,*) (i.e. A(~2^3366892,"010101101010111")).

lastly, the next k transitions for A(n,r) and A(n+3^k,r) are probably the same (i think this is true, but didn't rigorously prove this). it's worth investigating n%(3^k). i looked into the sequence of n%3, but this sequence appears statistically random. maybe someone can look into n%(3^k) more carefully.

this tm is like a lottery machine. i think it's probviously halting.

next steps:

* verify the simulation steps. does A(~2^3366892,"010101101010111") occur?
</pre>