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.

Analysis

Let $A(a,b,c):=0^{\infty }\;12^{a}\;1^{2b}\;{\textrm {<A}}\;1^{2c}\;0^{\infty }$. Then,

$${\begin{array}{|l l l|}\hline A(a,6b,c)&\xrightarrow {4a+(2b+1)48b+(12b+1)2c+13} &A(a,8b+c-1,2),\\A(a,6b+1,c)&\xrightarrow {4a+(6b+5)16b+(4b+1)6c+29} &A(a+1,8b+c-1,3),\\A(0,6b+2,c)&\xrightarrow {(b+1)96b+(3b+1)8c+18} &0^{\infty }\;{\textrm {<C}}\;1^{16b+2c+5}\;2\;0^{\infty },\\A(a,6b+2,c)&\xrightarrow {4a+(2b+3)48b+(12b+7)2c+51} &A(a-1,8b+c+3,2){\text{ if }}a\geq 1,\\A(a,6b+3,c)&\xrightarrow {4a+(6b+7)16b+(12b+5)2c+91} &A(a,8b+c+1,5),\\A(a,6b+4,c)&\xrightarrow {4a+(2b+3)48b+(12b+7)2c+63} &A(a+1,8b+c+3,2),\\A(a,6b+5,c)&\xrightarrow {4a+(6b+11)16b+(4b+3)6c+103} &A(a,8b+c+5,3).\\\hline \end{array}}$$

Proof

For now, we will work with the slightly different configuration $A'(a,b,c):=0^{\infty }\;12^{a}\;1^{b}\;{\textrm {<A}}\;1^{c}\;0^{\infty }$. Consider the partial configuration $P(m,n):=1^{m}\;{\textrm {<A}}\;1^{n}\;0^{\infty }$. We first require the following shift rule:

$${\begin{array}{|l|}\hline {\textrm {A>}}\;1^{s}\xrightarrow {s} 2^{s}\;{\textrm {A>}}\\\hline \end{array}}$$

Using this shift rule, we get $1^{m-1}\;2^{n+1}\;{\textrm {A>}}\;0^{\infty }$ after $n+1$ steps, followed by $1^{m-1}\;2^{n}\;{\textrm {<C}}\;122\;0^{\infty }$ four steps later. Observing that $22\;{\textrm {<C}}$ becomes ${\textrm {<C}}\;11$ in two steps leads to another shift rule:

$${\begin{array}{|l|}\hline 2^{2s}\;{\textrm {<C}}\xrightarrow {2s} {\textrm {<C}}\;1^{2s}\\\hline \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\ (\operatorname {mod} 2)$, then what follows is:
   $${\begin{array}{|l|}\hline 1^{m-1}\;2^{n}\;{\textrm {<C}}\;122\;0^{\infty }\xrightarrow {n} 1^{m-1}\;{\textrm {<C}}\;1^{n+1}\;22\;0^{\infty }\xrightarrow {4} 1^{m-3}\;{\textrm {<A}}\;1^{n+3}\;22\;0^{\infty }\xrightarrow {n+4} \\1^{m-4}\;2^{n+4}\;{\textrm {A>}}\;22\;0^{\infty }\xrightarrow {1} 1^{m-4}\;2^{n+4}\;{\textrm {<C}}\;12\;0^{\infty }\xrightarrow {n+4} 1^{m-4}\;{\textrm {<C}}\;1^{n+5}\;2\;0^{\infty }\xrightarrow {4} \\1^{m-6}\;{\textrm {<A}}\;1^{n+7}\;2\;0^{\infty }\xrightarrow {n+8} 1^{m-7}\;2^{n+8}\;{\textrm {A>}}\;2\;0^{\infty }\xrightarrow {1} 1^{m-7}\;2^{n+8}\;{\textrm {<C}}\;1\;0^{\infty }\xrightarrow {n+8} \\1^{m-7}\;{\textrm {<C}}\;1^{n+9}\;0^{\infty }\xrightarrow {4} 1^{m-9}\;{\textrm {<A}}\;1^{n+11}\;0^{\infty }\\\hline \end{array}}$$
   Therefore, we have
   $${\begin{array}{|l|}\hline P(m,n)\xrightarrow {6n+43} P(m-9,n+11){\text{ if }}m\geq 9{\text{ and }}n\equiv 0\ (\operatorname {mod} 2).\\\hline \end{array}}$$
2. If $n\equiv 1\ (\operatorname {mod} 2)$, then what follows is:
   $${\begin{array}{|l|}\hline 1^{m-1}\;2^{n}\;{\textrm {<C}}\;122\;0^{\infty }\xrightarrow {n-1} 1^{m-1}\;2\;{\textrm {<C}}\;1^{n}\;22\;0^{\infty }\xrightarrow {1} 1^{m-1}\;{\textrm {<A}}\;1^{n+1}\;22\;0^{\infty }\xrightarrow {n+2} \\1^{m-2}\;2^{n+2}\;{\textrm {A>}}\;22\;0^{\infty }\xrightarrow {1} 1^{m-2}\;2^{n+2}\;{\textrm {<C}}\;12\;0^{\infty }\xrightarrow {n+1} 1^{m-2}\;2\;{\textrm {<C}}\;1^{n+2}\;2\;0^{\infty }\xrightarrow {1} \\1^{m-2}\;{\textrm {<A}}\;1^{n+3}\;2\;0^{\infty }\xrightarrow {n+4} 1^{m-3}\;2^{n+4}\;{\textrm {A>}}\;2\;0^{\infty }\xrightarrow {1} 1^{m-3}\;2^{n+4}\;{\textrm {<C}}\;1\;0^{\infty }\xrightarrow {n+3} \\1^{m-3}\;2\;{\textrm {<C}}\;1^{n+4}\;0^{\infty }\xrightarrow {1} 1^{m-3}\;{\textrm {<A}}\;1^{n+5}\;0^{\infty }\\\hline \end{array}}$$
   Therefore, we have

$${\begin{array}{|l|}\hline P(m,n)\xrightarrow {6n+19} P(m-3,n+5){\text{ if }}m\geq 3{\text{ and }}n\equiv 1\ (\operatorname {mod} 2).\\\hline \end{array}}$$

From this we know that Bigfoot's behaviour depends on the value of $b$ modulo 12, and with $A'(a,b,c)$ we have $P(b,c)$. The following shift rules will be useful:

$${\begin{array}{|l|l|l|}\hline 12^{s}\;{\textrm {<A}}\xrightarrow {2s} {\textrm {<A}}\;21^{s}&{\textrm {B>}}\;1^{s}\xrightarrow {s} 1^{s}\;{\textrm {B>}}&{\textrm {B>}}\;2^{s}\xrightarrow {s} 2^{s}\;{\textrm {B>}}\\\hline \end{array}}$$

Only even values of $b$ and $c$ are relevant, so there remain six possible scenarios:

1. If $b\equiv 0\ (\operatorname {mod} 12)$, then in ${\textstyle {\displaystyle \sum _{i=0}^{b/12-1}}(6(16i+c)+43+6(16i+11+c)+19)={\displaystyle \sum _{i=0}^{b/12-1}}4(48i+3c+32)={\frac {2}{3}}b^{2}+{\frac {8}{3}}b+bc}$ steps we arrive at ${\textstyle P{\Big (}0,16\times {\frac {b}{12}}+c{\Big )}}$, or $0^{\infty }\;12^{a}\;{\textrm {<A}}\;1^{4b/3+c}\;0^{\infty }$ when considering the complete configuration. What follows is:
   $${\begin{array}{|l|}\hline 0^{\infty }\;12^{a}\;{\textrm {<A}}\;1^{4b/3+c}\;0^{\infty }\xrightarrow {2a} 0^{\infty }\;{\textrm {<A}}\;21^{a}\;1^{4b/3+c}\;0^{\infty }\xrightarrow {1} 0^{\infty }\;1\;{\textrm {B>}}\;21^{a}\;1^{4b/3+c}\;0^{\infty }\xrightarrow {2a+4b/3+c} \\0^{\infty }\;12^{a}\;1^{4b/3+c+1}\;{\textrm {B>}}\;0^{\infty }\xrightarrow {12} 0^{\infty }\;12^{a}\;1^{4b/3+c-2}\;{\textrm {<A}}\;1^{4}\;0^{\infty }\\\hline \end{array}}$$
   This means that if ${\textstyle {\frac {4}{3}}b+c\geq 2}$, then we will reach ${\textstyle A'{\Big (}a,{\frac {4}{3}}b+c-2,4{\Big )}}$ in ${\textstyle 4a+{\frac {2}{3}}b^{2}+4b+bc+c+13}$ steps.
2. If $b\equiv 2\ (\operatorname {mod} 12)$, then in ${\textstyle {\displaystyle \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 ${\textstyle P{\Big (}2,{\frac {4(b-2)}{3}}+c{\Big )}}$, or $0^{\infty }\;12^{a}\;11\;{\textrm {<A}}\;1^{(4b-2)/3+c}\;0^{\infty }$. What follows is:
   $${\begin{array}{|l|}\hline 0^{\infty }\;12^{a}\;11\;{\textrm {<A}}\;1^{4(b-2)/3+c}\;0^{\infty }\xrightarrow {4(b-2)/3+c+1} 0^{\infty }\;12^{a}\;1\;2^{4(b-2)/3+c+1}\;{\textrm {A>}}\;0^{\infty }\xrightarrow {4} \\0^{\infty }\;12^{a}\;1\;2^{4(b-2)/3+c}\;{\textrm {<C}}\;122\;0^{\infty }\xrightarrow {4(b-2)/3+c} 0^{\infty }\;12^{a}\;1\;{\textrm {<C}}\;1^{4(b-2)/3+c+1}\;22\;0^{\infty }\xrightarrow {1} \\0^{\infty }\;12^{a}\;{\textrm {<A}}\;2\;1^{4(b-2)/3+c+1}\;22\;0^{\infty }\xrightarrow {2a} 0^{\infty }\;{\textrm {<A}}\;21^{a}\;2\;1^{4(b-2)/3+c+1}\;22\;0^{\infty }\xrightarrow {1} \\0^{\infty }\;1\;{\textrm {B>}}\;21^{a}\;2\;1^{4(b-2)/3+c+1}\;22\;0^{\infty }\xrightarrow {4(b-2)/3+2a+c+4} 0^{\infty }\;12^{a+1}\;1^{4(b-2)/3+c+1}\;22\;{\textrm {B>}}\;0^{\infty }\xrightarrow {18} \\0^{\infty }\;12^{a+1}\;1^{4(b-2)/3+c-2}\;{\textrm {<A}}\;1^{6}\;0^{\infty }\\\hline \end{array}}$$
   This means that if ${\textstyle {\frac {4(b-2)}{3}}+c\geq 2}$, then we will reach ${\textstyle A'{\Big (}a+1,{\frac {4b-14}{3}}+c,6{\Big )}}$ in ${\textstyle 4a+{\frac {2}{3}}b^{2}+4b+bc+c+{\frac {55}{3}}}$ steps.
3. If $b\equiv 4\ (\operatorname {mod} 12)$, then in ${\textstyle {\frac {2}{3}}b^{2}-{\frac {8}{3}}b+bc-4c}$ steps we arrive at ${\textstyle P{\Big (}4,{\frac {4(b-4)}{3}}+c{\Big )}}$, or $0^{\infty }\;12^{a}\;1111\;{\textrm {<A}}\;1^{4(b-4)/3+c}\;0^{\infty }$. What follows is:
   $${\begin{array}{|l|}\hline 0^{\infty }\;12^{a}\;1111\;{\textrm {<A}}\;1^{4(b-4)/3+c}\;0^{\infty }\xrightarrow {(8b-14)/3+2c} 0^{\infty }\;12^{a}\;11\;{\textrm {<A}}\;2\;1^{4(b-4)/3+c+1}\;22\;0^{\infty }\xrightarrow {3} \\0^{\infty }\;12^{a}\;1\;{\textrm {<A}}\;1^{4(b-4)/3+c+3}\;22\;0^{\infty }\xrightarrow {4(b-4)/3+c+4} 0^{\infty }\;12^{a}\;2^{4(b-4)/3+c+4}\;{\textrm {A>}}\;22\;0^{\infty }\xrightarrow {1} \\0^{\infty }\;12^{a}\;2^{4(b-4)/3+c+4}\;{\textrm {<C}}\;12\;0^{\infty }\xrightarrow {4(b-4)/3+c+4} 0^{\infty }\;12^{a}\;{\textrm {<C}}\;1^{4(b-4)/3+c+5}\;2\;0^{\infty }\xrightarrow {1} \\0^{\infty }\;12^{a-1}\;1\;{\textrm {<A}}\;1^{4(b-4)/3+c+6}\;2\;0^{\infty }\xrightarrow {4(b-4)/3+c+7} 0^{\infty }\;12^{a-1}\;2^{4(b-4)/3+c+7}\;{\textrm {A>}}\;2\;0^{\infty }\xrightarrow {1} \\0^{\infty }\;12^{a-1}\;2^{4(b-4)/3+c+7}\;{\textrm {<C}}\;1\;0^{\infty }\xrightarrow {4(b-4)/3+c+6} 0^{\infty }\;12^{a-1}\;2\;{\textrm {<C}}\;1^{4(b-4)/3+c+7}\;0^{\infty }\xrightarrow {1} \\0^{\infty }\;12^{a-1}\;{\textrm {<A}}\;1^{4(b-4)/3+c+8}\;0^{\infty }\xrightarrow {2(a-1)} 0^{\infty }\;{\textrm {<A}}\;21^{a-1}\;1^{4(b-4)/3+c+8}\;0^{\infty }\xrightarrow {1} \\0^{\infty }\;1\;{\textrm {B>}}\;21^{a-1}\;1^{4(b-4)/3+c+8}\;0^{\infty }\xrightarrow {2a+4(b-4)/3+c+6} 0^{\infty }\;12^{a-1}\;1^{4(b-4)/3+c+9}\;{\textrm {B>}}\;0^{\infty }\xrightarrow {12} \\0^{\infty }\;12^{a-1}\;1^{4(b-4)/3+c+6}\;{\textrm {<A}}\;1^{4}\;0^{\infty }\\\hline \end{array}}$$
   This means that if $a=0$, then Bigfoot will reach the undefined C0 transition with the configuration $0^{\infty }\;{\textrm {<C}}\;1^{(4b-1)/3+c}\;2\;0^{\infty }$ in ${\textstyle {\frac {2}{3}}b^{2}+{\frac {8}{3}}b+bc-{\frac {10}{3}}}$ steps. Otherwise, it will proceed to reach ${\textstyle A'{\Big (}a-1,{\frac {4b+2}{3}}+c,4{\Big )}}$ in ${\textstyle 4a+{\frac {2}{3}}b^{2}+{\frac {20}{3}}b+bc+3c+{\frac {41}{3}}}$ steps.
4. If $b\equiv 6\ (\operatorname {mod} 12)$, then in ${\textstyle {\frac {2}{3}}b^{2}-{\frac {16}{3}}b+bc-6c+8}$ steps we arrive at ${\textstyle P{\Big (}6,{\frac {4(b-6)}{3}}+c{\Big )}}$, or $0^{\infty }\;12^{a}\;111111\;{\textrm {<A}}\;1^{4(b-6)/3+c}\;0^{\infty }$. What follows is:
   $${\begin{array}{|l|}\hline 0^{\infty }\;12^{a}\;111111\;{\textrm {<A}}\;1^{4(b-6)/3+c}\;0^{\infty }\xrightarrow {16b/3+4c-14} 0^{\infty }\;12^{a}\;11\;{\textrm {<C}}\;1^{4(b-6)/3+c+5}\;2\;0^{\infty }\xrightarrow {4} \\0^{\infty }\;12^{a}\;{\textrm {<A}}\;1^{4(b-6)/3+c+7}\;2\;0^{\infty }\xrightarrow {2a} 0^{\infty }\;{\textrm {<A}}\;21^{a}\;1^{4(b-6)/3+c+7}\;2\;0^{\infty }\xrightarrow {1} \\0^{\infty }\;1\;{\textrm {B>}}\;21^{a}\;1^{4(b-6)/3+c+7}\;2\;0^{\infty }\xrightarrow {2a+4(b-6)/3+c+8} 0^{\infty }\;12^{a}\;1^{4(b-6)/3+c+8}\;2\;{\textrm {B>}}\;0^{\infty }\xrightarrow {60} \\0^{\infty }\;12^{a}\;1^{4(b-6)/3+c+2}\;{\textrm {<A}}\;1^{10}\;0^{\infty }\\\hline \end{array}}$$
   This means that we will reach ${\textstyle A'{\Big (}a,{\frac {4}{3}}b+c-6,10{\Big )}}$ in ${\textstyle 4a+{\frac {2}{3}}b^{2}+{\frac {4}{3}}b+bc-c+59}$ steps.
5. If $b\equiv 8\ (\operatorname {mod} 12)$, then in ${\textstyle {\frac {2}{3}}b^{2}-8b+bc-8c+{\frac {64}{3}}}$ steps we arrive at ${\textstyle P{\Big (}8,{\frac {4(b-8)}{3}}+c{\Big )}}$, or $0^{\infty }\;12^{a}\;1^{8}\;{\textrm {<A}}\;1^{4(b-8)/3+c}\;0^{\infty }$. What follows is:
   $${\begin{array}{|l|}\hline 0^{\infty }\;12^{a}\;1^{8}\;{\textrm {<A}}\;1^{4(b-8)/3+c}\;0^{\infty }\xrightarrow {(16b-62)/3+4c} 0^{\infty }\;12^{a}\;11\;{\textrm {<A}}\;1^{4(b-8)/3+c+7}\;2\;0^{\infty }\xrightarrow {4(b-8)/3+c+8} \\0^{\infty }\;12^{a}\;1\;2^{4(b-8)/3+c+8}\;{\textrm {A>}}\;2\;0^{\infty }\xrightarrow {1} 0^{\infty }\;12^{a}\;1\;2^{4(b-8)/3+c+8}\;{\textrm {<C}}\;1\;0^{\infty }\xrightarrow {4(b-8)/3+c+8} \\0^{\infty }\;12^{a}\;1\;{\textrm {<C}}\;1^{4(b-8)/3+c+9}\;0^{\infty }\xrightarrow {1} 0^{\infty }\;12^{a}\;{\textrm {<A}}\;2\;1^{4(b-8)/3+c+9}\;0^{\infty }\xrightarrow {2a} \\0^{\infty }\;{\textrm {<A}}\;21^{a}\;2\;1^{4(b-8)/3+c+9}\;0^{\infty }\xrightarrow {1} 0^{\infty }\;1\;{\textrm {B>}}\;21^{a}\;2\;1^{4(b-8)/3+c+9}\;0^{\infty }\xrightarrow {2a+4(b-8)/3+c+10} \\0^{\infty }\;12^{a+1}\;1^{4(b-8)/3+c+9}\;{\textrm {B>}}\;0^{\infty }\xrightarrow {12} 0^{\infty }\;12^{a+1}\;1^{4(b-8)/3+c+6}\;{\textrm {<A}}\;1^{4}\;0^{\infty }\\\hline \end{array}}$$
   This means that we will reach ${\textstyle A'{\Big (}a+1,{\frac {4b-14}{3}}+c,4{\Big )}}$ in ${\textstyle 4a+{\frac {2}{3}}b^{2}+{\frac {4}{3}}b+bc-c+{\frac {29}{3}}}$ steps.
6. If $b\equiv 10\ (\operatorname {mod} 12)$, then in ${\textstyle {\frac {2}{3}}b^{2}-{\frac {32}{3}}b+bc-10c+40}$ steps we arrive at ${\textstyle P{\Big (}10,{\frac {4(b-10)}{3}}+c{\Big )}}$, or $0^{\infty }\;12^{a}\;1^{10}\;{\textrm {<A}}\;1^{4(b-10)/3+c}\;0^{\infty }$. What follows is:
   $${\begin{array}{|l|}\hline 0^{\infty }\;12^{a}\;1^{10}\;{\textrm {<A}}\;1^{4(b-10)/3+c}\;0^{\infty }\xrightarrow {8b+6c-37} 0^{\infty }\;12^{a}\;1\;{\textrm {<A}}\;1^{4(b-10)/3+c+11}\;0^{\infty }\xrightarrow {4(b-10)/3+c+12} \\0^{\infty }\;12^{a}\;2^{4(b-10)/3+c+12}\;{\textrm {A>}}\;0^{\infty }\xrightarrow {4} 0^{\infty }\;12^{a}\;2^{4(b-10)/3+c+11}\;{\textrm {<C}}\;122\;0^{\infty }\xrightarrow {4(b-10)/3+c+10} \\0^{\infty }\;12^{a}\;2\;{\textrm {<C}}\;1^{4(b-10)/3+c+11}\;22\;0^{\infty }\xrightarrow {1} 0^{\infty }\;12^{a}\;{\textrm {<A}}\;1^{4(b-10)/3+c+12}\;22\;0^{\infty }\xrightarrow {2a} \\0^{\infty }\;{\textrm {<A}}\;12^{a}\;1^{4(b-10)/3+c+12}\;22\;0^{\infty }\xrightarrow {1} 0^{\infty }\;1\;{\textrm {B>}}\;12^{a}\;1^{4(b-10)/3+c+12}\;22\;0^{\infty }\xrightarrow {2a+4(b-10)/3+c+14} \\0^{\infty }\;12^{a}\;1^{4(b-10)/3+c+13}\;22\;{\textrm {B>}}\;0^{\infty }\xrightarrow {18} 0^{\infty }\;12^{a}\;1^{4(b-10)/3+c+10}\;{\textrm {<A}}\;1^{6}\;0^{\infty }\\\hline \end{array}}$$
   This means that we will reach ${\textstyle A'{\Big (}a,{\frac {4b-10}{3}}+c,6{\Big )}}$ in ${\textstyle 4a+{\frac {2}{3}}b^{2}+{\frac {4}{3}}b+bc-c+23}$ steps.

The information above can be summarized as

$$A'(a,b,c)\rightarrow {\begin{cases}A'{\Big (}a,{\frac {4}{3}}b+c-2,4{\Big )}&{\text{if }}b\equiv 0{\pmod {12}}{\text{ and }}{\frac {4}{3}}b+c\geq 2,\\A'{\Big (}a+1,{\frac {4b-14}{3}}+c,6{\Big )}&{\text{if }}b\equiv 2{\pmod {12}}{\text{ and }}{\frac {4(b-2)}{3}}+c\geq 2,\\0^{\infty }\;{\textrm {<C}}\;1^{(4b-1)/3+c}\;2\;0^{\infty }&{\text{if }}b\equiv 4{\pmod {12}}{\text{ and }}a=0,\\A'{\Big (}a-1,{\frac {4b+2}{3}}+c,4{\Big )}&{\text{if }}b\equiv 4{\pmod {12}}{\text{ and }}a>0,\\A'{\Big (}a,{\frac {4}{3}}b+c-6,10{\Big )}&{\text{if }}b\equiv 6{\pmod {12}},\\A'{\Big (}a+1,{\frac {4b-14}{3}}+c,4{\Big )}&{\text{if }}b\equiv 8{\pmod {12}},\\A'{\Big (}a,{\frac {4b-10}{3}}+c,6{\Big )}&{\text{if }}b\equiv 10{\pmod {12}}.\end{cases}}$$

Using the definitions of $A'$ and $A$ to transform these rules produces this:

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

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$ as one united formula:

$$\textstyle {\begin{array}{c}f(m,n)={\Big (}{\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){\Big )},\\\delta _{i}(m)={\Big \lfloor }{\frac {x-i}{6}}{\Big \rfloor }-{\Big \lfloor }{\frac {x-i-1}{6}}{\Big \rfloor }={\begin{cases}1&{\text{if }}x\equiv i{\pmod {6}},\\0&{\text{otherwise.}}\end{cases}}\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|}\hline A(2,1,2)\xrightarrow {49} A(3,1,3)\xrightarrow {59} A(4,2,3)\xrightarrow {109} A(3,6,2)\xrightarrow {221} A(3,9,2)\xrightarrow {379} A(3,11,5)\xrightarrow {597} A(3,18,3)\rightarrow \cdots \\\hline \end{array}}$$

There exists a heuristic argument for Bigfoot being probviously nonhalting. After removing the instances in which $a$ does not change, one notices that the trajectory of $a$ values can be approximated by a random walk in which at each step, the walker moves +1 with probability ${\textstyle {\frac {2}{3}}}$ or moves -1 with probability ${\textstyle {\frac {1}{3}}}$, starting at position 2. If $P(n)$ is the probability that the walker will reach position -1 from position $n$, then ${\textstyle P(n)={\frac {1}{3}}P(n-1)+{\frac {2}{3}}P(n+1)}$. Solutions to this recurrence relation come in the form ${\textstyle P(n)=c_{0}2^{-n}+c_{1}}$, which after applying the appropriate boundary conditions reduces to ${\textstyle 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 ${\textstyle 2^{-3999889}\approx 2.697\times 10^{-1204087}}$.