Bigfoot

1RB2RA1LC_2LC1RB2RB_---2LA1LA (bbch)

Unsolved problem:

Does Bigfoot run forever?

Bigfoot is a BB(3,3) Cryptid. Its low-level behaviour was first shared over Discord by savask on 14 Oct 2023, and within two days, Shawn Ligocki described the high-level rules shown below, whose attributes inspired the Turing machine's name.

	0	1	2
A	1RB	2RA	1LC
B	2LC	1RB	2RB
C	---	2LA	1LA

The transition table of Bigfoot.

Bigfoot was also successfully compiled to a 7-state 2-symbol machine by Iijil: 0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB (bbch) in May of 2024.

Analysis

Let $A(a,b,c):=0^{\mathrm{\infty }}12^a{1}^{2b}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{2c}{0}^{\mathrm{\infty }}$. Then, $$\begin{array}{lll}A(a,6b,c)& \stackrel{4a+(2b+1)48b+(12b+1)2c+13}{\to }& A(a,8b+c-1,2),\\ A(a,6b+1,c)& \stackrel{4a+(6b+5)16b+(4b+1)6c+29}{\to }& A(a+1,8b+c-1,3),\\ A(0,6b+2,c)& \stackrel{(b+1)96b+(3b+1)8c+18}{\to }& 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{16b+2c+5}20^{\mathrm{\infty }},\\ A(a,6b+2,c)& \stackrel{4a+(2b+3)48b+(12b+7)2c+51}{\to }& A(a-1,8b+c+3,2)\text{ if }a\ge 1,\\ A(a,6b+3,c)& \stackrel{4a+(6b+7)16b+(12b+5)2c+91}{\to }& A(a,8b+c+1,5),\\ A(a,6b+4,c)& \stackrel{4a+(2b+3)48b+(12b+7)2c+63}{\to }& A(a+1,8b+c+3,2),\\ A(a,6b+5,c)& \stackrel{4a+(6b+11)16b+(4b+3)6c+103}{\to }& A(a,8b+c+5,3).\end{array}$$

Proof

For now, we will work with the slightly different configuration $A^{\prime }(a,b,c):=0^{\mathrm{\infty }}12^a{1}^b\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^c{0}^{\mathrm{\infty }}$. Consider the partial configuration $P(m,n):=1^m\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^n{0}^{\mathrm{\infty }}$. We first require the following shift rule: $$\begin{array}{l}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{1}^s\stackrel{s}{\to }{2}^s\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}\end{array}$$ Using this shift rule, we get $1^{m-1}{2}^{n+1}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$ after $n+1$ steps, followed by $1^{m-1}{2}^n\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}1220^{\mathrm{\infty }}$ four steps later. Observing that $22\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}$ becomes $\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}11$ in two steps leads to another shift rule: $$\begin{array}{l}{2}^{2s}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}\stackrel{2s}{\to }\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{2s}\end{array}$$ From here, there are two different scenarios depending on if $n$ is even or odd, given below as histories of transitions that use the aforementioned shift rules:

1. If $n\equiv 0(\mathrm{mod}2)$, then what follows is:$$\begin{array}{l}{1}^{m-1}{2}^n\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}1220^{\mathrm{\infty }}\stackrel{n}{\to }{1}^{m-1}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{n+1}220^{\mathrm{\infty }}\stackrel{4}{\to }{1}^{m-3}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{n+3}220^{\mathrm{\infty }}\stackrel{n+4}{\to }\\ 1^{m-4}{2}^{n+4}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}220^{\mathrm{\infty }}\stackrel{1}{\to }{1}^{m-4}{2}^{n+4}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}120^{\mathrm{\infty }}\stackrel{n+4}{\to }{1}^{m-4}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{n+5}20^{\mathrm{\infty }}\stackrel{4}{\to }\\ 1^{m-6}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{n+7}20^{\mathrm{\infty }}\stackrel{n+8}{\to }{1}^{m-7}{2}^{n+8}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}20^{\mathrm{\infty }}\stackrel{1}{\to }{1}^{m-7}{2}^{n+8}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}10^{\mathrm{\infty }}\stackrel{n+8}{\to }\\ 1^{m-7}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{n+9}{0}^{\mathrm{\infty }}\stackrel{4}{\to }{1}^{m-9}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{n+11}{0}^{\mathrm{\infty }}\end{array}$$Therefore, we have$$\begin{array}{l}P(m,n)\stackrel{6n+43}{\to }P(m-9,n+11)\text{ if }m\ge 9\text{ and }n\equiv 0(\mathrm{mod}2).\end{array}$$
2. If $n\equiv 1(\mathrm{mod}2)$, then what follows is:$$\begin{array}{l}{1}^{m-1}{2}^n\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}1220^{\mathrm{\infty }}\stackrel{n-1}{\to }{1}^{m-1}2\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{n}220^{\mathrm{\infty }}\stackrel{1}{\to }{1}^{m-1}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{n+1}220^{\mathrm{\infty }}\stackrel{n+2}{\to }\\ 1^{m-2}{2}^{n+2}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}220^{\mathrm{\infty }}\stackrel{1}{\to }{1}^{m-2}{2}^{n+2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}120^{\mathrm{\infty }}\stackrel{n+1}{\to }{1}^{m-2}2\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{n+2}20^{\mathrm{\infty }}\stackrel{1}{\to }\\ 1^{m-2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{n+3}20^{\mathrm{\infty }}\stackrel{n+4}{\to }{1}^{m-3}{2}^{n+4}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}20^{\mathrm{\infty }}\stackrel{1}{\to }{1}^{m-3}{2}^{n+4}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}10^{\mathrm{\infty }}\stackrel{n+3}{\to }\\ 1^{m-3}2\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{n+4}{0}^{\mathrm{\infty }}\stackrel{1}{\to }{1}^{m-3}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{n+5}{0}^{\mathrm{\infty }}\end{array}$$Therefore, we have

$$\begin{array}{l}P(m,n)\stackrel{6n+19}{\to }P(m-3,n+5)\text{ if }m\ge 3\text{ and }n\equiv 1(\mathrm{mod}2).\end{array}$$ From this we know that Bigfoot's behaviour depends on the value of $b$ modulo 12, and with $A^{\prime }(a,b,c)$ we have $P(b,c)$. The following shift rules will be useful: $$\begin{array}{lll}12^s\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}\stackrel{2s}{\to }\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^s& \text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}{1}^s\stackrel{s}{\to }{1}^s\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}& \text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}{2}^s\stackrel{s}{\to }{2}^s\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}\end{array}$$ Only even values of $b$ and $c$ are relevant, so there remain six possible scenarios:

1. If $b\equiv 0(\mathrm{mod}12)$, then in $\sum _{i=0}^{b/12-1}(6(16i+c)+43+6(16i+11+c)+19)=\sum _{i=0}^{b/12-1}4(48i+3c+32)=\frac{2}{3}{b}^2+\frac{8}{3}b+bc$ steps we arrive at $P(0,16\times \frac{b}{12}+c)$, or $0^{\mathrm{\infty }}12^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4b/3+c}{0}^{\mathrm{\infty }}$ when considering the complete configuration. What follows is:$$\begin{array}{l}{0}^{\mathrm{\infty }}12^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4b/3+c}{0}^{\mathrm{\infty }}\stackrel{2a}{\to }{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^a{1}^{4b/3+c}{0}^{\mathrm{\infty }}\stackrel{1}{\to }{0}^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}21^a{1}^{4b/3+c}{0}^{\mathrm{\infty }}\stackrel{2a+4b/3+c}{\to }\\ 0^{\mathrm{\infty }}12^a{1}^{4b/3+c+1}\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}{0}^{\mathrm{\infty }}\stackrel{12}{\to }{0}^{\mathrm{\infty }}12^a{1}^{4b/3+c-2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^4{0}^{\mathrm{\infty }}\end{array}$$This means that if $\frac{4}{3}b+c\ge 2$, then we will reach $A^{\prime }(a,\frac{4}{3}b+c-2,4)$ in $4a+\frac{2}{3}{b}^2+4b+bc+c+13$ steps.
2. If $b\equiv 2(\mathrm{mod}12)$, then in $\sum _{i=0}^{(b-2)/12-1}4(48i+3c+32)=\frac{2}{3}{b}^2+bc-2c-\frac{8}{3}$ steps we arrive at $P(2,\frac{4(b-2)}{3}+c)$, or $0^{\mathrm{\infty }}12^{a}11\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{(4b-2)/3+c}{0}^{\mathrm{\infty }}$. What follows is:$$\begin{array}{l}{0}^{\mathrm{\infty }}12^{a}11\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-2)/3+c}{0}^{\mathrm{\infty }}\stackrel{4(b-2)/3+c+1}{\to }{0}^{\mathrm{\infty }}12^{a}12^{4(b-2)/3+c+1}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}\stackrel{4}{\to }\\ 0^{\mathrm{\infty }}12^{a}12^{4(b-2)/3+c}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}1220^{\mathrm{\infty }}\stackrel{4(b-2)/3+c}{\to }{0}^{\mathrm{\infty }}12^{a}1\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{4(b-2)/3+c+1}220^{\mathrm{\infty }}\stackrel{1}{\to }\\ 0^{\mathrm{\infty }}12^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^{4(b-2)/3+c+1}220^{\mathrm{\infty }}\stackrel{2a}{\to }{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^{a}21^{4(b-2)/3+c+1}220^{\mathrm{\infty }}\stackrel{1}{\to }\\ 0^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}21^{a}21^{4(b-2)/3+c+1}220^{\mathrm{\infty }}\stackrel{4(b-2)/3+2a+c+4}{\to }{0}^{\mathrm{\infty }}12^{a+1}{1}^{4(b-2)/3+c+1}22\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}{0}^{\mathrm{\infty }}\stackrel{18}{\to }\\ 0^{\mathrm{\infty }}12^{a+1}{1}^{4(b-2)/3+c-2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^6{0}^{\mathrm{\infty }}\end{array}$$This means that if $\frac{4(b-2)}{3}+c\ge 2$, then we will reach $A^{\prime }(a+1,\frac{4b-14}{3}+c,6)$ in $4a+\frac{2}{3}{b}^2+4b+bc+c+\frac{55}{3}$ steps.
3. If $b\equiv 4(\mathrm{mod}12)$, then in $\frac{2}{3}{b}^2-\frac{8}{3}b+bc-4c$ steps we arrive at $P(4,\frac{4(b-4)}{3}+c)$, or $0^{\mathrm{\infty }}12^{a}1111\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-4)/3+c}{0}^{\mathrm{\infty }}$. What follows is:$$\begin{array}{l}{0}^{\mathrm{\infty }}12^{a}1111\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-4)/3+c}{0}^{\mathrm{\infty }}\stackrel{(8b-14)/3+2c}{\to }{0}^{\mathrm{\infty }}12^{a}11\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^{4(b-4)/3+c+1}220^{\mathrm{\infty }}\stackrel{3}{\to }\\ 0^{\mathrm{\infty }}12^{a}1\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-4)/3+c+3}220^{\mathrm{\infty }}\stackrel{4(b-4)/3+c+4}{\to }{0}^{\mathrm{\infty }}12^a{2}^{4(b-4)/3+c+4}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}220^{\mathrm{\infty }}\stackrel{1}{\to }\\ 0^{\mathrm{\infty }}12^a{2}^{4(b-4)/3+c+4}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}120^{\mathrm{\infty }}\stackrel{4(b-4)/3+c+4}{\to }{0}^{\mathrm{\infty }}12^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{4(b-4)/3+c+5}20^{\mathrm{\infty }}\stackrel{1}{\to }\\ 0^{\mathrm{\infty }}12^{a-1}1\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-4)/3+c+6}20^{\mathrm{\infty }}\stackrel{4(b-4)/3+c+7}{\to }{0}^{\mathrm{\infty }}12^{a-1}{2}^{4(b-4)/3+c+7}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}20^{\mathrm{\infty }}\stackrel{1}{\to }\\ 0^{\mathrm{\infty }}12^{a-1}{2}^{4(b-4)/3+c+7}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}10^{\mathrm{\infty }}\stackrel{4(b-4)/3+c+6}{\to }{0}^{\mathrm{\infty }}12^{a-1}2\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{4(b-4)/3+c+7}{0}^{\mathrm{\infty }}\stackrel{1}{\to }\\ 0^{\mathrm{\infty }}12^{a-1}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-4)/3+c+8}{0}^{\mathrm{\infty }}\stackrel{2(a-1)}{\to }{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^{a-1}{1}^{4(b-4)/3+c+8}{0}^{\mathrm{\infty }}\stackrel{1}{\to }\\ 0^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}21^{a-1}{1}^{4(b-4)/3+c+8}{0}^{\mathrm{\infty }}\stackrel{2a+4(b-4)/3+c+6}{\to }{0}^{\mathrm{\infty }}12^{a-1}{1}^{4(b-4)/3+c+9}\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}{0}^{\mathrm{\infty }}\stackrel{12}{\to }\\ 0^{\mathrm{\infty }}12^{a-1}{1}^{4(b-4)/3+c+6}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^4{0}^{\mathrm{\infty }}\end{array}$$This means that if $a=0$, then Bigfoot will reach the undefined C0 transition with the configuration $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{(4b-1)/3+c}20^{\mathrm{\infty }}$ in $\frac{2}{3}{b}^2+\frac{8}{3}b+bc-\frac{10}{3}$ steps. Otherwise, it will proceed to reach $A^{\prime }(a-1,\frac{4b+2}{3}+c,4)$ in $4a+\frac{2}{3}{b}^2+\frac{20}{3}b+bc+3c+\frac{41}{3}$ steps.
4. If $b\equiv 6(\mathrm{mod}12)$, then in $\frac{2}{3}{b}^2-\frac{16}{3}b+bc-6c+8$ steps we arrive at $P(6,\frac{4(b-6)}{3}+c)$, or $0^{\mathrm{\infty }}12^{a}111111\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-6)/3+c}{0}^{\mathrm{\infty }}$. What follows is:$$\begin{array}{l}{0}^{\mathrm{\infty }}12^{a}111111\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-6)/3+c}{0}^{\mathrm{\infty }}\stackrel{16b/3+4c-14}{\to }{0}^{\mathrm{\infty }}12^{a}11\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{4(b-6)/3+c+5}20^{\mathrm{\infty }}\stackrel{4}{\to }\\ 0^{\mathrm{\infty }}12^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-6)/3+c+7}20^{\mathrm{\infty }}\stackrel{2a}{\to }{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^a{1}^{4(b-6)/3+c+7}20^{\mathrm{\infty }}\stackrel{1}{\to }\\ 0^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}21^a{1}^{4(b-6)/3+c+7}20^{\mathrm{\infty }}\stackrel{2a+4(b-6)/3+c+8}{\to }{0}^{\mathrm{\infty }}12^a{1}^{4(b-6)/3+c+8}2\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}{0}^{\mathrm{\infty }}\stackrel{60}{\to }\\ 0^{\mathrm{\infty }}12^a{1}^{4(b-6)/3+c+2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{10}{0}^{\mathrm{\infty }}\end{array}$$This means that we will reach $A^{\prime }(a,\frac{4}{3}b+c-6,10)$ in $4a+\frac{2}{3}{b}^2+\frac{4}{3}b+bc-c+59$ steps.
5. If $b\equiv 8(\mathrm{mod}12)$, then in $\frac{2}{3}{b}^2-8b+bc-8c+\frac{64}{3}$ steps we arrive at $P(8,\frac{4(b-8)}{3}+c)$, or $0^{\mathrm{\infty }}12^a{1}^8\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-8)/3+c}{0}^{\mathrm{\infty }}$. What follows is:$$\begin{array}{l}{0}^{\mathrm{\infty }}12^a{1}^8\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-8)/3+c}{0}^{\mathrm{\infty }}\stackrel{(16b-62)/3+4c}{\to }{0}^{\mathrm{\infty }}12^{a}11\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-8)/3+c+7}20^{\mathrm{\infty }}\stackrel{4(b-8)/3+c+8}{\to }\\ 0^{\mathrm{\infty }}12^{a}12^{4(b-8)/3+c+8}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}20^{\mathrm{\infty }}\stackrel{1}{\to }{0}^{\mathrm{\infty }}12^{a}12^{4(b-8)/3+c+8}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}10^{\mathrm{\infty }}\stackrel{4(b-8)/3+c+8}{\to }\\ 0^{\mathrm{\infty }}12^{a}1\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{4(b-8)/3+c+9}{0}^{\mathrm{\infty }}\stackrel{1}{\to }{0}^{\mathrm{\infty }}12^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^{4(b-8)/3+c+9}{0}^{\mathrm{\infty }}\stackrel{2a}{\to }\\ 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}21^{a}21^{4(b-8)/3+c+9}{0}^{\mathrm{\infty }}\stackrel{1}{\to }{0}^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}21^{a}21^{4(b-8)/3+c+9}{0}^{\mathrm{\infty }}\stackrel{2a+4(b-8)/3+c+10}{\to }\\ 0^{\mathrm{\infty }}12^{a+1}{1}^{4(b-8)/3+c+9}\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}{0}^{\mathrm{\infty }}\stackrel{12}{\to }{0}^{\mathrm{\infty }}12^{a+1}{1}^{4(b-8)/3+c+6}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^4{0}^{\mathrm{\infty }}\end{array}$$This means that we will reach $A^{\prime }(a+1,\frac{4b-14}{3}+c,4)$ in $4a+\frac{2}{3}{b}^2+\frac{4}{3}b+bc-c+\frac{29}{3}$ steps.
6. If $b\equiv 10(\mathrm{mod}12)$, then in $\frac{2}{3}{b}^2-\frac{32}{3}b+bc-10c+40$ steps we arrive at $P(10,\frac{4(b-10)}{3}+c)$, or $0^{\mathrm{\infty }}12^a{1}^{10}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-10)/3+c}{0}^{\mathrm{\infty }}$. What follows is:$$\begin{array}{l}{0}^{\mathrm{\infty }}12^a{1}^{10}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-10)/3+c}{0}^{\mathrm{\infty }}\stackrel{8b+6c-37}{\to }{0}^{\mathrm{\infty }}12^{a}1\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-10)/3+c+11}{0}^{\mathrm{\infty }}\stackrel{4(b-10)/3+c+12}{\to }\\ 0^{\mathrm{\infty }}12^a{2}^{4(b-10)/3+c+12}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}\stackrel{4}{\to }{0}^{\mathrm{\infty }}12^a{2}^{4(b-10)/3+c+11}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}1220^{\mathrm{\infty }}\stackrel{4(b-10)/3+c+10}{\to }\\ 0^{\mathrm{\infty }}12^{a}2\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{4(b-10)/3+c+11}220^{\mathrm{\infty }}\stackrel{1}{\to }{0}^{\mathrm{\infty }}12^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^{4(b-10)/3+c+12}220^{\mathrm{\infty }}\stackrel{2a}{\to }\\ 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}12^a{1}^{4(b-10)/3+c+12}220^{\mathrm{\infty }}\stackrel{1}{\to }{0}^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}12^a{1}^{4(b-10)/3+c+12}220^{\mathrm{\infty }}\stackrel{2a+4(b-10)/3+c+14}{\to }\\ 0^{\mathrm{\infty }}12^a{1}^{4(b-10)/3+c+13}22\text{<mrow data-mjx-texclass="ORD">B<mo>></mo></mrow>}{0}^{\mathrm{\infty }}\stackrel{18}{\to }{0}^{\mathrm{\infty }}12^a{1}^{4(b-10)/3+c+10}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^6{0}^{\mathrm{\infty }}\end{array}$$This means that we will reach $A^{\prime }(a,\frac{4b-10}{3}+c,6)$ in $4a+\frac{2}{3}{b}^2+\frac{4}{3}b+bc-c+23$ steps.

The information above can be summarized as $$A^{\prime }(a,b,c)\to \{\begin{array}{ll}{A}^{\prime }(a,\frac{4}{3}b+c-2,4)& \text{if }b\equiv 0(\mathrm{mod}12)\text{ and }\frac{4}{3}b+c\ge 2,\\ A^{\prime }(a+1,\frac{4b-14}{3}+c,6)& \text{if }b\equiv 2(\mathrm{mod}12)\text{ and }\frac{4(b-2)}{3}+c\ge 2,\\ 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{(4b-1)/3+c}20^{\mathrm{\infty }}& \text{if }b\equiv 4(\mathrm{mod}12)\text{ and }a=0,\\ A^{\prime }(a-1,\frac{4b+2}{3}+c,4)& \text{if }b\equiv 4(\mathrm{mod}12)\text{ and }a>0,\\ A^{\prime }(a,\frac{4}{3}b+c-6,10)& \text{if }b\equiv 6(\mathrm{mod}12),\\ A^{\prime }(a+1,\frac{4b-14}{3}+c,4)& \text{if }b\equiv 8(\mathrm{mod}12),\\ A^{\prime }(a,\frac{4b-10}{3}+c,6)& \text{if }b\equiv 10(\mathrm{mod}12).\end{array}$$ Using the definitions of $A^{\prime }$ and $A$ to transform these rules produces this: $$A(a,b,c)\to \{\begin{array}{ll}A(a,\frac{4}{3}b+c-1,2)& \text{if }b\equiv 0(\mathrm{mod}6)\text{ and }\frac{4}{3}b+c\ge 1,\\ A(a+1,\frac{4b-7}{3}+c,3)& \text{if }b\equiv 1(\mathrm{mod}6)\text{ and }\frac{4(b-1)}{3}+c\ge 1,\\ 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{(8b-1)/3+2c}20^{\mathrm{\infty }}& \text{if }b\equiv 2(\mathrm{mod}6)\text{ and }a=0,\\ A(a-1,\frac{4b+1}{3}+c,2)& \text{if }b\equiv 2(\mathrm{mod}6)\text{ and }a>0,\\ A(a,\frac{4}{3}b+c-3,5)& \text{if }b\equiv 3(\mathrm{mod}6),\\ A(a+1,\frac{4b-7}{3}+c,2)& \text{if }b\equiv 4(\mathrm{mod}6),\\ A(a,\frac{4b-5}{3}+c,3)& \text{if }b\equiv 5(\mathrm{mod}6).\end{array}$$ Substituting $b\leftarrow 6b+k$ where $k$ is the remainder for each case yields the final result.

Using the floor function, it is possible to describe the behaviour of $b$ and $c$ using a function that is not defined piecewise: $$\begin{array}{c}f(m,n)=(\frac{4m-3-4({\delta }_1(m)-{\delta }_2(m)+{\delta }_4(m))-2(3{\delta }_3(m)+{\delta }_5(m))}{3}+n,2+{\delta }_1(m)+3{\delta }_3(m)+{\delta }_5(m)),\\ {\delta }_i(m)=\lfloor \frac{x-i}{6}\rfloor -\lfloor \frac{x-i-1}{6}\rfloor =\{\begin{array}{ll}1& \text{if }x\equiv i(\mathrm{mod}6),\\ 0& \text{otherwise.}\end{array}\end{array}$$ In effect, the halting problem for Bigfoot is about whether through enough iterations of $f(m,n)$ we encounter more $m$ values that are congruent to 2 modulo 6 than ones that are congruent to 1 or 4 modulo 6.

An important insight is that if $b$ is odd and $c=2$, then after four iterations of $A$, that will remain the case. This allows one to define a configuration that eliminates the $c$ parameter and whose rules use a modulus of 81.

In May 2024, Iijil shared a 7-state, 2-symbol machine, 0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB (bbch), that has the same behaviour as Bigfoot.

Trajectory

After 69 steps, Bigfoot will reach the configuration $A(2,1,2)$ before the Collatz-like rules are repeatedly applied. Simulations of Bigfoot have shown that after 24000000 rule steps, we have $a=3999888$. Here are the first few: $$\begin{array}{l}A(2,1,2)\stackrel{49}{\to }A(3,1,3)\stackrel{59}{\to }A(4,2,3)\stackrel{109}{\to }A(3,6,2)\stackrel{221}{\to }A(3,9,2)\stackrel{379}{\to }A(3,11,5)\stackrel{597}{\to }A(3,18,3)\to \cdots \end{array}$$ There exists a heuristic argument for Bigfoot being probviously non-halting. By only considering the rules for which $a$ changes, one may notice that the trajectory of $a$ values can be approximated by a random walk in which at each step, the walker moves +1 with probability $\frac{2}{3}$ or moves -1 with probability $\frac{1}{3}$, starting at position 2. If $P(n)$ is the probability that the walker will reach position -1 from position $n$, then $P(n)=\frac{1}{3}P(n-1)+\frac{2}{3}P(n+1)$. Solutions to this recurrence relation come in the form $P(n)=c_0{2}^{-n}+c_1$, which after applying the appropriate boundary conditions reduces to $P(n)=2^{-(n+1)}$. As a result, if the walker gets to position 3999888, then the probability of it ever reaching position -1 would be $2^{-3999889}\approx 2.697\times 10^{-1204087}$.