Bigfoot: Difference between revisions

Revision as of 20:52, 28 March 2025

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.^[1]

	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} 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$ as one united formula: $\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{x - i}{6} ⌋ - ⌊ \frac{x - i - 1}{6} ⌋ = {\begin{cases} 1 & if x \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]

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.^[2]

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 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 $\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.
↑ P. Michel, "Historical survey of Busy Beavers".

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

[2] P. Michel, "Historical survey of Busy Beavers".

[1]

[2]

@@ Line 36: / Line 36: @@
 From this we know that Bigfoot's behaviour depends on the value of <math>b</math> modulo 12, and with <math>A'(a,b,c)</math> we have <math>P(b,c)</math>. The following shift rules will be useful:
 <math display="block">\begin{array}{|l|l|l|}\hline12^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}</math>
-Because only even values of <math>b</math> are receiving focus, there remain six possible scenarios:
+Only even values of <math>b</math> and <math>c</math> are relevant, so there remain six possible scenarios:
 #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.
@@ Line 47: / Line 47: @@
 Using the definitions of <math>A'</math> and <math>A</math> to transform these rules produces this:
 <math display="block">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}</math>
-Substituting <math>b\leftarrow6b+k</math>, where <math>k</math> is the remainder for each case yields the final result.
+Substituting <math>b\leftarrow6b+k</math> where <math>k</math> is the remainder for each case yields the final result.
 </div></div>
-Using floor and ceiling functions, it is possible to describe the behaviour of <math>b</math> and <math>c</math> as one united formula:
+Using the floor function, it is possible to describe the behaviour of <math>b</math> and <math>c</math> as one united formula:
 <math display="block">\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}</math>
 In effect, the halting problem for Bigfoot is about whether through enough iterations of <math>f(m,n)</math> we encounter more <math>m</math> values that are congruent to 2 modulo 6 than ones that are congruent to 1 or 4 modulo 6.
-It turns out that if <math>b</math> is odd and <math>c=2</math> then after four iterations of <math>A</math>, that will remain the case. This allows one to define a configuration that eliminates the <math>c</math> parameter and whose rules use a modulus of 81.<ref name="b"></ref>
+An important insight is that if <math>b</math> is odd and <math>c=2</math>, then after four iterations of <math>A</math>, that will remain the case. This allows one to define a configuration that eliminates the <math>c</math> parameter and whose rules use a modulus of 81.<ref name="b"></ref>
 In May 2024, Iijil shared a 7-state, 2-symbol machine, {{TM|0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB}}, that has the same behaviour as Bigfoot.<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
 == Trajectory ==
-After 69 steps Bigfoot will reach the configuration <math>A(2,1,2)</math> before the [[Collatz-like]] rules are repeatedly applied. Simulations of Bigfoot have shown that after 24000000 rule steps, we have <math>a=3999888</math>. Here are the first few:
+After 69 steps, Bigfoot will reach the configuration <math>A(2,1,2)</math> before the [[Collatz-like]] rules are repeatedly applied. Simulations of Bigfoot have shown that after 24000000 rule steps, we have <math>a=3999888</math>. Here are the first few:
 <math display="block">\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}</math>
 There exists a heuristic argument for Bigfoot being [[probviously]] nonhalting. After removing the instances in which <math>a</math> does not change, one notices that the trajectory of <math>a</math> values can be approximated by a random walk in which at each step, the walker moves +1 with probability <math display="inline">\frac{2}{3}</math> or moves -1 with probability <math display="inline">\frac{1}{3}</math>, starting at position 2. If <math>P(n)</math> is the probability that the walker will reach position -1 from position <math>n</math>, then <math display="inline">P(n)=\frac{1}{3}P(n-1)+\frac{2}{3}P(n+1)</math>. Solutions to this recurrence relation come in the form <math display="inline"> P(n)=c_02^{-n}+c_1</math>, which after applying the appropriate boundary conditions reduces to <math display="inline">P(n)=2^{-(n+1)}</math>. As a result, if the walker gets to position 3999888, then the probability of it ever reaching position -1 would be <math display="inline">2^{-3999889}\approx 2.697\times 10^{-1204087}</math>.

Bigfoot: Difference between revisions

Revision as of 20:52, 28 March 2025

Analysis

Trajectory

References

Navigation menu

Search