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^{\mathrm{\infty }}1011^a{1}^{b}10\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$. Then, $$\begin{array}{lll}C(a+1,3b)& \stackrel{12b^2+53b+28}{\to }& C(a,8b+6),\\ C(a+2,3b+1)& \stackrel{12b^2+77b+103}{\to }& C(a,8b+16),\\ C(a+2,3b+2)& \stackrel{12b^2+101b+184}{\to }& C(a,8b+22),\\ C(0,3b)& \stackrel{12b^2+29b+52}{\to }& C(2b,8),\\ C(0,3b+1)& \stackrel{12b^2+53b+30}{\to }& C(0,8b+5),\\ C(1,3b+1)& \stackrel{12b^2+53b+58}{\to }& 0^{\mathrm{\infty }}1011^{2b+4}1\text{<mrow data-mjx-texclass="ORD">F<mo>></mo></mrow>}{0}^{\mathrm{\infty }},\\ C(0,3b+2)& \stackrel{12b^2+53b+28}{\to }& C(0,8b+5),\\ C(1,3b+2)& \stackrel{12b^2+77b+160}{\to }& C(2b+4,8).\end{array}$$

Proof

Consider the partial configuration $P(m,n):=1^{m}10^n\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, which after three steps is $1^{m}10^n\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}010^{\mathrm{\infty }}$. To advance, this shift rule is required: $$\begin{array}{l}10^s\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}\stackrel{2s}{\to }\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^s\end{array}$$ This means we have $1^m\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{n+1}{0}^{\mathrm{\infty }}$ after $2n$ steps, with $1^{m-3}0\text{<mrow data-mjx-texclass="ORD">D<mo>></mo></mrow>}01^{n+2}{0}^{\mathrm{\infty }}$ after three further steps. From here, we can use the fact that $0\text{<mrow data-mjx-texclass="ORD">D<mo>></mo></mrow>}01^s$ becomes $100\text{<mrow data-mjx-texclass="ORD">D<mo>></mo></mrow>}01^{s-1}$ in four steps if $s\ge 1$ to get this rule: $$\begin{array}{l}0\text{<mrow data-mjx-texclass="ORD">D<mo>></mo></mrow>}01^s\stackrel{4s}{\to }10^{s}0\text{<mrow data-mjx-texclass="ORD">D<mo>></mo></mrow>}\end{array}$$ Using this rule produces $1^{m-3}10^{n+2}0\text{<mrow data-mjx-texclass="ORD">D<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$ in $4n+8$ steps. With five more steps, we get $1^{m-3}10^{n+4}\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, which is also $P(m-3,n+4)$. To summarize: $$\begin{array}{l}P(m,n)\stackrel{6n+19}{\to }P(m-3,n+4)\text{ if }m\ge 3.\end{array}$$ With $C(a,b)$ we have $P(b,1)$ and are able to apply this rule $\lfloor \frac{b}{3}\rfloor$ times, with three possible scenarios:

1. If $b\equiv 0(\mathrm{mod}3)$, then in $\sum _{i=0}^{b/3-1}(6(1+4i)+19)=\frac{4}{3}{b}^2+\frac{13}{3}b$ steps we arrive at $P(0,1+\frac{4b}{3})$. The matching complete configuration is $0^{\mathrm{\infty }}1011^{a}10^{1+4b/3}\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$. In $\frac{8}{3}b+5$ steps we have $0^{\mathrm{\infty }}1011^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{2+4b/3}{0}^{\mathrm{\infty }}$, followed by $0^{\mathrm{\infty }}1011^{a-1}11\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}01^{3+4b/3}{0}^{\mathrm{\infty }}$ after three steps. We note that if $s\ge 2$, then $\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}01^s$ becomes $11\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}01^{s-1}$ in 8 steps, giving this transition rule:$$\begin{array}{l}\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}01^s\stackrel{8s-4}{\to }{1}^{2s-1}0\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}\text{ if }s\ge 1.\end{array}$$In this instance, the result is $0^{\mathrm{\infty }}1011^{a-1}{1}^{7+8b/3}0\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $C(a-1,\frac{8}{3}b+6)$, after $\frac{32}{3}b+20$ steps. This gives a total of $\frac{4}{3}{b}^2+\frac{53}{3}b+28$ steps.
2. We can rewrite $C(a,b)$ as $0^{\mathrm{\infty }}1011^{a-1}101^{b+2}10\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$ if $a\ge 1$. Given this, we have $P(b+2,1)$, and if $b\equiv 1(\mathrm{mod}3)$, then in $\frac{4}{3}{b}^2+\frac{29}{3}b+14$ steps we arrive at $0^{\mathrm{\infty }}1011^{a-1}10^{(4b+14)/3}\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, which in $\frac{8b+37}{3}$ steps becomes $0^{\mathrm{\infty }}1011^{a-1}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{(4b+17)/3}{0}^{\mathrm{\infty }}$, and then $0^{\mathrm{\infty }}1011^{a-2}11\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}01^{(4b+20)/3}{0}^{\mathrm{\infty }}$ after three more steps. We end with $\frac{32b+148}{3}$ steps to get $0^{\mathrm{\infty }}1011^{a-2}{1}^{(8b+43)/3}0\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $C(a-2,\frac{8b+40}{3})$. This gives a total of $\frac{4}{3}{b}^2+23b+\frac{236}{3}$ steps.
3. If $b\equiv 2(\mathrm{mod}3)$ and we reuse the technique of rewriting $C(a,b)$, then in $\frac{4}{3}{b}^2+7b+\frac{17}{3}$ steps we arrive at $0^{\mathrm{\infty }}1011^{a-1}10110^{(4b+7)/3}\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, which in $\frac{8b+23}{3}$ steps becomes $0^{\mathrm{\infty }}1011^{a-1}101\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{(4b+10)/3}{0}^{\mathrm{\infty }}$, and then in five steps, $0^{\mathrm{\infty }}1011^{a-1}0\text{<mrow data-mjx-texclass="ORD">D<mo>></mo></mrow>}01^{(4b+13)/3}{0}^{\mathrm{\infty }}$. Adding $\frac{16b+52}{3}$ steps gives us $0^{\mathrm{\infty }}1011^{a-1}10^{(4b+13)/3}0\text{<mrow data-mjx-texclass="ORD">D<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, and another eight gives us $0^{\mathrm{\infty }}1011^{a-1}10^{(4b+19)/3}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}010^{\mathrm{\infty }}$. After $\frac{8b+38}{3}$ steps, the configuration is $0^{\mathrm{\infty }}1011^{a-1}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{(4b+22)/3}{0}^{\mathrm{\infty }}$ and after three more, $0^{\mathrm{\infty }}1011^{a-2}11\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}01^{(4b+25)/3}{0}^{\mathrm{\infty }}$. We conclude with $0^{\mathrm{\infty }}1011^{a-2}{1}^{(8b+53)/3}0\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $C(a-2,\frac{8b+50}{3})$, after $\frac{32b+188}{3}$ steps, for a total of $\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(\mathrm{mod}3)$, then starting from $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{2+4b/3}{0}^{\mathrm{\infty }}$, we take three steps to get $0^{\mathrm{\infty }}10\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}01^{2+4b/3}{0}^{\mathrm{\infty }}$. It is here that another shift rule must come into use:$$\begin{array}{l}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}01^{2s}\stackrel{4s}{\to }1110^s\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}\end{array}$$Upon using this shift rule, we get $0^{\mathrm{\infty }}101110^{1+2b/3}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$ in $\frac{8}{3}b+4$ steps. This configuration is the same as $0^{\mathrm{\infty }}1011^{1+2b/3}10\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$. With 40 more steps, we end at $0^{\mathrm{\infty }}1011^{2b/3}{1}^{9}0\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $C(\frac{2}{3}b,8)$, for a total of $\frac{4}{3}{b}^2+\frac{29}{3}b+52$ steps.
2. If $a=0$ and $b\equiv 1(\mathrm{mod}3)$, then in $\frac{4}{3}{b}^2+\frac{5}{3}b-3$ steps we arrive at $0^{\mathrm{\infty }}110^{(4b-1)/3}\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$. With $\frac{8b+7}{3}$ more steps we now have $0^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{(4b+2)/3}{0}^{\mathrm{\infty }}$. Given five steps, the result is $0^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}01^{(4b+5)/3}{0}^{\mathrm{\infty }}$, which turns into $0^{\mathrm{\infty }}{1}^{(8b+10)/3}0\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $C(0,\frac{8b+7}{3})$ in $\frac{32b+28}{3}$ steps for a total of $\frac{4}{3}{b}^2+15b+\frac{41}{3}$ steps.
3. If $a=1$ and $b\equiv 1(\mathrm{mod}3)$, then starting from $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{(4b+17)/3}{0}^{\mathrm{\infty }}$, we get $0^{\mathrm{\infty }}10\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}01^{(4b+17)/3}{0}^{\mathrm{\infty }}$ in three steps. Since $01^{(4b+17)/3}$ and $01^{(4b+14)/3}01$ are the same, what follows is $0^{\mathrm{\infty }}1011^{(2b+7)/3}10\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}010^{\mathrm{\infty }}$ in $\frac{8b+28}{3}$ steps before finally reaching $0^{\mathrm{\infty }}1011^{(2b+10)/3}1\text{<mrow data-mjx-texclass="ORD">F<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, and therefore the undefined F0 transition, in three steps. This gives a total of $\frac{4}{3}{b}^2+15b+\frac{125}{3}$ steps.
4. If $a=0$ and $b\equiv 2(\mathrm{mod}3)$, then in $\frac{4}{3}{b}^2-b-\frac{10}{3}$ steps we arrive at $0^{\mathrm{\infty }}1110^{(4x-5)/3}\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$. It takes a further $\frac{8b-1}{3}$ steps to reach $0^{\mathrm{\infty }}11\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{(4b-2)/3}{0}^{\mathrm{\infty }}$, and adding three more gives us $0^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}01^{(4b+1)/3}{0}^{\mathrm{\infty }}$. With $\frac{32b-4}{3}$ more steps we end up with $0^{\mathrm{\infty }}{1}^{(8b+2)/3}0\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $C(0,\frac{8b-1}{3})$. This gives a total of $\frac{4}{3}{b}^2+\frac{37}{3}b-2$ steps.
5. If $a=1$ and $b\equiv 2(\mathrm{mod}3)$, then starting from $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>D</mrow>}01^{(4b+22)/3}{0}^{\mathrm{\infty }}$, we take three steps to get $0^{\mathrm{\infty }}10\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}01^{(4b+22)/3}{0}^{\mathrm{\infty }}$, and taking $\frac{8b+44}{3}$ more steps produces $0^{\mathrm{\infty }}1011^{(2b+11)/3}10\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$. After 40 steps, we reach $0^{\mathrm{\infty }}1011^{(2b+8)/3}{1}^{9}0\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, which is $C(\frac{2b+8}{3},8)$, for a total of $\frac{4}{3}{b}^2+\frac{61}{3}b+114$ steps.

The information above can be summarized as $$C(a,b)\to \{\begin{array}{ll}C(a-1,\frac{8}{3}b+6)& \text{if }a\ge 1\text{ and }b\equiv 0(\mathrm{mod}3),\\ C(a-2,\frac{8b+40}{3})& \text{if }a\ge 2\text{ and }b\equiv 1(\mathrm{mod}3),\\ C(a-2,\frac{8b+50}{3})& \text{if }a\ge 2\text{ and }b\equiv 2(\mathrm{mod}3),\\ C(\frac{2}{3}b,8)& \text{if }a=0\text{ and }b\equiv 0(\mathrm{mod}3),\\ C(0,\frac{8b+7}{3})& \text{if }a=0\text{ and }b\equiv 1(\mathrm{mod}3),\\ 0^{\mathrm{\infty }}1011^{(2b+10)/3}1\text{<mrow data-mjx-texclass="ORD">F<mo>></mo></mrow>}{0}^{\mathrm{\infty }}& \text{if }a=1\text{ and }b\equiv 1(\mathrm{mod}3),\\ C(0,\frac{8b-1}{3})& \text{if }a=0\text{ and }b\equiv 2(\mathrm{mod}3),\\ C(\frac{2b+8}{3},8)& \text{if }a=1\text{ and }b\equiv 2(\mathrm{mod}3).\end{array}$$ Substituting $b=3b+k$, where $k$ is the remainder of $b$ modulo 3, yields the final result.

We can define these functions:

• $f(n)=10n+6-18\lfloor \frac{n}{3}\rfloor -4\lfloor \frac{n+1}{3}\rfloor$ (the movement of $b$ according to the first three rules)
• $S(n)=\sum _{i=0}^n(1+\lfloor \frac{f^i(8)+1-3\lfloor f^i(8)/3\rfloor }{2}\rfloor )$ (which imitates $a$ decreasing, with $f^i(n)$ representing function iteration)
• $M_f(n)=\min \{k\in \mathbb{\mathbb{N}}:(f^k(8)\equiv 0(\mathrm{mod}3)\wedge S(k-1)=n)\vee (f^k(8)\equiv ̸0(\mathrm{mod}3)\wedge S(k-1)\ge n-1)\}$ (the number of iterations of $f(n)$ needed to reach a boundary condition)
• $g(n)=8\lfloor \frac{n-1}{3}\rfloor +5$ (representing rules 5 and 7)
• $M_g(n)=\min \{k\in \mathbb{\mathbb{N}}:g^k(n)\equiv 0(\mathrm{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: $$c_0=0,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(\mathrm{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}C(0,0)\stackrel{52}{\to }C(0,8)\stackrel{182}{\to }C(0,21)\stackrel{843}{\to }C(14,8)\stackrel{434}{\to }C(12,38)\stackrel{3124}{\to }C(10,118)\stackrel{21358}{\to }C(8,328)\to \cdots \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 $\frac{1}{3}$ or decrease by 2 with probability $\frac{2}{3}$. This step repeats as long as $n\ge 2$.
3. If $n=1$, then $n$ will decrease to 0, the game is won, or a new round begins, each with probability $\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 $P(n)=\frac{1}{3}P(n-1)+\frac{2}{3}P(n-2)$ if $n\ge 2$. This is a recurrence relation whose general solution is $P(n)=c_0+c_1{\left(-\frac{2}{3}\right)}^n$. The boundary conditions $P(0)=0$ and $P(1)=\frac{1}{3}$ enable us to obtain $c_0=\frac{1}{5}$ and $c_1=-\frac{1}{5}$. Since $\left|-\frac{2}{3}\right|<1$, $P(n)\approx \frac{1}{5}$ for large $n$, so the probability of winning the game in $r$ rounds is approximately $1-(\frac{4}{5}{)}^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.