View source for 1RB1LA 1LC0RE 1LF1LD 0RB0LA 1RC1RE ---0LD


{{machine|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}}{{unsolved|Does this TM run forever?}}
{{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}} is a [[probviously]] non-halting [[BB(6)]] [[Cryptid]] first discovered and analyzed by @mxdys on [https://discord.com/channels/960643023006490684/1239205785913790465/1326911501357023296 9 Jan 2025]. Mxdys derived the lower level rules, and Racheline and Katelyn Doucette independently derived the higher level rules later on.

Determining whether this machine halts requires proving that a highly chaotically growing sequence never intersects with a value equal to <math>2^n</math>. It is believed to be a [[Cryptid]], because proving this seems to require a deep understanding of how addition of two integers affects the number of factors of 2 in the sum, and/or much stronger ways of characterizing when two sequences can share terms in common. Both of which are believed to be out of reach of current mathematics.

This machine is named "Space Needle", and it is the [[Beaver Math Olympiad#Unsolved problems|BMO's 6th problem.]]

== Analysis ==
=== Low Level Rules ===
The original reported low level rules derived by @mxdys:

<pre>
1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD

start: (3,1)
(0,2+c) --> (4+c,1)
(1,c) --> halt
(2+2b,c) --> (7+5b+c,1)
(3+2b,c) --> (b,4+b+c)

(b,c) := 0^inf <A 1^b 00 1^c 0^inf
</pre>

Or the following rewritten form by Andrew Ducharme:

<pre>
start: (3,1)
(1,c) --> halt
(2b,c) --> (2+5b+c,1)
(2b+1,c) --> (b-1,3+b+c)

(b,c) := 0^inf <A 1^b 00 1^c 0^inf
</pre>

=== Higher Level Rules ===
Further derivation and analysis of the higher level rules took place on [https://discord.com/channels/960643023006490684/1400226828396003480 July 31 2025]<br>
The low level rules can be abstracted up a level by noticing that the c parameter always gets set to a consistent starting value of 1 when the rule triggered by b being even is encountered. It's possible to, through induction, generate a mapping from each <math>(b_n, 1)</math> to the next <math>(b_{n+1}, 1)</math>. This allows one to completely eliminate the c parameter and have a set of rules entirely dependent on the value of b.

[https://discord.com/channels/960643023006490684/1400226828396003480/1400226828396003480 Rules derived by Katelyn Doucette:]
<pre>
Let v(b) denote the largest power of 2 that divides b.

START: b = 6

If b = 2^v(b):
    HALT
else:
    b --> b + v(b) + 3/2 * (b/2^v(b) - 1)
</pre>

Important to note, the actual machine seems to work with an alternative formulation of the above rules where b and its halting problem are shifted down by 3. The version with b shifted up by 3 is shown instead due to stylistic reasons, as well as improved computation speed.

== Trajectory ==
At a high level, the machine's halting problem is governed by a highly chaotically growing sequence. The first few terms of the sequence are:
<math display="block">\begin{array}{|c|}\hline 6 \rightarrow 10 \rightarrow 17 \rightarrow 41 \rightarrow 101 \rightarrow 251 \rightarrow 626 \rightarrow 1095 \rightarrow 2736 \rightarrow 2995 \rightarrow \cdots\\\hline\end{array}</math>
This sequence has been calculated out to over 17 million terms, with the final value of b calculated before the program was terminated reaching <math> >10^{4,800,000} </math>. No power of 2 was ever encountered (which would lead to halting), and the most factors of 2 any term had was 24.

The growth rate of this sequence was characterized by @LegionMammal978 as below:<br>
Assuming that the lower bits of b are random and uniform (which is well-supported empirically), it grows by an average log-factor of <math>0.652355</math>, which corresponds to <math>O(1.92006^b)</math>, plus or minus a random walk on the log scale.

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