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^{\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} to transform these rules produces this: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A(a,b,c)\rightarrow\begin{cases}A\Big(a,\frac{4}{3}b+c-1,2\Big)&\text{if }b\equiv0\pmod{6}\text{ and }\frac{4}{3}b+c\ge1,\\A\Big(a+1,\frac{4b-7}{3}+c,3\Big)&\text{if }b\equiv1\pmod{6}\text{ and }\frac{4(b-1)}{3}+c\ge1,\\0^\infty\;\textrm{<C}\;1^{(8b-1)/3+2c}\;2\;0^\infty&\text{if }b\equiv2\pmod{6}\text{ and }a=0,\\A\Big(a-1,\frac{4b+1}{3}+c,2\Big)&\text{if }b\equiv2\pmod{6}\text{ and }a>0,\\A\Big(a,\frac{4}{3}b+c-3,5\Big)&\text{if }b\equiv3\pmod{6},\\A\Big(a+1,\frac{4b-7}{3}+c,2\Big)&\text{if }b\equiv4\pmod{6},\\A\Big(a,\frac{4b-5}{3}+c,3\Big)&\text{if }b\equiv5\pmod{6}.\end{cases}} Substituting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b\leftarrow6b+k} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} is the remainder for each case yields the final result.

Using the floor function, it is possible to describe the behaviour of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} using a function that is not defined piecewise: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(m,n)} we encounter more Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} is odd and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=2} , then after four iterations of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , that will remain the case. This allows one to define a configuration that eliminates the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} parameter and whose rules use a modulus of 81.

Trajectory

After 69 steps, Bigfoot will reach the configuration Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A(2,1,2)} before the Collatz-like rules are repeatedly applied. Simulations of Bigfoot have shown that after 24000000 rule steps, we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=3999888} . Here are the first few: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 non-halting. By only considering the rules for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} changes, one may notice that the trajectory of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} values can be approximated by a random walk in which at each step, the walker moves +1 with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{2}{3}} or moves -1 with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{1}{3}} , starting at position 2. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(n)} is the probability that the walker will reach position -1 from position Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle P(n)=\frac{1}{3}P(n-1)+\frac{2}{3}P(n+1)} . Solutions to this recurrence relation come in the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle P(n)=c_02^{-n}+c_1} , which after applying the appropriate boundary conditions reduces to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 2^{-3999889}\approx 2.697\times 10^{-1204087}} .