Bigfoot: Difference between revisions

Revision as of 19:45, 7 October 2025

Unsolved problem:

Does Bigfoot run forever?

Bigfoot (1RB2RA1LC_2LC1RB2RB_---2LA1LA (bbch)) 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.^[1]

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

The transition table of Bigfoot.

In May of 2024, Iijil compiled Bigfoot into a 7-state 2-symbol machine 0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB (bbch).

Analysis

Let $A (a, b, c) : = 0^{\infty} 1 2^{a} 1^{2 b} < A 1^{2 c} 0^{\infty}$ . Then, $\begin{array}{lll} A (a, 6 b, c) & \overset{4 a + (2 b + 1) 48 b + (12 b + 1) 2 c + 13}{\to} & A (a, 8 b + c - 1, 2), \\ A (a, 6 b + 1, c) & \overset{4 a + (6 b + 5) 16 b + (4 b + 1) 6 c + 29}{\to} & A (a + 1, 8 b + c - 1, 3), \\ A (0, 6 b + 2, c) & \overset{(b + 1) 96 b + (3 b + 1) 8 c + 18}{\to} & 0^{\infty} < C 1^{16 b + 2 c + 5} 2 0^{\infty}, \\ A (a, 6 b + 2, c) & \overset{4 a + (2 b + 3) 48 b + (12 b + 7) 2 c + 51}{\to} & A (a - 1, 8 b + c + 3, 2) if a \geq 1, \\ A (a, 6 b + 3, c) & \overset{4 a + (6 b + 7) 16 b + (12 b + 5) 2 c + 91}{\to} & A (a, 8 b + c + 1, 5), \\ A (a, 6 b + 4, c) & \overset{4 a + (2 b + 3) 48 b + (12 b + 7) 2 c + 63}{\to} & A (a + 1, 8 b + c + 3, 2), \\ A (a, 6 b + 5, c) & \overset{4 a + (6 b + 11) 16 b + (4 b + 3) 6 c + 103}{\to} & A (a, 8 b + c + 5, 3) . \end{array}$

Proof

For now, we will work with the slightly different configuration $A^{'} (a, b, c) : = 0^{\infty} 1 2^{a} 1^{b} < A 1^{c} 0^{\infty}$ . Consider the partial configuration $P (m, n) : = 1^{m} < A 1^{n} 0^{\infty}$ . We first require the following shift rule: $\begin{array}{l} A > 1^{s} \overset{s}{\to} 2^{s} A > \end{array}$ Using this shift rule, we get $1^{m - 1} 2^{n + 1} A > 0^{\infty}$ after $n + 1$ steps, followed by $1^{m - 1} 2^{n} < C 122 0^{\infty}$ four steps later. Observing that $22 < C$ becomes $< C 11$ in two steps leads to another shift rule: $\begin{array}{l} 2^{2 s} < C \overset{2 s}{\to} < C 1^{2 s} \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:

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

$\begin{array}{l} P (m, n) \overset{6 n + 19}{\to} P (m - 3, n + 5) if m \geq 3 and n \equiv 1 (\mod 2) . \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}{lll} 1 2^{s} < A \overset{2 s}{\to} < A 2 1^{s} & B > 1^{s} \overset{s}{\to} 1^{s} B > & B > 2^{s} \overset{s}{\to} 2^{s} B > \end{array}$ Only even values of $b$ and $c$ are relevant, so there remain six possible scenarios:

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

The information above can be summarized as $A^{'} (a, b, c) \to {\begin{cases} A^{'} (a, \frac{4}{3} b + c - 2, 4) & if b \equiv 0 (\mod 12) and \frac{4}{3} b + c \geq 2, \\ A^{'} (a + 1, \frac{4 b - 14}{3} + c, 6) & if b \equiv 2 (\mod 12) and \frac{4 (b - 2)}{3} + c \geq 2, \\ 0^{\infty} < C 1^{(4 b - 1) / 3 + c} 2 0^{\infty} & if b \equiv 4 (\mod 12) and a = 0, \\ A^{'} (a - 1, \frac{4 b + 2}{3} + c, 4) & if b \equiv 4 (\mod 12) and a > 0, \\ A^{'} (a, \frac{4}{3} b + c - 6, 10) & if b \equiv 6 (\mod 12), \\ A^{'} (a + 1, \frac{4 b - 14}{3} + c, 4) & if b \equiv 8 (\mod 12), \\ A^{'} (a, \frac{4 b - 10}{3} + c, 6) & if b \equiv 10 (\mod 12) . \end{cases}$ Using the definitions of $A^{'}$ and $A$ to transform these rules produces this: $A (a, b, c) \to {\begin{cases} A (a, \frac{4}{3} b + c - 1, 2) & if b \equiv 0 (\mod 6) and \frac{4}{3} b + c \geq 1, \\ A (a + 1, \frac{4 b - 7}{3} + c, 3) & if b \equiv 1 (\mod 6) and \frac{4 (b - 1)}{3} + c \geq 1, \\ 0^{\infty} < C 1^{(8 b - 1) / 3 + 2 c} 2 0^{\infty} & if b \equiv 2 (\mod 6) and a = 0, \\ A (a - 1, \frac{4 b + 1}{3} + c, 2) & if b \equiv 2 (\mod 6) and a > 0, \\ A (a, \frac{4}{3} b + c - 3, 5) & if b \equiv 3 (\mod 6), \\ A (a + 1, \frac{4 b - 7}{3} + c, 2) & if b \equiv 4 (\mod 6), \\ A (a, \frac{4 b - 5}{3} + c, 3) & if b \equiv 5 (\mod 6) . \end{cases}$ Substituting $b \leftarrow 6 b + 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{4 m - 3 - 4 (δ_{1} (m) - δ_{2} (m) + δ_{4} (m)) - 2 (3 δ_{3} (m) + δ_{5} (m))}{3} + n, 2 + δ_{1} (m) + 3 δ_{3} (m) + δ_{5} (m)), \\ δ_{i} (m) = ⌊ \frac{m - i}{6} ⌋ - ⌊ \frac{m - i - 1}{6} ⌋ = {\begin{cases} 1 & if m \equiv i (\mod 6), \\ 0 & 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.^[1]

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) \overset{49}{\to} A (3, 1, 3) \overset{59}{\to} A (4, 2, 3) \overset{109}{\to} A (3, 6, 2) \overset{221}{\to} A (3, 9, 2) \overset{379}{\to} A (3, 11, 5) \overset{597}{\to} A (3, 18, 3) \to \dots \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 1 0^{- 1204087}$ .

References

↑ ^1.0 ^1.1 S. Ligocki, "BB(3, 3) is Hard (Bigfoot) (2024). Accessed 22 July 2024.

[b-1] 1.0 ^1.1 S. Ligocki, "BB(3, 3) is Hard (Bigfoot) (2024). Accessed 22 July 2024.

[1]

@@ Line 25: / Line 25: @@
 == Analysis ==
-Let <math>A(a,b,c):=0^\infty\;12^a\;1^{2b}\;\textrm{<A}\;1^{2c}\;0^\infty</math>. Then,
+Let <math>A(a,b,c):=0^\infty\;12^a\;1^{2b}\;<\text{A}\;1^{2c}\;0^\infty</math>. Then,
-<math display="block">\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\ge1,\\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}</math>
+<math display="block">\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\;<\text{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\ge1,\\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}</math>
 <div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">
 For now, we will work with the slightly different configuration <math>A'(a,b,c):=0^\infty\;12^a\;1^b\;\textrm{<A}\;1^c\;0^\infty</math>. Consider the partial configuration <math>P(m,n):=1^m\;\textrm{<A}\;1^n\;0^\infty</math>. We first require the following shift rule:
@@ Line 42: / Line 42: @@
 #If <math>b\equiv0\ (\operatorname{mod}12)</math>, then in <math display="inline">{\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</math> steps we arrive at <math display="inline">P\Big(0,16\times\frac{b}{12}+c\Big)</math>, or <math>0^\infty\;12^a\;\textrm{<A}\;1^{4b/3+c}\;0^\infty</math> when considering the complete configuration. What follows is:<math display="block">\begin{array}{|l|}\hline0^\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}</math>This means that if <math display="inline">\frac{4}{3}b+c\ge2</math>, then we will reach <math display="inline">A'\Big(a,\frac{4}{3}b+c-2,4\Big)</math> in <math display="inline">4a+\frac{2}{3}b^2+4b+bc+c+13</math> steps.
 #If <math>b\equiv2\ (\operatorname{mod}12)</math>, then in <math display="inline">{\displaystyle\sum_{i=0}^{(b-2)/12-1}}4(48i+3c+32)=\frac{2}{3}b^2+bc-2c-\frac{8}{3}</math> steps we arrive at <math display="inline">P\Big(2,\frac{4(b-2)}{3}+c\Big)</math>, or <math>0^\infty\;12^a\;11\;\textrm{<A}\;1^{(4b-2)/3+c}\;0^\infty</math>. What follows is:<math display="block">\begin{array}{|l|}\hline0^\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}</math>This means that if <math display="inline">\frac{4(b-2)}{3}+c\ge 2</math>, then we will reach <math display="inline">A'\Big(a+1,\frac{4b-14}{3}+c,6\Big)</math> in <math display="inline">4a+\frac{2}{3}b^2+4b+bc+c+\frac{55}{3}</math> steps.
-#If <math>b\equiv4\ (\operatorname{mod}12)</math>, then in <math display="inline>\frac{2}{3}b^2-\frac{8}{3}b+bc-4c</math> steps we arrive at <math display="inline">P\Big(4,\frac{4(b-4)}{3}+c\Big)</math>, or <math>0^\infty\;12^a\;1111\;\textrm{<A}\;1^{4(b-4)/3+c}\;0^\infty</math>. What follows is:<math display="block">\begin{array}{|l|}\hline0^\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}</math>This means that if <math>a=0</math>, then Bigfoot will reach the undefined <code>C0</code> transition with the configuration <math>0^\infty\;\textrm{<C}\;1^{(4b-1)/3+c}\;2\;0^\infty</math> in <math display="inline">\frac{2}{3}b^2+\frac{8}{3}b+bc-\frac{10}{3}</math> steps. Otherwise, it will proceed to reach <math display="inline">A'\Big(a-1,\frac{4b+2}{3}+c,4\Big)</math> in <math display="inline">4a+\frac{2}{3}b^2+\frac{20}{3}b+bc+3c+\frac{41}{3}</math> steps.
+#If <math>b\equiv4\ (\operatorname{mod}12)</math>, then in <math display="inline">\frac{2}{3}b^2-\frac{8}{3}b+bc-4c</math> steps we arrive at <math display="inline">P\Big(4,\frac{4(b-4)}{3}+c\Big)</math>, or <math>0^\infty\;12^a\;1111\;\textrm{<A}\;1^{4(b-4)/3+c}\;0^\infty</math>. What follows is:<math display="block">\begin{array}{|l|}\hline0^\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}</math>This means that if <math>a=0</math>, then Bigfoot will reach the undefined <code>C0</code> transition with the configuration <math>0^\infty\;\textrm{<C}\;1^{(4b-1)/3+c}\;2\;0^\infty</math> in <math display="inline">\frac{2}{3}b^2+\frac{8}{3}b+bc-\frac{10}{3}</math> steps. Otherwise, it will proceed to reach <math display="inline">A'\Big(a-1,\frac{4b+2}{3}+c,4\Big)</math> in <math display="inline">4a+\frac{2}{3}b^2+\frac{20}{3}b+bc+3c+\frac{41}{3}</math> steps.
 #If <math>b\equiv6\ (\operatorname{mod}12)</math>, then in <math display="inline">\frac{2}{3}b^2-\frac{16}{3}b+bc-6c+8</math> steps we arrive at <math display="inline">P\Big(6,\frac{4(b-6)}{3}+c\Big)</math>, or <math>0^\infty\;12^a\;111111\;\textrm{<A}\;1^{4(b-6)/3+c}\;0^\infty</math>. What follows is:<math display="block">\begin{array}{|l|}\hline0^\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}</math>This means that we will reach <math display="inline">A'\Big(a,\frac{4}{3}b+c-6,10\Big)</math> in <math display="inline">4a+\frac{2}{3}b^2+\frac{4}{3}b+bc-c+59</math> steps.
-#If <math>b\equiv8\ (\operatorname{mod}12)</math>, then in <math display="inline>\frac{2}{3}b^2-8b+bc-8c+\frac{64}{3}</math> steps we arrive at <math display="inline">P\Big(8,\frac{4(b-8)}{3}+c\Big)</math>, or <math>0^\infty\;12^a\;1^8\;\textrm{<A}\;1^{4(b-8)/3+c}\;0^\infty</math>. What follows is:<math display="block">\begin{array}{|l|}\hline0^\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}</math>This means that we will reach <math display="inline">A'\Big(a+1,\frac{4b-14}{3}+c,4\Big)</math> in <math display="inline">4a+\frac{2}{3}b^2+\frac{4}{3}b+bc-c+\frac{29}{3}</math> steps.
+#If <math>b\equiv8\ (\operatorname{mod}12)</math>, then in <math display="inline">\frac{2}{3}b^2-8b+bc-8c+\frac{64}{3}</math> steps we arrive at <math display="inline">P\Big(8,\frac{4(b-8)}{3}+c\Big)</math>, or <math>0^\infty\;12^a\;1^8\;\textrm{<A}\;1^{4(b-8)/3+c}\;0^\infty</math>. What follows is:<math display="block">\begin{array}{|l|}\hline0^\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}</math>This means that we will reach <math display="inline">A'\Big(a+1,\frac{4b-14}{3}+c,4\Big)</math> in <math display="inline">4a+\frac{2}{3}b^2+\frac{4}{3}b+bc-c+\frac{29}{3}</math> steps.
 #If <math>b\equiv10\ (\operatorname{mod}12)</math>, then in <math display="inline">\frac{2}{3}b^2-\frac{32}{3}b+bc-10c+40</math> steps we arrive at <math display="inline">P\Big(10,\frac{4(b-10)}{3}+c\Big)</math>, or <math>0^\infty\;12^a\;1^{10}\;\textrm{<A}\;1^{4(b-10)/3+c}\;0^\infty</math>. What follows is:<math display="block">\begin{array}{|l|}\hline0^\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}</math>This means that we will reach <math display="inline">A'\Big(a,\frac{4b-10}{3}+c,6\Big)</math> in <math display="inline">4a+\frac{2}{3}b^2+\frac{4}{3}b+bc-c+23</math> steps.
 The information above can be summarized as

Bigfoot: Difference between revisions

Revision as of 19:45, 7 October 2025

Analysis

Trajectory

References

Navigation menu

Search