View source for 1RB--- 0RC0RE 1RD1RF 1LE0LB 1RC0LD 1RC1RA

{{machine|1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA}}{{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}
{{TM|1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA}} is a [[probviously]] halting [[BB(6)]] [[Cryptid]] found by Racheline on 23 November 2024.

When the TM starts on any starting state, it exhibits the same probviously halting behaviour:

* When the starting state is A, the [[Tree Normal Form|TNF]] is {{TM|1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA}}.
* When the starting state is B, the TNF is not in TNF-1RB format, and can be (mostly) ignored.
* When the starting state is C, the TNF is {{TM|1RB1RD_1LC0LE_1RA0LB_1RA1RF_0RA0RC_1RE---}}.
* When the starting state is D, the TNF is {{TM|1RB0RE_1LC0RA_1LA1LD_1LC1LF_0LC0LB_1LE---}}.
* When the starting state is E, the TNF is {{TM|1RB0LC_1RC1RE_1LA0LD_0RB0RA_1RB1RF_1RD---}}.
* When the starting state is F, the TNF is {{TM|1RB1RF_1RC1RA_1LD0LE_1RB0LC_0RB0RD_1RE---}}. However, both E and F use <code>1RC</code> as the first transition, so they have the same trajectory.

There are 4 trajectories to analyze (A, C, D, and E).

== Analysis by Racheline ==

On 23 November 2024, Racheline posted an analysis ([https://discord.com/channels/960643023006490684/1239205785913790465/1309900024930635786 Discord link]) of this TM. The TM has an interesting halting mechanism.

<pre>
`1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA` is a probviously halting cryptid. just an exponential one, specifically at each step it simply multiplies the main number by 8/3 and then changes a few things depending on what it was mod 3. the left side can change in a few ways to store information between these steps. if you start from the empty left side, there are some sequences of numbers you can get mod 3 which make the TM halt, and if the main number mod 3 was random, then the probability of this eventually happening would be 1 regardless of how long those sequences are. this is all standard stuff.

however
i'm pretty sure the shortest such sequence has length around 100. i think it's a fun puzzle to try to find one yourself. the shortest one i found on my own has length 110, though it's actually a group of 2^13\*3^15 = 117546246144 such sequences because some parts can be permuted with certain restrictions. specifically, each (n,m) in the following sequence of pairs can be replaced with any sequence of n 2's and m 0's whose first k elements contain at least k/3 2's for every k<=n+m:
||(1,0), (2,1), (1,0), (2,3), (1,0), (2,4), (1,0), (2,3), (1,0), (3,5), (1,0), (3,4), (1,0), (3,3), (1,0), (2,4), (1,0), (2,3), (1,0), (3,4), (1,0), (3,6), (1,0), (2,3), (1,0), (3,4), (1,0), (3,6), (1,0)|| (spoilered because i think it's a relatively fun puzzle to try to figure out on your own)
for any given point at which the left side is empty, the probability that it will follow one of these sequences from that point is just above 1/3^87
i also ran a search on all sequences of only 0's and 2's (1's seem to always reset most of the progress you made in getting to a halting config so i ignored those) up to that length, and the shortest it found was length 107, so the only way it's less than that would be if either my code is wrong or somehow 1's manage to be useful for something other than resetting.

so i think it's pretty reasonable to guess that from a given position with empty left side, the probability that the TM will halt before resetting the left side is around 1/3^80. the rest of the computation is the same as always: the expected number of times we generate a new random number mod 3 should be around 3^80, and since that happens only when the main number is roughly multiplied by 8/3, the number of 1s when halting should be around (8/3)^3^80 ≈ 10^10^37.8, and the halting time should be around (that)^2, i.e. around 10^10^38.1
i know, not that impressive compared to the current champion, but i'm posting it because i like the mechanism. also i guess it would still be in 11th place if this approximation is correct, though the current 11th place TM takes around 10^10^35.3 steps to halt so it's kinda close.
</pre>

== Analysis by @-d ==

@-d has provided an analysis of a similar TM {{TM|1RB0RE_1LC0RA_1LA1LD_1LC1LF_0LC0LB_1LE---}} (i.e. start state D). @-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 causes the TM to halt.

Message sent on Aug 13 2025: [https://discord.com/channels/960643023006490684/1400456788955893840/1405116468168888423]
<pre>
1RB0RE_1LC0RA_1LA1LD_1LC1LF_0LC0LB_1LE---

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>
1RB0RE_1LC0RA_1LA1LD_1LC1LF_0LC0LB_1LE--- (update 2)

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>

[[Category:BB(6)]][[Category:Cryptids]]