View source for 1RB--- 0RC0RD 1LD1RB 0LE0LC 1RA0LF 1LD1LE

{{machine|1RB---_0RC0RD_1LD1RB_0LE0LC_1RA0LF_1LD1LE}}{{TM|1RB---_0RC0RD_1LD1RB_0LE0LC_1RA0LF_1LD1LE}} appears to be a chaotic [[probviously]] halting [[BB(6)]] TM, but with no estimate for halting time. It is still under analysis as of 24 Apr 2026.

== Analysis by Shawn Ligocki ==
https://discord.com/channels/960643023006490684/1239205785913790465/1497001816741646407

Low level rules:
<pre>
1RB---_0RC0RD_1LD1RB_0LE0LC_1RA0LF_1LD1LE

Let A(a,b,c) = 0^inf 1^a 10^b C> 1^c 0^inf

A(a+1,b,c+3) --> A(a,b+2,c)

A(a,b,0) --> A(2b+1,1,a+1)
A(a,b,1) --> A(2b+3,1,a+1)
A(a,b,2) --> A(2b+5,1,a+1)

A(0,b,c+5) --> A(2b+4,2,c)
A(0,b,4) --> Halt
A(0,b,3) --> Halt

Start: A(0,1,0)
</pre>

High level rules:<pre>if a ≥ floor(c/3):
  A(a, b, 3k)    -->  A(4k+2b+1, 1, a-k+1)    X -> X+4
  A(a, b, 3k+1)  -->  A(4k+2b+3, 1, a-k+1)    X -> X+5
  A(a, b, 3k+2)  -->  A(4k+2b+5, 1, a-k+1)    X -> X+6
if a < floor(c/3):
  A(k, b, 3k+3)  -->  Halt
  A(k, b, 3k+4)  -->  Halt
  A(k, b, 3k+5+c)  -->  A(4k+2b+4, 2, c)      X -> X+3

with X=a+2b+c</pre>where <math>X = a+2b+c</math> is a sort of norm on these configs that we can see grows only linearly.

Simulated out to 1.5T high level rules:
<pre>
    1_000_000_000  A(    1_449_166_375,  1,     3_050_820_388)
   10_000_000_000  A(   39_348_725_977,  1,     5_651_355_297)
  100_000_000_000  A(  150_379_323_247,  1,   299_620_772_649)
  500_000_000_000  A(2_123_188_460_901,  1,   126_811_502_474)
1_000_000_000_000  A(2_018_953_178_979,  1, 2_481_046_137_608)
1_500_000_000_000  A(  415_020_273_351,  1, 6_334_978_834_030)
</pre>
=== Probabilistic Model ===
[[File:Tent Distr 5B.png|thumb|Distribution of ''r'' values over the first 5B steps (1000 buckets).]]
[[File:Skewed tent map.png|thumb|Map governing update of ''r'' stat in the limit. It is a Skewed or [[wikipedia:Tent_map#Asymmetric_tent_map|Asymmetric Tent Map]].]]
Consider <math>r = \frac{a}{a+c}</math>. This value seems empirically to be be extremely uniform on the range [0,1]. And for large values of a,c there is a clear reason why: The update function is a [[wikipedia:Tent_map#Asymmetric_tent_map|Skewed Tent Map]], a map which is known to have long-run time average distribution completely uniform.

If we assume that this sequence has (pseudo-)random uniform distribution, then we can calculate an exact probability of halting. Let <math>S = a+c</math> and consider at each step that the model has a fixed value of S and b, but the value of ''a'' (and consequently also ''c'') are chosen uniformly at random. If S = 4k+3, there is exactly 1/S choices that will lead to halt: A(k, b, 3k+3). The same is true for S = 4k+4. But for S = 4k+{0,1}, all choices must reset (hit a non-halt rule). Assuming that S is equally likely to have each remainder, we can say that there is a <math>\frac{1}{2S}</math> chance of halting at each high level rule. We can see above that X grows linearly with each rule application, the same is true for S since <math>b \in \{1,2\}</math>. Thus <math>\sum_t \frac{1}{2S(t)} \to \infty</math> and thus <math>P(\text{never halt}) = \prod_t \left( 1 - \frac{1}{2S(t)} \right) = 0</math>. In other words, this random model is guaranteed to eventually halt.

This model supports a survival function <math>V(T) = \prod_{t=0}^T \left( 1 - \frac{1}{2(S_0 + \mu t)} \right) </math> for <math>\mu \approx 4.5 </math> the average increase in S per step. With a bit of approximation you can get <math>V(t) \approx \left( 1 + \frac{\mu t}{S_0} \right)^{-\frac{1}{2\mu}} </math> and solving for ''t'' (to find the time when only P = V(t) have survived) you get <math>t(P) = \frac{S_0}{\mu} (P^{2\mu} - 1) </math>, if you further assume that <math>S_0 \approx N\mu </math> (the sim started from S=0, and after N steps was at <math>N\mu </math>), then you see that the median halting time (given that you have already simulated for N steps without halt) is 512N.

I (Shawn) simulated starting from all a,c such that S=a+c=2048 (and all <math>b \in \{1,2\} </math> and there were the empirical survival rates:<pre>S=2048: 4098 configs, 2264 halted within 20_000_000 steps

Survival at multiples of S:
  step 2_048: 3491/4098 (85.2%)
  step 4_096: 3407/4098 (83.1%)
  step 8_192: 3205/4098 (78.2%)
  step 16_384: 3205/4098 (78.2%)
  step 32_768: 2704/4098 (66.0%)
  step 65_536: 2704/4098 (66.0%)
  step 131_072: 2350/4098 (57.3%)
  step 262_144: 2235/4098 (54.5%)
  step 524_288: 2070/4098 (50.5%)
  step 1_048_576: 2070/4098 (50.5%)
  step 2_097_152: 2070/4098 (50.5%)
  step 4_194_304: 1834/4098 (44.8%)
  step 8_388_608: 1834/4098 (44.8%)
  step 16_777_216: 1834/4098 (44.8%)</pre>These seem to roughly match the model which expects that the median halting time would have been 1,048,576.
[[Category:BB(6)]]