Lucy's Moonlight

1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA (bbch)

Lucy's Moonlight is a probviously halting tetrational BB(6) Cryptid. This Turing machine was first mentioned on Discord by Racheline on 1 Mar 2025, who afterward found a set of high-level rules describing it. Shawn Ligocki later discovered and shared a more refined set of rules, displayed below.

	0	1
A	1RB	0RD
B	0RC	1RE
C	1RD	0LA
D	1LE	1LC
E	1RF	0LD
F	---	0RA

The transition table of Lucy's Moonlight.

Analysis

Let $C(a,b):=0^{\infty }\;1011^{a}\;1^{b}\;10\;{\textrm {C>}}\;0^{\infty }$. Then,

$${\begin{array}{|lll|}\hline C(a+1,3b)&\xrightarrow {12b^{2}+53b+28} &C(a,8b+6),\\C(a+2,3b+1)&\xrightarrow {12b^{2}+77b+103} &C(a,8b+16),\\C(a+2,3b+2)&\xrightarrow {12b^{2}+101b+184} &C(a,8b+22),\\C(0,3b)&\xrightarrow {12b^{2}+29b+52} &C(2b,8),\\C(0,3b+1)&\xrightarrow {12b^{2}+53b+30} &C(0,8b+5),\\C(1,3b+1)&\xrightarrow {12b^{2}+53b+58} &0^{\infty }\;1011^{2b+4}\;1\;{\textrm {F>}}\;0^{\infty },\\C(0,3b+2)&\xrightarrow {12b^{2}+53b+28} &C(0,8b+5),\\C(1,3b+2)&\xrightarrow {12b^{2}+77b+160} &C(2b+4,8).\\\hline \end{array}}$$

Proof

Consider the partial configuration $P(m,n):=1^{m}\;10^{n}\;{\textrm {C>}}\;0^{\infty }$, which after three steps is $1^{m}\;10^{n}\;{\textrm {<D}}\;01\;0^{\infty }$. To advance, this shift rule is required:

$${\begin{array}{|l|}\hline 10^{s}\;{\textrm {<D}}\xrightarrow {2s} {\textrm {<D}}\;01^{s}\\\hline \end{array}}$$

This means we have $1^{m}\;{\textrm {<D}}\;01^{n+1}\;0^{\infty }$ after $2n$ steps, with $1^{m-3}\;0\;{\textrm {D>}}\;01^{n+2}\;0^{\infty }$ after three further steps. From here, we can use the fact that $0\;{\textrm {D>}}\;01^{s}$ becomes $100\;{\textrm {D>}}\;01^{s-1}$ in four steps if $s\geq 1$ to get this rule:

$${\begin{array}{|l|}\hline 0\;{\textrm {D>}}\;01^{s}\xrightarrow {4s} 10^{s}\;0\;{\textrm {D>}}\\\hline \end{array}}$$

Using this rule produces $1^{m-3}\;10^{n+2}\;0\;{\textrm {D>}}\;0^{\infty }$ in $4n+8$ steps. With five more steps, we get $1^{m-3}\;10^{n+4}\;{\textrm {C>}}\;0^{\infty }$, which is also $P(m-3,n+4)$. To summarize:

$${\begin{array}{|l|}\hline P(m,n)\xrightarrow {6n+19} P(m-3,n+4){\text{ if }}m\geq 3.\\\hline \end{array}}$$

With $C(a,b)$ we have $P(b,1)$ and are able to apply this rule ${\textstyle {\Big \lfloor }{\frac {b}{3}}{\Big \rfloor }}$ times, with three possible scenarios:

1. If $b\equiv 0\ (\operatorname {mod} 3)$, then in ${\textstyle {\displaystyle \sum _{i=0}^{b/3-1}(6(1+4i)+19)}={\frac {4}{3}}b^{2}+{\frac {13}{3}}b}$ steps we arrive at ${\textstyle P{\Big (}0,1+{\frac {4b}{3}}{\Big )}}$. The matching complete configuration is $0^{\infty }\;1011^{a}\;10^{1+4b/3}\;{\textrm {C>}}\;0^{\infty }$. In ${\textstyle {\frac {8}{3}}b+5}$ steps we have $0^{\infty }\;1011^{a}\;{\textrm {<D}}\;01^{2+4b/3}\;0^{\infty }$, followed by $0^{\infty }\;1011^{a-1}\;11\;{\textrm {B>}}\;01^{3+4b/3}\;0^{\infty }$ after three steps. We note that if $s\geq 2$, then ${\textrm {B>}}\;01^{s}$ becomes $11\;{\textrm {B>}}\;01^{s-1}$ in 8 steps, giving this transition rule:
   $${\begin{array}{|l|}\hline {\textrm {B>}}\;01^{s}\xrightarrow {8s-4} 1^{2s-1}\;0\;{\textrm {C>}}{\text{ if }}s\geq 1.\\\hline \end{array}}$$
   In this instance, the result is $0^{\infty }\;1011^{a-1}\;1^{7+8b/3}\;0\;{\textrm {C>}}\;0^{\infty }$, equal to ${\textstyle C{\Big (}a-1,{\frac {8}{3}}b+6{\Big )}}$, after ${\textstyle {\frac {32}{3}}b+20}$ steps. This gives a total of ${\textstyle {\frac {4}{3}}b^{2}+{\frac {53}{3}}b+28}$ steps.
2. We can rewrite $C(a,b)$ as $0^{\infty }\;1011^{a-1}\;10\;1^{b+2}\;10\;{\textrm {C>}}\;0^{\infty }$ if $a\geq 1$. Given this, we have $P(b+2,1)$, and if $b\equiv 1\ (\operatorname {mod} 3)$, then in ${\textstyle {\frac {4}{3}}b^{2}+{\frac {29}{3}}b+14}$ steps we arrive at $0^{\infty }\;1011^{a-1}\;10^{(4b+14)/3}\;{\textrm {C>}}\;0^{\infty }$, which in ${\textstyle {\frac {8b+37}{3}}}$ steps becomes $0^{\infty }\;1011^{a-1}\;{\textrm {<D}}\;01^{(4b+17)/3}\;0^{\infty }$, and then $0^{\infty }\;1011^{a-2}\;11\;{\textrm {B>}}\;01^{(4b+20)/3}\;0^{\infty }$ after three more steps. We end with ${\textstyle {\frac {32b+148}{3}}}$ steps to get $0^{\infty }\;1011^{a-2}\;1^{(8b+43)/3}\;0\;{\textrm {C>}}\;0^{\infty }$, equal to ${\textstyle C{\Big (}a-2,{\frac {8b+40}{3}}{\Big )}}$. This gives a total of ${\textstyle {\frac {4}{3}}b^{2}+23b+{\frac {236}{3}}}$ steps.
3. If $b\equiv 2\ (\operatorname {mod} 3)$ and we reuse the technique of rewriting $C(a,b)$, then in ${\textstyle {\frac {4}{3}}b^{2}+7b+{\frac {17}{3}}}$ steps we arrive at $0^{\infty }\;1011^{a-1}\;101\;10^{(4b+7)/3}\;{\textrm {C>}}\;0^{\infty }$, which in ${\textstyle {\frac {8b+23}{3}}}$ steps becomes $0^{\infty }\;1011^{a-1}\;101\;{\textrm {<D}}\;01^{(4b+10)/3}\;0^{\infty }$, and then in five steps, $0^{\infty }\;1011^{a-1}\;0\;{\textrm {D>}}\;01^{(4b+13)/3}\;0^{\infty }$. Adding ${\textstyle {\frac {16b+52}{3}}}$ steps gives us $0^{\infty }\;1011^{a-1}\;10^{(4b+13)/3}\;0\;{\textrm {D>}}\;0^{\infty }$, and another eight gives us $0^{\infty }\;1011^{a-1}\;10^{(4b+19)/3}\;{\textrm {<D}}\;01\;0^{\infty }$. After ${\textstyle {\frac {8b+38}{3}}}$ steps, the configuration is $0^{\infty }\;1011^{a-1}\;{\textrm {<D}}\;01^{(4b+22)/3}\;0^{\infty }$ and after three more, $0^{\infty }\;1011^{a-2}\;11\;{\textrm {B>}}\;01^{(4b+25)/3}\;0^{\infty }$. We conclude with $0^{\infty }\;1011^{a-2}\;1^{(8b+53)/3}\;0\;{\textrm {C>}}\;0^{\infty }$, equal to ${\textstyle C{\Big (}a-2,{\frac {8b+50}{3}}{\Big )}}$, after ${\textstyle {\frac {32b+188}{3}}}$ steps, for a total of ${\textstyle {\frac {4}{3}}b^{2}+{\frac {85}{3}}b+122}$ steps.

The behaviour of Lucy's Moonlight changes at the boundary conditions: $a=0$ or $a=1$. These changes are addressed below:

1. If $a=0$ and $b\equiv 0\ (\operatorname {mod} 3)$, then starting from $0^{\infty }\;{\textrm {<D}}\;01^{2+4b/3}\;0^{\infty }$, we take three steps to get $0^{\infty }\;10\;{\textrm {A>}}\;01^{2+4b/3}\;0^{\infty }$. It is here that another shift rule must come into use:
   $${\begin{array}{|l|}\hline {\textrm {A>}}\;01^{2s}\xrightarrow {4s} 1110^{s}\;{\textrm {A>}}\\\hline \end{array}}$$
   Upon using this shift rule, we get $0^{\infty }\;10\;1110^{1+2b/3}\;{\textrm {A>}}\;0^{\infty }$ in ${\textstyle {\frac {8}{3}}b+4}$ steps. This configuration is the same as $0^{\infty }\;1011^{1+2b/3}\;10\;{\textrm {A>}}\;0^{\infty }$. With 40 more steps, we end at $0^{\infty }\;1011^{2b/3}\;1^{9}\;0\;{\textrm {C>}}\;0^{\infty }$, equal to ${\textstyle C{\Big (}{\frac {2}{3}}b,8{\Big )}}$, for a total of ${\textstyle {\frac {4}{3}}b^{2}+{\frac {29}{3}}b+52}$ steps.
2. If $a=0$ and $b\equiv 1\ (\operatorname {mod} 3)$, then in ${\textstyle {\frac {4}{3}}b^{2}+{\frac {5}{3}}b-3}$ steps we arrive at $0^{\infty }\;1\;10^{(4b-1)/3}\;{\textrm {C>}}\;0^{\infty }$. With ${\textstyle {\frac {8b+7}{3}}}$ more steps we now have $0^{\infty }\;1\;{\textrm {<D}}\;01^{(4b+2)/3}\;0^{\infty }$. Given five steps, the result is $0^{\infty }\;1\;{\textrm {B>}}\;01^{(4b+5)/3}\;0^{\infty }$, which turns into $0^{\infty }\;1^{(8b+10)/3}\;0\;{\textrm {C>}}\;0^{\infty }$, equal to ${\textstyle C{\Big (}0,{\frac {8b+7}{3}}{\Big )}}$ in ${\textstyle {\frac {32b+28}{3}}}$ steps for a total of ${\textstyle {\frac {4}{3}}b^{2}+15b+{\frac {41}{3}}}$ steps.
3. If $a=1$ and $b\equiv 1\ (\operatorname {mod} 3)$, then starting from $0^{\infty }\;{\textrm {<D}}\;01^{(4b+17)/3}\;0^{\infty }$, we get $0^{\infty }\;10\;{\textrm {A>}}\;01^{(4b+17)/3}\;0^{\infty }$ in three steps. Since $01^{(4b+17)/3}$ and $01^{(4b+14)/3}\;01$ are the same, what follows is $0^{\infty }\;1011^{(2b+7)/3}\;10\;{\textrm {A>}}\;01\;0^{\infty }$ in ${\textstyle {\frac {8b+28}{3}}}$ steps before finally reaching $0^{\infty }\;1011^{(2b+10)/3}\;1\;{\textrm {F>}}\;0^{\infty }$, and therefore the undefined F0 transition, in three steps. This gives a total of ${\textstyle {\frac {4}{3}}b^{2}+15b+{\frac {125}{3}}}$ steps.
4. If $a=0$ and $b\equiv 2\ (\operatorname {mod} 3)$, then in ${\textstyle {\frac {4}{3}}b^{2}-b-{\frac {10}{3}}}$ steps we arrive at $0^{\infty }\;11\;10^{(4x-5)/3}\;{\textrm {C>}}\;0^{\infty }$. It takes a further ${\textstyle {\frac {8b-1}{3}}}$ steps to reach $0^{\infty }\;11\;{\textrm {<D}}\;01^{(4b-2)/3}\;0^{\infty }$, and adding three more gives us $0^{\infty }\;1\;{\textrm {B>}}\;01^{(4b+1)/3}\;0^{\infty }$. With ${\textstyle {\frac {32b-4}{3}}}$ more steps we end up with $0^{\infty }\;1^{(8b+2)/3}\;0\;{\textrm {C>}}\;0^{\infty }$, equal to ${\textstyle C{\Big (}0,{\frac {8b-1}{3}}{\Big )}}$. This gives a total of ${\textstyle {\frac {4}{3}}b^{2}+{\frac {37}{3}}b-2}$ steps.
5. If $a=1$ and $b\equiv 2\ (\operatorname {mod} 3)$, then starting from $0^{\infty }\;{\textrm {<D}}\;01^{(4b+22)/3}\;0^{\infty }$, we take three steps to get $0^{\infty }\;10\;{\textrm {A>}}\;01^{(4b+22)/3}\;0^{\infty }$, and taking ${\textstyle {\frac {8b+44}{3}}}$ more steps produces $0^{\infty }\;1011^{(2b+11)/3}\;10\;{\textrm {A>}}\;0^{\infty }$. After 40 steps, we reach $0^{\infty }\;1011^{(2b+8)/3}\;1^{9}\;0\;{\textrm {C>}}\;0^{\infty }$, which is ${\textstyle C{\Big (}{\frac {2b+8}{3}},8{\Big )}}$, for a total of ${\textstyle {\frac {4}{3}}b^{2}+{\frac {61}{3}}b+114}$ steps.

The information above can be summarized as

$$C(a,b)\rightarrow {\begin{cases}C{\Big (}a-1,{\frac {8}{3}}b+6{\Big )}&{\text{if }}a\geq 1{\text{ and }}b\equiv 0{\pmod {3}},\\C{\Big (}a-2,{\frac {8b+40}{3}}{\Big )}&{\text{if }}a\geq 2{\text{ and }}b\equiv 1{\pmod {3}},\\C{\Big (}a-2,{\frac {8b+50}{3}}{\Big )}&{\text{if }}a\geq 2{\text{ and }}b\equiv 2{\pmod {3}},\\C{\Big (}{\frac {2}{3}}b,8{\Big )}&{\text{if }}a=0{\text{ and }}b\equiv 0{\pmod {3}},\\C{\Big (}0,{\frac {8b+7}{3}}{\Big )}&{\text{if }}a=0{\text{ and }}b\equiv 1{\pmod {3}},\\0^{\infty }\;1011^{(2b+10)/3}\;1\;{\textrm {F>}}\;0^{\infty }&{\text{if }}a=1{\text{ and }}b\equiv 1{\pmod {3}},\\C{\Big (}0,{\frac {8b-1}{3}}{\Big )}&{\text{if }}a=0{\text{ and }}b\equiv 2{\pmod {3}},\\C{\Big (}{\frac {2b+8}{3}},8{\Big )}&{\text{if }}a=1{\text{ and }}b\equiv 2{\pmod {3}}.\end{cases}}$$

Substituting $b=3b+k$, where $k$ is the remainder of $b$ modulo 3, yields the final result.

We can define these functions:

• ${\textstyle f(n)=10n+6-18{\Big \lfloor }{\frac {n}{3}}{\Big \rfloor }-4{\Big \lfloor }{\frac {n+1}{3}}{\Big \rfloor }}$ (the movement of $b$ according to the first three rules)
• ${\textstyle S(n)={\displaystyle \sum _{i=0}^{n}}{\bigg (}1+{\bigg \lfloor }{\frac {f^{i}(8)+1-3\lfloor f^{i}(8)/3\rfloor }{2}}{\bigg \rfloor }{\bigg )}}$ (which imitates $a$ decreasing, with $f^{i}(n)$ representing function iteration)
• $M_{f}(n)=\min\{k\in \mathbb {N} :(f^{k}(8)\equiv 0\ (\operatorname {mod} 3)\land S(k-1)=n)\lor (f^{k}(8)\not \equiv 0\ (\operatorname {mod} 3)\land S(k-1)\geq n-1)\}$ (the number of iterations of $f(n)$ needed to reach a boundary condition)
• ${\textstyle g(n)=8{\Big \lfloor }{\frac {n-1}{3}}{\Big \rfloor }+5}$ (representing rules 5 and 7)
• ${\textstyle M_{g}(n)=\min\{k\in \mathbb {N} :g^{k}(n)\equiv 0\ (\operatorname {mod} 3)\}}$ (the amount of times $g(n)$ must be applied to reach a multiple of 3)
• $q(n)=f^{M_{f}(n)}(8)$

The sequence of values for which as long as Lucy's Moonlight does not halt, we get configurations of the form $C(k,8)$, denoted $c_{n}$, can be written as:

$$\textstyle c_{0}=0,\qquad c_{n+1}=(c_{n}-S(M_{f}(c_{n})-1))\times {\frac {2q(c_{n})+8}{3}}+(1-c_{n}+S(M_{f}(c_{n})-1))\times {\frac {2}{3}}g^{M_{g}(q(c_{n}))}(q(c_{n})).$$

Lucy's Moonlight halts if and only if there exists a $c\in c_{n}$ such that $c-S(M_{f}(c)-1)=1$ and $q(c_{n})\equiv 1\ (\operatorname {mod} 3)$.

Trajectory

Starting with $C(0,0)$ after two steps, Lucy's Moonlight repeatedly applies the Collatz-like rules. The first few steps are shown below:

$${\begin{array}{|l|}\hline C(0,0)\xrightarrow {52} C(0,8)\xrightarrow {182} C(0,21)\xrightarrow {843} C(14,8)\xrightarrow {434} C(12,38)\xrightarrow {3124} C(10,118)\xrightarrow {21358} C(8,328)\rightarrow \cdots \\\hline \end{array}}$$

From $C(0,0)$, it takes 11 rule steps to get $C(11292,8)$ and 6811 more to get $C(c_{3},8)$, where $c_{3}\approx 8.282\times 10^{2901}$. Because $c_{n}$ grows tetrationally, analysis of $f^{i}(n)$ and $g^{i}(n)$ is critical to understanding the nature of any additional terms of this sequence. Despite this, Lucy's Moonlight can be argued to probviously halt if one considers each instance of $C(k,8)$ as the beginning of an independent round of a luck-based game, detailed below:

1. A random large number $n$ is generated.
2. At each time unit, $n$ will decrease by 1 with probability ${\textstyle {\frac {1}{3}}}$ or decrease by 2 with probability ${\textstyle {\frac {2}{3}}}$. This step repeats as long as $n\geq 2$.
3. If $n=1$, then $n$ will decrease to 0, the game is won, or a new round begins, each with probability ${\textstyle {\frac {1}{3}}}$.
4. If $n=0$, then a new round begins.

If $P(n)$ is the probability of winning a round with starting value $n$, then ${\textstyle P(n)={\frac {1}{3}}P(n-1)+{\frac {2}{3}}P(n-2)}$ if $n\geq 2$. This is a recurrence relation whose general solution is ${\textstyle P(n)=c_{0}+c_{1}{{\Big (}{-{\frac {2}{3}}}{\Big )}}^{n}}$. The boundary conditions $P(0)=0$ and ${\textstyle P(1)={\frac {1}{3}}}$ enable us to obtain ${\textstyle c_{0}={\frac {1}{5}}}$ and ${\textstyle c_{1}=-{\frac {1}{5}}}$. Since ${\textstyle \left\vert {-{\frac {2}{3}}}\right\vert <1}$, ${\textstyle P(n)\approx {\frac {1}{5}}}$ for large $n$, so the probability of winning the game in $r$ rounds is approximately ${\textstyle 1-{\Big (}{\frac {4}{5}}{\Big )}^{r}}$. Because there is an unlimited number of rounds available, the game will almost surely be won eventually, so Lucy's Moonlight will almost surely halt.