BusyBeaverWiki - User contributions [en]

Pebble Automaton

2026-10-18T15:49:58Z

AlephSquirrel: /* Busy Beaver function */ p(7) proven

{{Stub}}
A pebble automaton is a type of [[cellular automaton]]. Each cell contains a non-negative number of pebbles, and the number of pebbles determines how many pebbles to push to each neighbor. Though pebble automata could be considered in any number of dimensions, investigation so far has primarily focused on 1 dimension.

Though it is unknown whether pebble automata are [[Turing-complete]], it is highly suspected that they are, since certain automata have been found to compute [[Collatz-like]] functions.

== Definition ==
A 1D pebble automaton is defined by three integer functions L(n), S(n) and R(n), defined over non-negative integers n, under the constraints:

* L(n) ≥ 0
* S(n) ≥ 0
* R(n) ≥ 0
* L(n) + S(n) + R(n) = n for all n

A simulation of a pebble automaton is represented by p(x, t), the number of pebbles at position x and time t. The initial configuration (t=0) has all n pebbles at x=0 and each generation, the pebbles are moved around according to the L, S, R rules:

* p(0, 0) = n
* p(x, 0) = 0 for x ≠ 0
* p(x, t+1) = R(p(x-1, t)) + S(p(x,t)) + L(p(x+1, t))

Informally, when a cell has n pebbles, it pushes L(n) to its left neighbor, R(n) to its right neighbor and S(n) stay.

Because the number of pebbles is preserved in each row, the maximum number of pebbles in one location is n. Therefore, a pebble automaton only needs to specify the function values up to n.

== Busy Beaver function ==
Let us define peBBle(n) as the maximum number of steps it takes for any pebble automaton to stabilize, starting from an initial state of n pebbles in a single cell.

Notation (long version): <code><nowiki>n --> L(n) | S(n) | R(n)</nowiki></code>

<code>0 --> 0 | 0 | 0</code> is omitted since it is forced by the definition.

The short version sets the rules in increasing order, separated by underscores, and removes <code>S(n)</code> since it can be obtained with the equation <code>S(N) = n - L(n) - R(n)</code>

If there are over 10 pebbles, we can extend the notation with letters, like with hexadecimal colors.
{| class="wikitable"
|+
!n
!peBBle(n)
!Champion
|-
|1
|0
|<code>00</code>
|-
|2
|1
|<code>00_01</code>
|-
|3
|3
|<code>00_01_20</code>
|-
|4
|6
|<code>00_01_20_03</code>
|-
|5
|11
|<code>00_11_03_21_04</code>
|-
|6
|17
|<code>00_11_03_21_40_15</code>
|-
|7
|28
|<code>00_11_03_21_10_33_61</code>
|-
|8
|≥ 63
|<code>00_11_03_21_50_30_24_70</code>
|-
|9
|≥ 63577
|<code>00_02_01_40_14_12_00_52_81</code>
|}

== Analysis ==

=== peBBle(5) ===
<syntaxhighlight line="1">
.5.....
.14....
.311...
..41...
.212...
1.3.1..
1..31..
1...4..
1..211.
1.1.21.
1.11.2.
1.111.1
</syntaxhighlight>

=== peBBle(6) ===
<syntaxhighlight line="1">
...6.....
..1.5....
..141....
..312....
...5.1...
..41.1...
.212.1...
1.3.11...
1..311...
1...41...
1..212...
1.1.3.1..
1.1..31..
1.1...4..
1.1..211.
1.1.1.21.
1.1.11.2.
1.1.111.1
</syntaxhighlight>

=== peBBle(7) ===
<syntaxhighlight line="1">
..7.......
.6.1......
3.31......
.3.4......
..511.....
.1411.....
.3121.....
..5.2.....
.141.1....
.312.1....
..5.11....
.14.11....
.31111....
..4111....
.21211....
1.3.21....
1..4.2....
1.212.1...
11.3.11...
11..311...
11...41...
11..212...
11.1.3.1..
11.1..31..
11.1...4..
11.1..211.
11.1.1.21.
11.1.11.2.
11.1.111.1
</syntaxhighlight>

=== peBBle(8) ===
<syntaxhighlight line="1">
.....8............
....71............
...215............
..1.7.............
..1214............
..2.411...........
.1.3121...........
.1..5.2...........
.1.5.1.1..........
.15..1.1..........
.6...1.1..........
33...1.1..........
.33..1.1..........
..33.1.1..........
...331.1..........
....34.1..........
....2411..........
...12221..........
...21212..........
..1.3.3.1.........
..1..3.31.........
..1...3.4.........
..1....511........
..1...5.11........
..1..5..11........
..1.5...11........
..15....11........
..6.....11........
.33.....11........
..33....11........
...33...11........
....33..11........
.....33.11........
......3311........
.......341........
.......242........
......12311.......
......2.141.......
.....1.1312.......
.....1.1.5.1......
.....1.15..1......
.....1.6...1......
.....133...1......
.....1.33..1......
.....1..33.1......
.....1...331......
.....1....34......
.....1....241.....
.....1...1222.....
.....1...21211....
.....1..1.3.21....
.....1..1..4.2....
.....1..1.212.1...
.....1..11.3.11...
.....1..11..311...
.....1..11...41...
.....1..11..212...
.....1..11.1.3.1..
.....1..11.1..31..
.....1..11.1...4..
.....1..11.1..211.
.....1..11.1.1.21.
.....1..11.1.11.2.
.....1..11.1.111.1
</syntaxhighlight>

=== peBBle(9) ===
The champion performs a [[Collatz-like]] function.

Analysis:
<syntaxhighlight line="1">
A(n) := 60^n3
B(n) := 60^n21

A(3k+1) -(20k+12)-> B(11k+5)
A(3k+2) -(8k+7)---> HALT
A(3k+3) -(20k+26)-> B(11k+12)

B(3k) -(8k+3)---> HALT
B(3k+1) -(20k+16)-> A(11k+7)
B(3k+2) -(20k+22)-> A(11k+11)

9 -(8)-> B(4) -(36)-> A(18) -(126)-> B(67) -(456)-> A(249) -(1666)-> B(914) -(6102)-> A(3355) -(22372)-> B(12303) -(32811)-> HALT
</syntaxhighlight>

== Cryptids ==

Though the overall Turing-completeness of pebble automata are unknown, an 86 pebble automaton has been produced by hand to display [[Hydra]]-like behavior:
<pre>
1 --> 0 | 1 | 0
2 --> 0 | 0 | 2
3 --> 0 | 0 | 3
5 --> 0 | 0 | 5
6 --> 0 | 6 | 0
7 --> 0 | 1 | 6
8 --> 0 | 2 | 6
9 --> 9 | 0 | 0
12 --> 12 | 0 | 0
14 --> 0 | 14 | 0
15 --> 6 | 9 | 0
17 --> 17 | 0 | 0
24 --> 0 | 24 | 0
25 --> 0 | 2 | 23
26 --> 0 | 1 | 25
27 --> 24 | 3 | 0
28 --> 26 | 2 | 0
29 --> 27 | 2 | 0
30 --> 27 | 3 | 0
32 --> 0 | 32 | 0
33 --> 0 | 33 | 0
35 --> 0 | 2 | 33
38 --> 0 | 3 | 35
39 --> 0 | 0 | 39
40 --> 0 | 0 | 40
41 --> 1 | 40 | 0
45 --> 0 | 39 | 6
78 --> 0 | 0 | 78
79 --> 0 | 79 | 0
84 --> 24 | 15 | 45
86 --> 1 | 1 | 84
</pre>
It may be interpreted in the following way:
<pre>
Let C(x, y) = $ 1 0^y 1 0^x 84 $
C(2k, y) --> C(7k + 3, y + 2)
C(2k + 1, y + 1) --> C(7k + 10, y)
C(2k + 1, 0) --> HALT

$$ --> C(0, 0) --> C(3, 2) --> C(17, 1) --> C(66, 0) --> C(234, 2)...
</pre>

== Sources ==

* Discord thread: https://discord.com/channels/960643023006490684/1535695107448381591
== External resources ==

* [https://gist.github.com/AlephSquirrel/9ada4b14b675d18fe8755b200b20509d Uiua simulator]
* [https://github.com/AzertyWasTaken/Busy-Beaver/tree/main/Pebble%20Automaton Enumerator GitHub repo]
* [https://azertywastaken.github.io/Busy-Beaver/Website/pebble-automaton.html Simulator website]

[[Category:Functions]]
[[Category:Stubs]]

Register machine

2026-10-15T19:07:44Z

AlephSquirrel: /* Cryptids */ Add Riemann Hypothesis

'''Register machines''', also known as '''Minsky machines''', are a [[Turing complete|Turing-complete]] model of computation.

Register machines contain a set of instructions and a set of registers. The instructions are labelled A, B, C, and so on. The registers are numbered 0, 1, 2, and so on. There are 2 types of instructions:

* inc(c, n) adds 1 to the register c then jumps to instruction n.
* dec(c, n, m) jumps to instruction m if register c equals 0, else subtract 1 to the register c then jump to instruction n.

The program halts if it reaches an undefined instruction. Here we label an undefined instruction with <code>*</code>.

== Register Busy Beaver ==
The Register Busy Beaver function, denoted MBB(n,r), returns the maximum number of instructions executed by a register machine with n instructions and r registers when started in instruction A and all registers initialized to 0. MBB(n) = MBB(n,n) (unlimited registers).
{| class="wikitable"
!Domain
!Halting Time
!Champion
|-
|MBB(1)
|1
|<code>0+*</code>
|-
|MBB(2)
|3
|<code>0+B_0-B*</code>
|-
|MBB(3)
|5
|<code>0+B_0+C_0-C*</code>
|-
|MBB(4)
|10
|<code>0+B_1+C_0-BD_1-C*</code>
|-
|MBB(5)
|24
|<code>0-DB_0+C_1-ED_1+A_1-B*</code>
|-
|MBB(6)
|49
|<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code>
|-
|MBB(7)
|231
|<code>0+B_0+C_0+D_1-GE_1+F_0-EC_1-A*</code>
|-
|MBB(8)
|≥ 3,394
|<code>0+B_0+C_1-GD_1+E_0-DF_2-HG_2+A_2-D*</code>
|-
|MBB(9)
|> 4.493 × 1074
|<code>0+B_0+C_1-HD_0-EG_0-FI_1+D_2+H_0+A_2-B*</code>
|-
|MBB(10)
|> 10↑↑4.03
|<code>0+B_1-AC_2-ED_1+E_1+F_0-DG_2-JH_2+I_1-HE_2-A*</code>
|-
|MBB(11)
|> 10↑↑17.74
|<code>0-KB_1-IC_1+D_1+E_2-CF_0-AG_0+H_1-GI_2+J_2+B_0-B*</code>
|}

== Analysis ==
MBB(7):
<pre>
Let A(x) = A:[x, 0]
A(2x) -> 9x+20 -> A(3x+4)
A(2x+1) -> 9x+27 -> halt

A(0) -> 20 -> A(4) -> 38 -> A(10) -> 65 -> A(19) -> 108 -> halt
</pre>

MBB(8):
<pre>Let S(z) = F:[0, 2z+1, z]
S(2k) -> 44k+19 -> S(5k+2)
S(2k+1) -> 4k+2 -> halt

A:[0, 0, 0] -> 44 -> S(4) -> 107 -> S(12) -> 283 -> S(32) -> 723 -> S(82) -> 1823 -> S(207) -> 414 -> halt</pre>

MBB(9):
<pre>Let A(x, y) = D:[x, 0, y]
A(2k, y) --(7k + 6)--> A(3k + 3, y + 1)
A(2k + 1, y + 1) --(7k + 5)--> A(3k + 1, y)
A(2k + 1, 0) --(3k + 3)--> *:[0, k, 0]

A:[0, 0, 0]
--(3)--> A(2, 0)
--(13)--> A(6, 1)
--(27)--> A(12, 2)
...
--(2753550047052785432549)--> A(1180092877308336613950, 31)
--(4130325070579178148831)--> A(1770139315962504920928, 32)
--(6195487605868767223254)--> A(2655208973943757381395, 33)
...
--(123361440505394191838159894807429323394336791980165278392551786831696080997)--> A(52869188788026082216354240631755424311858625134356547882522194356441177569, 0)
--(79303783182039123324531360947633136467787937701534821823783291534661766355)--> *[0, 26434594394013041108177120315877712155929312567178273941261097178220588784, 0]
MBB(9) ≥ 449388104698221698839011045369921106650798313642030657001438652029750007257</pre>

MBB(10):
<pre>
Let A(x) = E:[0, 0, x]
A(3k) --(28 × 2^k - 5k - 21)--> A(4 × 2^k - 2)
A(3k + 1) --(20 × 2^k - 5k - 16)--> *:[0, 4 × 2^k - 3, 0]
A(3k + 2) --(56 × 2^k - 5k - 23)--> A(8 × 2^k - 1)

Let t3 = 2^5864062014807
Let t4 = 2^((t3 + 4) / 3)

A:[0, 0, 0]
--(20)--> A(5)
--(84)--> A(15)
--(850)--> A(126)
--(123145302310681)--> A(17592186044414)
--(7 × t3 - 29320310074043)--> A(t3 - 1)
--(5 × t4 - 5 / 3 × t3 - 38 / 3)--> *:[0, t4 - 3, 0]
MBB(10) ≥ 5 × t4 + 16 / 3 × t3 + 281474976712738 / 3 > 10^^4.03
</pre>

MBB(11):
<pre>
Let A(x) = I:[x, 0, 0]
A(3k) --> A((20 * 4^k + 1)/3) if k ≥ 1
A(3k + 1) --> A((80 * 4^k + 1)/3) if k ≥ 1
A(3k + 2) --> *:[0, (20 * 4^k - 2)/3, 0] if k ≥ 1

A:[0, 0, 0] --(140)--> A(27)
--> A((20 * 4^9 + 1) / 3) = A(1747627)
--> A((80 * 4^582542 + 1) / 3) ≡ A(4897384) mod 3^15
--> A((80 * 4^1632461 + 1) / 3) ≡ A(2637523) mod 3^14
--> A((80 * 4^879174 + 1) / 3) ≡ A(813591) mod 3^13
--> A((20 * 4^271197 + 1) / 3) ≡ A(72385) mod 3^12
--> A((80 * 4^24128 + 1) / 3) ≡ A(84526) mod 3^11
--> A((80 * 4^28175 + 1) / 3) ≡ A(35479) mod 3^10
--> A((80 * 4^11826 + 1) / 3) ≡ A(14202) mod 3^9
--> A((20 * 4^4734 + 1) / 3) ≡ A(268) mod 3^8
--> A((80 * 4^89 + 1) / 3) ≡ A(2077) mod 3^7
--> A((80 * 4^692 + 1) / 3) ≡ A(394) mod 3^6
--> A((80 * 4^131 + 1) / 3) ≡ A(235) mod 3^5
--> A((80 * 4^78 + 1) / 3) ≡ A(21) mod 3^4
--> A((20 * 4^7 + 1) / 3) ≡ A(12) mod 3^3
--> A((20 * 4^4 + 1) / 3) ≡ A(6) mod 3^2
--> A((20 * 4^2 + 1) / 3) ≡ A(2) mod 3^1
--> *:[0, (20 * 4^0 - 2) / 3, 0] ≡ *:[0, 0, 0] mod 3^0
MBB(11) > 10^^17.74
</pre>

== Cryptids ==

=== MBB(8): Space Needle variants ===

Through the exhaustive search of the MBB(8) domain, all eight register machines have either been decided, or are equivalent to one of the two following potential [[cryptids]]: <code>0+B_1+C_2-AD_1-EH_2+F_1-DG_0-EB_2-C*</code> and <code>0+B_1-FC_2-GD_0-EF_1+C_2+A_2-EH_1-B*</code>, which may each be interpreted in the following ways:
<pre>
0+B_1+C_2-AD_1-EH_2+F_1-DG_0-EB_2-C*

Let A(x, y) = D:[x, y, 0]
A(x, 0) --(2)--> *:[x, 0, 0]
A(x, 2k + 1) --(6k + 6y + 9)--> A(x + k + 1, x + k + 2)
A(x, 2k + 2) --(6y + 6)--> A(x + k, k)

A:[0, 0, 0] --(3)--> A(1, 1)

Needle rules:
Let C(x + 3) = A(x, x + 1) = D:[x, x + 1, 0].
Let a and b be non-negative integers satisfying x = (2a + 1) * 2^b.
C(x) --> C(2x - a - 2b - 1) if a > 0
C(x) --> *:[2x - 2b - 3, 0, 0] if a = 0

START: C(5)
</pre>
<pre>
0+B_1-FC_2-GD_0-EF_1+C_2+A_2-EH_1-B*

Let A(x, y) = C:[x, 0, y]
A(x, 2k) --(6x + 6k + 5)--> A(x + k + 1, x + k + 1)
A(x, 2k + 3) --(6k + 7)--> A(x + k, k)
A(x, 1) --(3)--> *:[x, 0, 0]

A:[0, 0, 0] --(2)--> A(1, 0)

Needle rules:
Let C(x + 3) = A(x, x) = C:[x, 0, x].
Let a and b be non-negative integers satisfying x = (2a + 1) * 2^b.
C(x) --> C(2x - a - 3b - 1) if a > 0
C(x) --> *:[2x - 3b - 1, 0, 0] if a = 0

START: C(5)
</pre>
They are similar to the [[BB(6)]] cryptid [[Space Needle]], which is also the [[Beaver Math Olympiad#Unsolved problems|BMO's 6th problem]].

=== MBB(10): Hydra ===

[[Hydra]] was hand coded into a 10-instruction, 3-register register machine: <code>0-BF_1+C_1+D_0-EH_1+A_2+G_2+I_2-I*_0+J_1-IA</code> which can be interpreted the following way:[https://discord.com/channels/960643023006490684/1243312334907375676/1446694179337011325]
<pre>
Let S(h,w) = A:[h-3,0,w]

Start: A:[0,0,0] = S(3,0)
S(2k,0) = A:[2k-3,0,0] -> Halt
S(2k,w+1) = A:[2k-3,0,w+1] -> A:[3k-3,0,w] = S(3k,w)
S(2k+1,w) = A:[2k-2,0,w] -> A:[3k-2,0,w+2] = S(3k+1,w+2)
</pre>

=== MBB(12,2): Convergence of 7 under the 5n + 1 map ===
The 5n + 1 map has also been hand coded into a 12-instruction, 2-register machine: <code>0+B_0+C_0+D_0+E_1-IF_1+G_0-HE_0-FJ_0+A_1-KL_0+J_0-H*</code> which can be interpreted the following way:[https://discord.com/channels/960643023006490684/1552294888740098139/1555083694937604097]
<pre>
0+B_0+C_0+D_0+E_1-IF_1+G_0-HE_0-FJ_0+A_1-KL_0+J_0-H*

Let A(x + 3) = F:[x, 0]
Assume x > 0.
A(4) --(10)--> *:[0, 0]
A(2k) --(5k - 2)--> A(k)
A(2k + 1) --(9k)--> A(5k + 3)

A:[0, 0] --(5)--> A(7)
</pre>

=== MBB(130): Riemann Hypothesis ===
The Riemann Hypothesis has been coded into a 130-instruction, 29-register machine.[https://www.sciencedirect.com/science/article/pii/S0304397519304633]
[[Category:functions]]

Pebble Automaton

2026-10-14T14:04:29Z

AlephSquirrel: /* Busy Beaver function */ p(5) and p(6) proven (pretty confident this is correct now)

{{Stub}}
A pebble automaton is a type of [[cellular automaton]]. Each cell contains a non-negative number of pebbles, and the number of pebbles determines how many pebbles to push to each neighbor. Though pebble automata could be considered in any number of dimensions, investigation so far has primarily focused on 1 dimension.

Though it is unknown whether pebble automata are [[Turing-complete]], it is highly suspected that they are, since certain automata have been found to compute [[Collatz-like]] functions.

== Definition ==
A 1D pebble automaton is defined by three integer functions L(n), S(n) and R(n), defined over non-negative integers n, under the constraints:

* L(n) ≥ 0
* S(n) ≥ 0
* R(n) ≥ 0
* L(n) + S(n) + R(n) = n for all n

A simulation of a pebble automaton is represented by p(x, t), the number of pebbles at position x and time t. The initial configuration (t=0) has all n pebbles at x=0 and each generation, the pebbles are moved around according to the L, S, R rules:

* p(0, 0) = n
* p(x, 0) = 0 for x ≠ 0
* p(x, t+1) = R(p(x-1, t)) + S(p(x,t)) + L(p(x+1, t))

Informally, when a cell has n pebbles, it pushes L(n) to its left neighbor, R(n) to its right neighbor and S(n) stay.

Because the number of pebbles is preserved in each row, the maximum number of pebbles in one location is n. Therefore, a pebble automaton only needs to specify the function values up to n.

== Busy Beaver function ==
Let us define peBBle(n) as the maximum number of steps it takes for any pebble automaton to stabilize, starting from an initial state of n pebbles in a single cell.

Notation (long version): <code><nowiki>n --> L(n) | S(n) | R(n)</nowiki></code>

<code>0 --> 0 | 0 | 0</code> is omitted since it is forced by the definition.

The short version sets the rules in increasing order, separated by underscores, and removes <code>S(n)</code> since it can be obtained with the equation <code>S(N) = n - L(n) - R(n)</code>

If there are over 10 pebbles, we can extend the notation with letters, like with hexadecimal colors.
{| class="wikitable"
|+
!n
!peBBle(n)
!Champion
|-
|1
|0
|<code>00</code>
|-
|2
|1
|<code>00_01</code>
|-
|3
|3
|<code>00_01_20</code>
|-
|4
|6
|<code>00_01_20_03</code>
|-
|5
|11
|<code>00_11_03_21_04</code>
|-
|6
|17
|<code>00_11_03_21_40_15</code>
|-
|7
|≥ 28
|<code>00_11_03_21_10_33_61</code>
|-
|8
|≥ 63
|<code>00_11_03_21_50_30_24_70</code>
|-
|9
|≥ 63577
|<code>00_02_01_40_14_12_00_52_81</code>
|}

== Analysis ==

=== peBBle(5) ===
<syntaxhighlight line="1">
.5.....
.14....
.311...
..41...
.212...
1.3.1..
1..31..
1...4..
1..211.
1.1.21.
1.11.2.
1.111.1
</syntaxhighlight>

=== peBBle(6) ===
<syntaxhighlight line="1">
...6.....
..1.5....
..141....
..312....
...5.1...
..41.1...
.212.1...
1.3.11...
1..311...
1...41...
1..212...
1.1.3.1..
1.1..31..
1.1...4..
1.1..211.
1.1.1.21.
1.1.11.2.
1.1.111.1
</syntaxhighlight>

=== peBBle(7) ===
<syntaxhighlight line="1">
..7.......
.6.1......
3.31......
.3.4......
..511.....
.1411.....
.3121.....
..5.2.....
.141.1....
.312.1....
..5.11....
.14.11....
.31111....
..4111....
.21211....
1.3.21....
1..4.2....
1.212.1...
11.3.11...
11..311...
11...41...
11..212...
11.1.3.1..
11.1..31..
11.1...4..
11.1..211.
11.1.1.21.
11.1.11.2.
11.1.111.1
</syntaxhighlight>

=== peBBle(8) ===
<syntaxhighlight line="1">
.....8............
....71............
...215............
..1.7.............
..1214............
..2.411...........
.1.3121...........
.1..5.2...........
.1.5.1.1..........
.15..1.1..........
.6...1.1..........
33...1.1..........
.33..1.1..........
..33.1.1..........
...331.1..........
....34.1..........
....2411..........
...12221..........
...21212..........
..1.3.3.1.........
..1..3.31.........
..1...3.4.........
..1....511........
..1...5.11........
..1..5..11........
..1.5...11........
..15....11........
..6.....11........
.33.....11........
..33....11........
...33...11........
....33..11........
.....33.11........
......3311........
.......341........
.......242........
......12311.......
......2.141.......
.....1.1312.......
.....1.1.5.1......
.....1.15..1......
.....1.6...1......
.....133...1......
.....1.33..1......
.....1..33.1......
.....1...331......
.....1....34......
.....1....241.....
.....1...1222.....
.....1...21211....
.....1..1.3.21....
.....1..1..4.2....
.....1..1.212.1...
.....1..11.3.11...
.....1..11..311...
.....1..11...41...
.....1..11..212...
.....1..11.1.3.1..
.....1..11.1..31..
.....1..11.1...4..
.....1..11.1..211.
.....1..11.1.1.21.
.....1..11.1.11.2.
.....1..11.1.111.1
</syntaxhighlight>

=== peBBle(9) ===
The champion performs a [[Collatz-like]] function.

Analysis:
<syntaxhighlight line="1">
A(n) := 60^n3
B(n) := 60^n21

A(3k+1) -(20k+12)-> B(11k+5)
A(3k+2) -(8k+7)---> HALT
A(3k+3) -(20k+26)-> B(11k+12)

B(3k) -(8k+3)---> HALT
B(3k+1) -(20k+16)-> A(11k+7)
B(3k+2) -(20k+22)-> A(11k+11)

9 -(8)-> B(4) -(36)-> A(18) -(126)-> B(67) -(456)-> A(249) -(1666)-> B(914) -(6102)-> A(3355) -(22372)-> B(12303) -(32811)-> HALT
</syntaxhighlight>

== Cryptids ==

Though the overall Turing-completeness of pebble automata are unknown, an 86 pebble automaton has been produced by hand to display [[Hydra]]-like behavior:
<pre>
1 --> 0 | 1 | 0
2 --> 0 | 0 | 2
3 --> 0 | 0 | 3
5 --> 0 | 0 | 5
6 --> 0 | 6 | 0
7 --> 0 | 1 | 6
8 --> 0 | 2 | 6
9 --> 9 | 0 | 0
12 --> 12 | 0 | 0
14 --> 0 | 14 | 0
15 --> 6 | 9 | 0
17 --> 17 | 0 | 0
24 --> 0 | 24 | 0
25 --> 0 | 2 | 23
26 --> 0 | 1 | 25
27 --> 24 | 3 | 0
28 --> 26 | 2 | 0
29 --> 27 | 2 | 0
30 --> 27 | 3 | 0
32 --> 0 | 32 | 0
33 --> 0 | 33 | 0
35 --> 0 | 2 | 33
38 --> 0 | 3 | 35
39 --> 0 | 0 | 39
40 --> 0 | 0 | 40
41 --> 1 | 40 | 0
45 --> 0 | 39 | 6
78 --> 0 | 0 | 78
79 --> 0 | 79 | 0
84 --> 24 | 15 | 45
86 --> 1 | 1 | 84
</pre>
It may be interpreted in the following way:
<pre>
Let C(x, y) = $ 1 0^y 1 0^x 84 $
C(2k, y) --> C(7k + 3, y + 2)
C(2k + 1, y + 1) --> C(7k + 10, y)
C(2k + 1, 0) --> HALT

$$ --> C(0, 0) --> C(3, 2) --> C(17, 1) --> C(66, 0) --> C(234, 2)...
</pre>

== Sources ==

* Discord thread: https://discord.com/channels/960643023006490684/1535695107448381591
== External resources ==

* [https://gist.github.com/AlephSquirrel/9ada4b14b675d18fe8755b200b20509d Uiua simulator]
* [https://github.com/AzertyWasTaken/Busy-Beaver/tree/main/Pebble%20Automaton Enumerator GitHub repo]
* [https://azertywastaken.github.io/Busy-Beaver/Website/pebble-automaton.html Simulator website]

[[Category:Functions]]
[[Category:Stubs]]

Pebble Automaton

2026-10-13T14:41:27Z

AlephSquirrel: add p(8) analysis

{{Stub}}
A pebble automaton is a type of [[cellular automaton]]. Each cell contains a non-negative number of pebbles, and the number of pebbles determines how many pebbles to push to each neighbor. Though pebble automata could be considered in any number of dimensions, investigation so far has primarily focused on 1 dimension.

Though it is unknown whether pebble automata are [[Turing-complete]], it is highly suspected that they are, since certain automata have been found to compute [[Collatz-like]] functions.

== Definition ==
A 1D pebble automaton is defined by three integer functions L(n), S(n) and R(n), defined over non-negative integers n, under the constraints:

* L(n) ≥ 0
* S(n) ≥ 0
* R(n) ≥ 0
* L(n) + S(n) + R(n) = n for all n

A simulation of a pebble automaton is represented by p(x, t), the number of pebbles at position x and time t. The initial configuration (t=0) has all n pebbles at x=0 and each generation, the pebbles are moved around according to the L, S, R rules:

* p(0, 0) = n
* p(x, 0) = 0 for x ≠ 0
* p(x, t+1) = R(p(x-1, t)) + S(p(x,t)) + L(p(x+1, t))

Informally, when a cell has n pebbles, it pushes L(n) to its left neighbor, R(n) to its right neighbor and S(n) stay.

Because the number of pebbles is preserved in each row, the maximum number of pebbles in one location is n. Therefore, a pebble automaton only needs to specify the function values up to n.

== Busy Beaver function ==
Let us define peBBle(n) as the maximum number of steps it takes for any pebble automaton to stabilize, starting from an initial state of n pebbles in a single cell.

Notation (long version): <code><nowiki>n --> L(n) | S(n) | R(n)</nowiki></code>

<code>0 --> 0 | 0 | 0</code> is omitted since it is forced by the definition.

The short version sets the rules in increasing order, separated by underscores, and removes <code>S(n)</code> since it can be obtained with the equation <code>S(N) = n - L(n) - R(n)</code>

If there are over 10 pebbles, we can extend the notation with letters, like with hexadecimal colors.
{| class="wikitable"
|+
!n
!peBBle(n)
!Champion
|-
|1
|0
|<code>00</code>
|-
|2
|1
|<code>00_01</code>
|-
|3
|3
|<code>00_01_20</code>
|-
|4
|6
|<code>00_01_20_03</code>
|-
|5
|≥ 11
|<code>00_11_03_21_04</code>
|-
|6
|≥ 17
|<code>00_11_03_21_40_15</code>
|-
|7
|≥ 28
|<code>00_11_03_21_10_33_61</code>
|-
|8
|≥ 63
|<code>00_11_03_21_50_30_24_70</code>
|-
|9
|≥ 63577
|<code>00_02_01_40_14_12_00_52_81</code>
|}

== Analysis ==

=== peBBle(5) ===
<syntaxhighlight line="1">
.5.....
.14....
.311...
..41...
.212...
1.3.1..
1..31..
1...4..
1..211.
1.1.21.
1.11.2.
1.111.1
</syntaxhighlight>

=== peBBle(6) ===
<syntaxhighlight line="1">
...6.....
..1.5....
..141....
..312....
...5.1...
..41.1...
.212.1...
1.3.11...
1..311...
1...41...
1..212...
1.1.3.1..
1.1..31..
1.1...4..
1.1..211.
1.1.1.21.
1.1.11.2.
1.1.111.1
</syntaxhighlight>

=== peBBle(7) ===
<syntaxhighlight line="1">
..7.......
.6.1......
3.31......
.3.4......
..511.....
.1411.....
.3121.....
..5.2.....
.141.1....
.312.1....
..5.11....
.14.11....
.31111....
..4111....
.21211....
1.3.21....
1..4.2....
1.212.1...
11.3.11...
11..311...
11...41...
11..212...
11.1.3.1..
11.1..31..
11.1...4..
11.1..211.
11.1.1.21.
11.1.11.2.
11.1.111.1
</syntaxhighlight>

=== peBBle(8) ===
<syntaxhighlight line="1">
.....8............
....71............
...215............
..1.7.............
..1214............
..2.411...........
.1.3121...........
.1..5.2...........
.1.5.1.1..........
.15..1.1..........
.6...1.1..........
33...1.1..........
.33..1.1..........
..33.1.1..........
...331.1..........
....34.1..........
....2411..........
...12221..........
...21212..........
..1.3.3.1.........
..1..3.31.........
..1...3.4.........
..1....511........
..1...5.11........
..1..5..11........
..1.5...11........
..15....11........
..6.....11........
.33.....11........
..33....11........
...33...11........
....33..11........
.....33.11........
......3311........
.......341........
.......242........
......12311.......
......2.141.......
.....1.1312.......
.....1.1.5.1......
.....1.15..1......
.....1.6...1......
.....133...1......
.....1.33..1......
.....1..33.1......
.....1...331......
.....1....34......
.....1....241.....
.....1...1222.....
.....1...21211....
.....1..1.3.21....
.....1..1..4.2....
.....1..1.212.1...
.....1..11.3.11...
.....1..11..311...
.....1..11...41...
.....1..11..212...
.....1..11.1.3.1..
.....1..11.1..31..
.....1..11.1...4..
.....1..11.1..211.
.....1..11.1.1.21.
.....1..11.1.11.2.
.....1..11.1.111.1
</syntaxhighlight>

=== peBBle(9) ===
The champion performs a [[Collatz-like]] function.

Analysis:
<syntaxhighlight line="1">
A(n) := 60^n3
B(n) := 60^n21

A(3k+1) -(20k+12)-> B(11k+5)
A(3k+2) -(8k+7)---> HALT
A(3k+3) -(20k+26)-> B(11k+12)

B(3k) -(8k+3)---> HALT
B(3k+1) -(20k+16)-> A(11k+7)
B(3k+2) -(20k+22)-> A(11k+11)

9 -(8)-> B(4) -(36)-> A(18) -(126)-> B(67) -(456)-> A(249) -(1666)-> B(914) -(6102)-> A(3355) -(22372)-> B(12303) -(32811)-> HALT
</syntaxhighlight>

== Cryptids ==

Though the overall Turing-completeness of pebble automata are unknown, an 86 pebble automaton has been produced by hand to display [[Hydra]]-like behavior:
<pre>
1 --> 0 | 1 | 0
2 --> 0 | 0 | 2
3 --> 0 | 0 | 3
5 --> 0 | 0 | 5
6 --> 0 | 6 | 0
7 --> 0 | 1 | 6
8 --> 0 | 2 | 6
9 --> 9 | 0 | 0
12 --> 12 | 0 | 0
14 --> 0 | 14 | 0
15 --> 6 | 9 | 0
17 --> 17 | 0 | 0
24 --> 0 | 24 | 0
25 --> 0 | 2 | 23
26 --> 0 | 1 | 25
27 --> 24 | 3 | 0
28 --> 26 | 2 | 0
29 --> 27 | 2 | 0
30 --> 27 | 3 | 0
32 --> 0 | 32 | 0
33 --> 0 | 33 | 0
35 --> 0 | 2 | 33
38 --> 0 | 3 | 35
39 --> 0 | 0 | 39
40 --> 0 | 0 | 40
41 --> 1 | 40 | 0
45 --> 0 | 39 | 6
78 --> 0 | 0 | 78
79 --> 0 | 79 | 0
84 --> 24 | 15 | 45
86 --> 1 | 1 | 84
</pre>
It may be interpreted in the following way:
<pre>
Let C(x, y) = $ 1 0^y 1 0^x 84 $
C(2k, y) --> C(7k + 3, y + 2)
C(2k + 1, y + 1) --> C(7k + 10, y)
C(2k + 1, 0) --> HALT

$$ --> C(0, 0) --> C(3, 2) --> C(17, 1) --> C(66, 0) --> C(234, 2)...
</pre>

== Sources ==

* Discord thread: https://discord.com/channels/960643023006490684/1535695107448381591
== External resources ==

* [https://gist.github.com/AlephSquirrel/9ada4b14b675d18fe8755b200b20509d Uiua simulator]
* [https://github.com/AzertyWasTaken/Busy-Beaver/tree/main/Pebble%20Automaton Enumerator GitHub repo]
* [https://azertywastaken.github.io/Busy-Beaver/Website/pebble-automaton.html Simulator website]

[[Category:Functions]]
[[Category:Stubs]]

Pebble Automaton

2026-10-12T20:13:28Z

AlephSquirrel: Undo revision 9059 by AlephSquirrel (talk)

Pebble Automaton

2026-10-12T19:44:15Z

AlephSquirrel: /* Busy Beaver function */ p(5) and p(6) proven

TMBR: September 2026

2026-10-05T17:42:13Z

AlephSquirrel: Add TMBR category

{{TMBRnav|August 2026|October 2026}}

''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''

== Blog Posts ==

* September 1, 2026. Nick Drozd. [https://nickdrozd.github.io/2026/09/01/tetrational-self-cleaning-turing-machine.html A Tetrational Self-Cleaning Turing Machine].

== Champions ==

* On September 1, nickdrozd discovered a new [[BLB|BLB(3,3)]] champion which runs for over 10↑↑6.54 steps before blanking the tape.[https://discord.com/channels/960643023006490684/1259770474897080380/1544448259437895680] Note that this is not a new [[BBB|BBB(3,3)]] champion.
* On September 9, @-d discovered a new [[BBf|BBf(24)]] champion which runs for over 9.000 × 1014,448 steps.[https://discord.com/channels/960643023006490684/1438019511155691521/1547182811713380383]

== BB Adjacent ==

* [[Cyclic Tag]]
** On September 1, Azerty enumerated all BBCT programs up to size 14, proving the values of BBCT(n) for n < 7.[https://discord.com/channels/960643023006490684/1542262029430292501/1544315541383155784]
** On September 2, sheep discovered new champions for BBCT(11),[https://discord.com/channels/960643023006490684/1542262029430292501/1544351459846529134] BBCT(13),[https://discord.com/channels/960643023006490684/1542262029430292501/1544368872973664337] and BBCT(14).[https://discord.com/channels/960643023006490684/1542262029430292501/1544633416064962611]
** On September 5, Azerty proved BBCT(7) = 13.[https://discord.com/channels/960643023006490684/1542262029430292501/1545914357777571951]

* Cellular Automata Busy Beaver
** On September 1, Azerty introduced an extension to mxdys's BB1dCA(n) function, called BBCA(n),[https://discord.com/channels/960643023006490684/1544449379027525692/1544449379027525692] and discovered a champion for BBCA(3).[https://discord.com/channels/960643023006490684/1544449379027525692/1544450495769350165]
** On September 2, Azerty discovered champions for BBCA(2), BBCA(3), BBCA(4), BBCA(2,3), and BBCA(2,4).[https://github.com/AzertyWasTaken/Busy-Beaver/commit/9b9fdf5719899c3b99c88a3c20cfaf4e210212ce#diff-6592f17ae2c30022dac537f021e42737edeff658a96c47ca285e2c301b8e1415]
** On September 20, Azerty discovered new champions for BBCA(4), BBCA(3,3), and BBCA(2,4), and proved BBCA(2,3) = 4.[https://github.com/AzertyWasTaken/Busy-Beaver/commit/b9f2fa8eeaa40c3cdede7b39d4f9785185eaf10a#diff-6592f17ae2c30022dac537f021e42737edeff658a96c47ca285e2c301b8e1415]

* [[General Recursive Function]]
** On September 5, after Shawn Ligocki renewed interest in a certain chaotic BBµ(16) holdout last month, sheep devised a method to accelerate the simulation of the holdout.[https://discord.com/channels/960643023006490684/1447627603698647303/1545730338725171250] This allowed her to confirm that, if the holdout returned a value, it would be larger than 3.124 × 1016.[https://discord.com/channels/960643023006490684/1260977480316092527/1546531543290224701]
** On September 7, the aforementioned method was ported to Rust by @ZTS439, allowing them to extend the bound to 4.999 × 1017.[https://discord.com/channels/960643023006490684/1447627603698647303/1546666535911821413]

* PLUSMINUS[https://discord.com/channels/960643023006490684/1243312334907375676/1546687220390567948]
** On September 8, @Jack introduced PLUSMINUS, a new esoteric language.[https://discord.com/channels/960643023006490684/1243312334907375676/1546687220390567948] Though its completeness is unknown, this language is not expected to be Turing-complete.[https://discord.com/channels/960643023006490684/1243312334907375676/1546687246231666688]
** On September 9, @mathmasterzach discovered champion PLUSMINUS strings for sizes 9,[https://discord.com/channels/960643023006490684/1243312334907375676/1547051560972845178] 11,[https://discord.com/channels/960643023006490684/1243312334907375676/1547050522425561209] 12,[https://discord.com/channels/960643023006490684/1243312334907375676/1547054625134477342], 15, and 16.[https://discord.com/channels/960643023006490684/1547296154105159722/1547336527334613092]
** On the same day, @Furious discovered champion PLUSMINUS strings for sizes 1 to 8[https://discord.com/channels/960643023006490684/1243312334907375676/1547258179589775523] and size 10-14.[https://discord.com/channels/960643023006490684/1547296154105159722/1547300240019816589]
** On the same day, racheline provided an estimate for the halting times of PLUSMINUS programs.[https://discord.com/channels/960643023006490684/1243312334907375676/1547306730487283832] This suggests that PLUSMINUS is not Turing-complete.
** On September 10, @Furious converted the rules of PLUSMINUS into a piecewise mathematical function.[https://discord.com/channels/960643023006490684/1547296154105159722/1547678473429065831]
** On September 11, @Jack discovered champion PLUSMINUS strings for sizes 20, 23, 32, 36, and 40.[https://discord.com/channels/960643023006490684/1547296154105159722/1548057628503179335]

* [[Post Tag System]] (alternate definition)
** On September 12, Azerty introduced an alternate formulation of the Busy Beaver function for Post Tag Systems, where a system in the BBPT*(m, n) domain may continue running even if it reduces to less than m symbols;[https://discord.com/channels/960643023006490684/1547326637488738314/1548436378050625629] in this formulation, the BBPT(11) cryptid <code>11111_20_1</code> is non-halting.[https://discord.com/channels/960643023006490684/1547326637488738314/1548483710909812889]
** On September 16, Azerty enumerated all 2-tag systems with size less than or equal to 9[https://discord.com/channels/960643023006490684/1547326637488738314/1549745884596797580], and proved the values of BBPT*(n) for sizes 1 to 5.
** On the same day, sheep discovered a new BBPT*(9) champion.[https://discord.com/channels/960643023006490684/1547326637488738314/1549811809081626755]
** On September 30, sheep discovered a 2-tag size 11 cryptid, showing BBPT*(11) is hard;[https://discord.com/channels/960643023006490684/1547326637488738314/1554759504560656415] Azerty expects there to be smaller cryptids,[https://discord.com/channels/960643023006490684/1547326637488738314/1554818815093907468] likely referring to systems with their tape length history similar to a biased random walk.
* [[Fractran]]
** On September 13, @-d completed enumeration of BBf(24), leaving an initial 6,733,785 holdouts, which were reduced to 231,432 holdouts, or 10,838 holdouts if ai-created deciders are used.[https://discord.com/channels/960643023006490684/1438019511155691521/1548561426262790144]

* [https://github.com/AzertyWasTaken/Busy-Beaver/tree/main/Ordered%Rewrite%20System Ordered rewrite system]
** On September 16, @andrewthebonfire and Azerty introduced the Busy Beaver function on Ordered rewrite systems,[https://discord.com/channels/960643023006490684/1243312334907375676/1549603291791360051][https://discord.com/channels/960643023006490684/1243312334907375676/1549678817470058516][https://discord.com/channels/960643023006490684/1243312334907375676/1549767379490447501] with Azerty later finding BBOR(n) champions for sizes 1 to 8, and proving the values of BBOR(n) for sizes 1 to 4.[https://discord.com/channels/960643023006490684/1243312334907375676/1549853449015795764]
** On September 17, @andrewthebonfire provided a method to convert Turing machines into ordered rewrite systems.[https://discord.com/channels/960643023006490684/1243312334907375676/1550137065969287220] He also showed that ordered rewrite systems with a binary alphabet (i.e. two symbols) are still Turing-complete.[https://discord.com/channels/960643023006490684/1243312334907375676/1550139787456020560]
** On September 30, sheep discovered a size 17 cryptid, showing BBOR(17) is hard.[https://discord.com/channels/960643023006490684/1243312334907375676/1554501166388351179]

* [[Register machine|Register Machine]]
** On September 18, @mineralli discovered a new MBB(9) champion.[https://discord.com/channels/960643023006490684/1243312334907375676/1550599643031670875] sheep then discovered four new champions for MBB(9) in the four following days.[https://discord.com/channels/960643023006490684/1243312334907375676/1550932034040635585][https://discord.com/channels/960643023006490684/1243312334907375676/1551127274244411494][https://discord.com/channels/960643023006490684/1243312334907375676/1551194371435790418][https://discord.com/channels/960643023006490684/1243312334907375676/1551985291198210071]
** On the same day, @elgan65536 discovered a new MBB(8,2) champion.[https://discord.com/channels/960643023006490684/1243312334907375676/1550504258401599609]
** On September 23, sheep discovered champions for MBB(11)[https://discord.com/channels/960643023006490684/1243312334907375676/1552283247889612861] and MBB(12).[https://discord.com/channels/960643023006490684/1243312334907375676/1552284085781667851]
** On September 25, sheep discovered an MBB(10) champion,[https://discord.com/channels/960643023006490684/1552294888740098139/1552360261900435537] which was shown to halt in around 102,629,437 steps by Shawn Ligocki.[https://discord.com/channels/960643023006490684/1552294888740098139/1552690832006447186] This champion prompted a rework of Ligocki's hydra-like rule accelerator.[https://discord.com/channels/960643023006490684/1552294888740098139/1553109975528902729]
** On September 29, @mineralli discovered a 5-register, 19-state machine which halts iff the Erdős ternary conjecture is false.
** On the same day, sheep discovered a 7-register, 28-state machine beating [[Graham's number]].[https://discord.com/channels/960643023006490684/1552294888740098139/1554558141964886190]
** On September 30, @mineralli discovered a new MBB(11,2) champion,[https://discord.com/channels/960643023006490684/1552294888740098139/1554893821857501236] improved upon by sheep.[https://discord.com/channels/960643023006490684/1552294888740098139/1554913439695249570]
* [[Pebble Eating]]
** On September 30, sheep discovered an 86 pebble cryptid, showing peBBle(86) is hard.[https://discord.com/channels/960643023006490684/1535695107448381591/1554751849742082102]

== Holdouts ==
* [[BB(6)]]
** By September 4, mxdys solved all 16 Counter Class 1 TMs.[https://discord.com/channels/960643023006490684/1239205785913790465/1545487019218698290]
** On September 4, Discord user fifi_49513 claimed to have proven a TM non-halting. [https://discord.com/channels/960643023006490684/1545543031468462150/1545543031468462150] This machine was later confirmed non-halting in Rocq on September 5 by mxdys. [https://discord.com/channels/960643023006490684/1545543031468462150/1545682001481175095]
** On September 8, mxdys released a new holdouts list of '''964''' machines up to equivalence.[https://discord.com/channels/960643023006490684/1239205785913790465/1546881471556620339]
** On September 14, an independent computation by Seiji extended the [[Space Needle]] trajectory to '''100,000,000''' terms: no power of 2 was ever encountered, and the most factors of 2 any term had was '''25''' (first occurring at n = 23,145,881; the previously documented state was >17,000,000 terms with max 24). The full final value (94,125,050 bits) is published with SHA-256 anchors, together with 400 checkpoints cross-verified by two independent implementations, and exact macro step-count laws of the machine (L0–L4; L1 and L3 formally proven). [https://github.com/oohzaim1-afk/space-needle-100M]
** On September 16, mxdys released another holdouts list of '''855''' machines up to equivalence.[https://discord.com/channels/960643023006490684/1239205785913790465/1549771931677364264]
** On September 24, mxdys released another holdouts list of '''815''' machines up to equivalence.[https://discord.com/channels/960643023006490684/1239205785913790465/1552681541401059350] The newly solved holdouts include:
*** [[BMO|BMO9]]
*** Two shift-overflow bell counters
*** 31 shift-overflow mixed-digits counters with similar behavior
*** two new translated cyclers (also shift-overflow mixed-digits counters) with high period
*** two other shift-overflow counters
**On September 24, Discord user q64 simulated a TM to halt[https://discord.com/channels/960643023006490684/1239205785913790465/1552399839269224498]
**The halting status of {{TM|1RB1LA_1RC1RE_1LD0RB_1LA0LC_0RF0RD_0RB---}} was formalized without new axioms by avoiding the use of Baker–Wüstholz theorem.
**On September 30, mxdys released another holdouts list of '''797''' machines up to equivalence.[https://discord.com/channels/960643023006490684/1239205785913790465/1554765260735512616]
*[[BB(2,5)]]
**On September 8, mxdys released a new holdouts list of '''60''' machines.[https://discord.com/channels/960643023006490684/1259770421046411285/1546880921318326282]
**On September 25 and 26, prurq used Aristotle AI and GPT6 to solve 21 of the 60 remaining holdouts.[https://discord.com/channels/960643023006490684/1259770421046411285/1552990521650319453][https://discord.com/channels/960643023006490684/1259770421046411285/1553433274762919997 <nowiki>[67]</nowiki>]
* [[BB(2,7)]]
** Terry Ligocki enumerated 31K more subtasks, increasing the number of holdouts to '''3,062,427,379'''. A total of 980K subtasks out of the 1 million subtasks (or '''98%''') have been enumerated.

== Misc ==
* On September 2, RobinCodes began work on updating the BB(6) holdout [https://docs.google.com/spreadsheets/d/1mMp8bAcTFT91j7azn72liX8NSTwc2E_ozKnOGTfRCfw/edit?pli=1&gid=1330361301#gid=1330361301 spreadsheet].[https://discord.com/channels/960643023006490684/1239205785913790465/1544742905850236978]
* On September 5, [[User:XnoobSpeakable|XnoobSpeakable]] began an opt-in archival project of the bbchallenge Discord server.[https://discord.com/channels/960643023006490684/960643023530762341/1545742987710038088]
* On September 23, Joseph M. Shunia published a preprint presenting a 120-state TM that halts iff Riemann hypothesis is false.[https://arxiv.org/abs/2609.30306]
* On September 22, Twitter user @_Mira___Mira_ claimed to have discovered a 387-state TM whose halting status is [[Independence from ZFC|independent of ZFC]] with GPT-6 Astra.[https://twitter.com/_Mira___Mira_/status/2102108613028560993]
** On September 24, they claimed to have found a 314-state ZFC-independent TM, and a 289-state PA-independent TM.[https://twitter.com/_Mira___Mira_/status/2102796188265439626]
** On September 30, after a series of constant improvements, they claimed to have found a 256-state ZFC-independent TM, and a 238-state PA-independent TM. A Metamath formalization is in progress.[https://twitter.com/_Mira___Mira_/status/2105184649098268774]
* On September 28, Twitter user @_Mira___Mira_ discovered a fractal related to the Antihydra conjecture.[https://twitter.com/_Mira___Mira_/status/2104539527117513127]

[[Category:This Month in Beaver Research|2026-09]]

TMBR: July 2026

2026-10-03T15:44:36Z

AlephSquirrel: /* BB Adjacent */ Wnagtlies

{{TMBRnav|June 2026|August 2026}}

''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''

== General ==

* TODO: BB(5) Lean proof completed: https://discord.com/channels/960643023006490684/1218877181321678928/1530515342772666429
* TODO: BBB(4) proof progress: https://discord.com/channels/960643023006490684/1385498968011575366/1532076512927420556

== BB Adjacent ==
[[SKI Calculus]]:
* A new champion was discovered for Ξ₀(12).
* New champions were discovered for Ξ₀SK(12), Ξ₀SK(13), Ξ₀S(14), Ξ₀SK(15), Ξ₀SK(16) and Ξ₀SK(17).
TODO: update

[[Lambda Calculus]]:
* [https://discord.com/channels/960643023006490684/1355653587824283678/1528855324881326181 BBλ(40) was solved] on 20 July, showing that BBλ(40) ≈ 10↑↑↑16. BBλ(40) is the first solved domain in any BB variant to reach pentational values.
TODO: Post Tag System

* [[Wang Tiles]]
** Over July 22-25, AlephSquirrel found champions 1-4 and proved their optimality, and found the BB_WT(5) champion.
** Prior work by Emmanuel Jeandel and Michael Rao in 2015 shows BB_WT(10) ≥ 212.<ref>https://arxiv.org/abs/1506.06492</ref>

== Holdouts ==
{| class="wikitable"
|+BB Holdout Reduction by Domain
!Domain
!Previous Holdout Count
!New Holdout Count
!Holdout Reduction
!% Reduction
|-
|[[BB(6)]]
|1,094
|1,064
|30
|2.74%
|-
|[[BB(4,3)]]
|4,784,443
|4,747,566
|36,877
|0.77%
|}
* [[BB(6)]]
** On 2 July, mxdys solved three holdouts in rocq.[https://discord.com/channels/960643023006490684/1239205785913790465/1522010493529751604][https://discord.com/channels/960643023006490684/1239205785913790465/1522209150699044904]
** On 3 July, mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1522617640554860574 solved another holdout] in rocq using an LLM.
** mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1531681818439319604 released] a new holdouts list of '''1,064''' machines up to equivalence, this is a '''2.74%''' reduction compared to the previous holdouts list.
** On 28 July, prurq [https://discord.com/channels/960643023006490684/1239205785913790465/1531564686238027976 found a TM to halt]. This was [https://discord.com/channels/960643023006490684/1239205785913790465/1532416648533901503 verified by mxdys] in rocq two days later together with another machine.
** TODO: BMO 9 and BMO 10
* [[BB(4,3)]]
** Andrew Ducharme reduced the number of holdouts from 4,784,443 to '''4,747,566''', a '''0.77%''' reduction.[https://discord.com/channels/960643023006490684/1084047886494470185/1522168741922607164][https://discord.com/channels/960643023006490684/1084047886494470185/1530496818155229294]
*[[BB(2,7)]]
**Terry Ligocki enumerated 180K more subtasks, increasing the number of holdouts to '''2,185,010,519'''. A total of 700K subtasks out of the 1 million subtasks (or '''70%''') have been enumerated.

[[Category:This Month in Beaver Research|2026-07]]

TMBR: August 2026

2026-10-03T15:24:13Z

AlephSquirrel: /* BB Adjacent */

{{TMBRnav|July 2026|September 2026}}

''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''

== BB Adjacent ==

* [[TT|TT (Terminating Turmites)]]
** On August 3, Discord user creeperman7002 discovered a new step and score champion for TT(3,3), <code>1PB2PA0PC_2TB1PC2PB_2PB1PZ0PA</code>, running for 715,764,479 steps.
** On August 8, Discord user creeperman7002 discovered a new step champion for TT(3,3), <code>1PB0TC1PA_2PC1PZ2PA_2TC0PA2PC</code>, running for 2.27 × 10248 steps.

* [[Pebble Automaton]]
** On August 8-9, AlephSquirrel and Sheep found champions 1-5.
** On August 10, Deccy found champions 6-7.
** On August 13, mathmasterzach found the peBBle(8) champion, and the previous peBBle(9) champion, which ran for 323 steps.
** On August 16, AlephSquirrel proved the peBBle(4) champion to be optimal.
** On August 17, AlephSquirrel tweaked the peBBle(9) champion to run for 63577 steps.

TODO: [[Wang Tiles]]

TODO: [[SKI Calculus]]

TODO: [[Cyclic Tag]]

== Holdouts ==
* [[BB(6)]]
** On August 3, prurq found three machines to halt.[https://discord.com/channels/960643023006490684/1239205785913790465/1533572940459675791][https://discord.com/channels/960643023006490684/1239205785913790465/1533837709452251227][https://discord.com/channels/960643023006490684/1239205785913790465/1533889409332674763]
** On August 5, q64 [https://discord.com/channels/960643023006490684/1239205785913790465/1534370964350042263 simulated another TM] to halt.
** On August 15, Discord user jacobrschwartz [https://discord.com/channels/960643023006490684/960643023530762341/1538044554286993418 proved another TM] halting.
** Later that day, mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1538109685033607198 released] a new holdouts list of '''1,016''' machines up to equivalence, this is a '''4.51%''' reduction compared to the previous holdouts lists.
** On August 24, Discord user flintt_6 informally [https://discord.com/channels/960643023006490684/1239205785913790465/1541418968806334515 proved another TM] halting.
** On August 26, q64 [https://discord.com/channels/960643023006490684/1239205785913790465/1542210565404098652 proved another TM] halting.
** On August 30, mxdys [https://discordapp.com/channels/960643023006490684/1239205785913790465/1543436534831906926 released] another holdouts list of '''1,003''' machines up to equivalence.
** On August 31, mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1543878992195620884 released] another holdouts list of '''999''' machines up to equivalence.
*[[BB(2,7)]]
**Terry Ligocki enumerated 150K more subtasks, increasing the number of holdouts to '''2,651,060,579'''. A total of 850K subtasks out of the 1 million subtasks (or '''85%''') have been enumerated.

[[Category:This Month in Beaver Research|2026-08]]

TMBR: August 2026

2026-10-03T15:20:21Z

AlephSquirrel: /* BB Adjacent */

{{TMBRnav|July 2026|September 2026}}

''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''

== BB Adjacent ==

* [[TT|TT (Terminating Turmites)]]
** On August 3, Discord user creeperman7002 discovered a new step and score champion for TT(3,3), <code>1PB2PA0PC_2TB1PC2PB_2PB1PZ0PA</code>, running for 715,764,479 steps.
** On August 8, Discord user creeperman7002 discovered a new step champion for TT(3,3), <code>1PB0TC1PA_2PC1PZ2PA_2TC0PA2PC</code>, running for 2.27 × 10248 steps.

* [[Pebble Automaton]]
** On August 8-9, AlephSquirrel and Sheep found champions 1-5, running for [0, 1, 3, 6, 11] steps.
** On August 10, Deccy found champions 6-7, running for [17, 28] steps.
** On August 13, mathmasterzach found the peBBle(8) champion, running for 63 steps, and the previous peBBle(9) champion, which ran for 323 steps.
** On August 16, AlephSquirrel proved the peBBle(4) champion to be optimal.
** On August 17, AlephSquirrel tweaked the peBBle(9) champion to run for 63577 steps.

TODO: [[Wang Tiles]]

TODO: [[SKI Calculus]]

TODO: [[Cyclic Tag]]

== Holdouts ==
* [[BB(6)]]
** On August 3, prurq found three machines to halt.[https://discord.com/channels/960643023006490684/1239205785913790465/1533572940459675791][https://discord.com/channels/960643023006490684/1239205785913790465/1533837709452251227][https://discord.com/channels/960643023006490684/1239205785913790465/1533889409332674763]
** On August 5, q64 [https://discord.com/channels/960643023006490684/1239205785913790465/1534370964350042263 simulated another TM] to halt.
** On August 15, Discord user jacobrschwartz [https://discord.com/channels/960643023006490684/960643023530762341/1538044554286993418 proved another TM] halting.
** Later that day, mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1538109685033607198 released] a new holdouts list of '''1,016''' machines up to equivalence, this is a '''4.51%''' reduction compared to the previous holdouts lists.
** On August 24, Discord user flintt_6 informally [https://discord.com/channels/960643023006490684/1239205785913790465/1541418968806334515 proved another TM] halting.
** On August 26, q64 [https://discord.com/channels/960643023006490684/1239205785913790465/1542210565404098652 proved another TM] halting.
** On August 30, mxdys [https://discordapp.com/channels/960643023006490684/1239205785913790465/1543436534831906926 released] another holdouts list of '''1,003''' machines up to equivalence.
** On August 31, mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1543878992195620884 released] another holdouts list of '''999''' machines up to equivalence.
*[[BB(2,7)]]
**Terry Ligocki enumerated 150K more subtasks, increasing the number of holdouts to '''2,651,060,579'''. A total of 850K subtasks out of the 1 million subtasks (or '''85%''') have been enumerated.

[[Category:This Month in Beaver Research|2026-08]]

TMBR: August 2026

2026-10-03T04:15:59Z

AlephSquirrel: /* BB Adjacent */ Pebbl

{{TMBRnav|July 2026|September 2026}}

''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''

== BB Adjacent ==

* [[TT|TT (Terminating Turmites)]]
** On August 3, Discord user creeperman7002 discovered a new step and score champion for TT(3,3), <code>1PB2PA0PC_2TB1PC2PB_2PB1PZ0PA</code>, running for 715,764,479 steps.
** On August 8, Discord user creeperman7002 discovered a new step champion for TT(3,3), <code>1PB0TC1PA_2PC1PZ2PA_2TC0PA2PC</code>, running for 2.27 × 10248 steps.

* [[Pebble Automaton]]
** On August 8-9, AlephSquirrel and Sheep found champions 1-5.
** On August 10, Deccy found champions 6-7.
** On August 13, mathmasterzach found the peBBle(8) champion, and the previous peBBle(9) champion which ran for 323 steps.
** On August 16, AlephSquirrel proved the peBBle(4) champion to be optimal, and on the following day tweaked the peBBle(9) champion to run for 63577 steps.

TODO: [[Wang Tiles]]

TODO: [[SKI Calculus]]

TODO: [[Cyclic Tag]]

== Holdouts ==
* [[BB(6)]]
** On August 3, prurq found three machines to halt.[https://discord.com/channels/960643023006490684/1239205785913790465/1533572940459675791][https://discord.com/channels/960643023006490684/1239205785913790465/1533837709452251227][https://discord.com/channels/960643023006490684/1239205785913790465/1533889409332674763]
** On August 5, q64 [https://discord.com/channels/960643023006490684/1239205785913790465/1534370964350042263 simulated another TM] to halt.
** On August 15, Discord user jacobrschwartz [https://discord.com/channels/960643023006490684/960643023530762341/1538044554286993418 proved another TM] halting.
** Later that day, mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1538109685033607198 released] a new holdouts list of '''1,016''' machines up to equivalence, this is a '''4.51%''' reduction compared to the previous holdouts lists.
** On August 24, Discord user flintt_6 informally [https://discord.com/channels/960643023006490684/1239205785913790465/1541418968806334515 proved another TM] halting.
** On August 26, q64 [https://discord.com/channels/960643023006490684/1239205785913790465/1542210565404098652 proved another TM] halting.
** On August 30, mxdys [https://discordapp.com/channels/960643023006490684/1239205785913790465/1543436534831906926 released] another holdouts list of '''1,003''' machines up to equivalence.
** On August 31, mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1543878992195620884 released] another holdouts list of '''999''' machines up to equivalence.
*[[BB(2,7)]]
**Terry Ligocki enumerated 150K more subtasks, increasing the number of holdouts to '''2,651,060,579'''. A total of 850K subtasks out of the 1 million subtasks (or '''85%''') have been enumerated.

[[Category:This Month in Beaver Research|2026-08]]

Register machine

2026-09-19T16:54:39Z

AlephSquirrel: /* Analysis */ third register is unused

Register machine

2026-09-19T13:33:32Z

AlephSquirrel: new MBB(9) champion found by @mineralli

Pebble Automaton

2026-08-22T16:35:25Z

AlephSquirrel: Link to simulator

Pebble Automaton

2026-08-18T00:16:04Z

AlephSquirrel: New p(9) champion

Pebble Automaton

2026-08-17T23:00:58Z

AlephSquirrel: /* peBBle(9) */ fix analysis

Pebble Automaton

2026-08-17T14:21:20Z

AlephSquirrel: /* Analysis */ add p(9) analysis

Pebble Automaton

2026-08-17T01:34:23Z

AlephSquirrel: /* Busy Beaver function */ 4th value is now proven optimal

Pebble Automaton

2026-08-14T20:53:43Z

AlephSquirrel: /* Definition */ boop

Pebble Automaton

2026-08-14T16:44:12Z

AlephSquirrel: /* Busy Beaver function */ note about values at 0

Pebble Automaton

2026-08-14T16:42:57Z

AlephSquirrel: /* Definition */ the functions need to be defined at 0

Pebble Automaton

2026-08-12T19:23:14Z

AlephSquirrel: /* Busy Beaver function */ Explain notation

A pebble automaton is a type of [[cellular automaton]]. Each cell contains a non-negative number of pebbles, and the number of pebbles determines how many pebbles to push to each neighbor. Though pebble automata could be considered in any number of dimensions, investigation so far has primarily focused on 1 dimension.

A 1D pebble automaton is defined by two integer functions L(n) and R(n), defined over positive integers n, under the constraints:

* L(n) ≥ 0
* S(n) ≥ 0
* R(n) ≥ 0
* L(n) + S(n) + R(n) = n for all n

p(x, t) represents the number of pebbles at position x and time t.

* p(0, 0) = n
* p(x, 0) = 0 for x != 0
* p(x, t+1) = R(p(x-1, t)) + S(p(x,t)) + L(p(x+1, t))

Informally, when a cell has n pebbles, it pushes L(n) to its left neighbor, R(n) to its right neighbor and S(n) stay.

== Busy Beaver function ==
Let us define peBBle(n) as the maximum number of steps it takes for any pebble automaton to stabilize, starting from an initial state of n pebbles in a single cell.

Notation: <code><nowiki>n --> L(n) | S(n) | R(n)</nowiki></code>
{| class="wikitable"
|+
!n
!peBBln(n)
!Champion
|-
|1
|0
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
|-
|2
|1
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 0 | 1 | 1</code>
|-
|3
|3
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 1 | 1 | 0</code>

<code>3 --> 0 | 1 | 2</code>
|-
|4
|≥ 6
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 0 | 1 | 1</code>

<code>3 --> 2 | 1 | 0</code>

<code>4 --> 0 | 1 | 3</code>
|-
|5
|≥ 11
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 1 | 0 | 1</code>

<code>3 --> 0 | 0 | 3</code>

<code>4 --> 2 | 1 | 1</code>

<code>5 --> 0 | 1 | 4</code>
|-
|6
|≥ 17
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 1 | 0 | 1</code>

<code>3 --> 0 | 0 | 3</code>

<code>4 --> 2 | 1 | 1</code>

<code>5 --> 4 | 1 | 0</code>

<code>6 --> 1 | 0 | 5</code>
|-
|7
|≥ 28
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 1 | 0 | 1</code>

<code>3 --> 0 | 0 | 3</code>

<code>4 --> 2 | 1 | 1</code>

<code>5 --> 1 | 4 | 0</code>

<code>6 --> 3 | 0 | 3</code>

<code>7 --> 6 | 0 | 1</code>
|}

== Sources ==
Discord thread: https://discord.com/channels/960643023006490684/1535695107448381591

Pebble Automaton

2026-08-12T19:10:53Z

AlephSquirrel: Add paragraph for explanation

A pebble automaton is a type of [[cellular automaton]]. Each cell contains a non-negative number of pebbles, and the number of pebbles determines how many pebbles to push to each neighbor. Though pebble automata could be considered in any number of dimensions, investigation so far has primarily focused on 1 dimension.

A 1D pebble automaton is defined by two integer functions L(n) and R(n), defined over positive integers n, under the constraints:

* L(n) ≥ 0
* S(n) ≥ 0
* R(n) ≥ 0
* L(n) + S(n) + R(n) = n for all n

p(x, t) represents the number of pebbles at position x and time t.

* p(0, 0) = n
* p(x, 0) = 0 for x != 0
* p(x, t+1) = R(p(x-1, t)) + S(p(x,t)) + L(p(x+1, t))

Informally, when a cell has n pebbles, it pushes L(n) to its left neighbor, R(n) to its right neighbor and S(n) stay.

== Busy Beaver function ==
Let us define peBBle(n) as the maximum number of steps it takes for any pebble automaton to stabilize, starting from an initial state of n pebbles in a single cell.
{| class="wikitable"
|+
!n
!peBBln(n)
!Champion
|-
|1
|0
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
|-
|2
|1
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 0 | 1 | 1</code>
|-
|3
|3
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 1 | 1 | 0</code>

<code>3 --> 0 | 1 | 2</code>
|-
|4
|≥ 6
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 0 | 1 | 1</code>

<code>3 --> 2 | 1 | 0</code>

<code>4 --> 0 | 1 | 3</code>
|-
|5
|≥ 11
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 1 | 0 | 1</code>

<code>3 --> 0 | 0 | 3</code>

<code>4 --> 2 | 1 | 1</code>

<code>5 --> 0 | 1 | 4</code>
|-
|6
|≥ 17
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 1 | 0 | 1</code>

<code>3 --> 0 | 0 | 3</code>

<code>4 --> 2 | 1 | 1</code>

<code>5 --> 4 | 1 | 0</code>

<code>6 --> 1 | 0 | 5</code>
|-
|7
|≥ 28
|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
<code>2 --> 1 | 0 | 1</code>

<code>3 --> 0 | 0 | 3</code>

<code>4 --> 2 | 1 | 1</code>

<code>5 --> 1 | 4 | 0</code>

<code>6 --> 3 | 0 | 3</code>

<code>7 --> 6 | 0 | 1</code>
|}

== Sources ==
Discord thread: https://discord.com/channels/960643023006490684/1535695107448381591

TMBR: July 2026

2026-08-01T16:07:21Z

AlephSquirrel:

{{TMBRnav|June 2026|August 2026}}

''This edition of TMBR is in progress and has not yet been released. Please add any notes you think may be relevant (including in the form a of a TODO with a link to any relevant Discord discussion).''

== General ==

* TODO: BB(5) Lean proof completed: https://discord.com/channels/960643023006490684/1218877181321678928/1530515342772666429
* TODO: BBB(4) proof progress: https://discord.com/channels/960643023006490684/1385498968011575366/1532076512927420556

== BB Adjacent ==
[[SKI Calculus]]:
* A new champion was discovered for Ξ₀(12).
* New champions were discovered for Ξ₀_SK(12), Ξ₀_SK(13), Ξ₀_SK(14), Ξ₀_SK(15), Ξ₀_SK(16) and Ξ₀_SK(17).
TODO: update

[[Lambda Calculus]]:
* [https://discord.com/channels/960643023006490684/1355653587824283678/1528855324881326181 BBλ(40) was solved] on 20 July, showing that BBλ(40) ≈ 10↑↑↑16. BBλ(40) is the first solved domain in any BB variant to reach pentational values.
TODO: Post Tag System

TODO: Wang tiles (https://discord.com/channels/960643023006490684/1529586687926210691)

== Holdouts ==
{| class="wikitable"
|+BB Holdout Reduction by Domain
!Domain
!Previous Holdout Count
!New Holdout Count
!Holdout Reduction
!% Reduction
|-
|[[BB(6)]]
|1,094
|1,064
|30
|2.74%
|-
|[[BB(4,3)]]
|4,784,443
|4,747,566
|36,877
|0.77%
|}
* [[BB(6)]]:
** On 2 July, mxdys solved three holdouts in rocq.[https://discord.com/channels/960643023006490684/1239205785913790465/1522010493529751604][https://discord.com/channels/960643023006490684/1239205785913790465/1522209150699044904]
** On 3 July, mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1522617640554860574 solved another holdout] in rocq using an LLM.
** mxdys [https://discord.com/channels/960643023006490684/1239205785913790465/1531681818439319604 released] a new holdouts list of '''1,064''' machines up to equivalence, this is a '''2.74%''' reduction compared to the previous holdouts list.
** On 28 July, prurq [https://discord.com/channels/960643023006490684/1239205785913790465/1531564686238027976 found a TM to halt]. This was [https://discord.com/channels/960643023006490684/1239205785913790465/1532416648533901503 verified by mxdys] in rocq two days later together with another machine.
** TODO: BMO 9 and BMO 10
* [[BB(4,3)]]:
** Andrew Ducharme reduced the number of holdouts from 4,784,443 to '''4,747,566''', a '''0.77%''' reduction.[https://discord.com/channels/960643023006490684/1084047886494470185/1522168741922607164][https://discord.com/channels/960643023006490684/1084047886494470185/1530496818155229294]
*[[BB(2,7)]]:
**Terry Ligocki enumerated 180K more subtasks, increasing the number of holdouts to '''2,185,010,519'''. A total of 700K subtasks out of the 1 million subtasks (or '''70%''') have been enumerated.

[[Category:This Month in Beaver Research|2026-07]]

1RB1RE 1LC0RA 0RD1LB ---1RC 1LF1RE 0LB0LE

2026-07-20T19:22:36Z

AlephSquirrel: /* Relation to Other Math Problems */ Add some info on zero-in-the-corner

{{machine|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}{{unsolved|Does this TM run forever?}}
{{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}, called '''[[Beaver Math Olympiad|BMO]] #1''', is a [[holdout]] [[BB(6)]] TM discovered by @-d on 25 Jun 2024 which is modeled by the [[Piecewise Affine Function]]:

<pre>
A(a, b) -> A(a-b, 4b+2) if a > b
A(a, b) -> A(2a+1, b-a) if a Halt if a = b

Start A(1, 2)
</pre>

for <code>A(a, b) = 0^inf 10^{a-1} 0 1^b E> 0^inf</code>. The configuration is always valid because <math>a \ge 1</math> is always maintained. Forward simulations of this model by @-d and Andrew Ducharme do not halt after 100,000,000 iterations of the map <code>A(a,b)</code>. It is the inspiration for the [[Beaver Math Olympiad]].

The rules and the derivation of the function condition were proved in Lean<ref>https://github.com/rwst/bbchallenge/tree/main/1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE/machine.lean</ref>.

== Relation to Other Math Problems ==
This TM is a possible [[Cryptid]] since it seems hard to predict whether we could ever end up in <code>A(n, n)</code>. However, it is not (yet) classified as a Cryptid because there are no arguments for why this TM is hard (e.g., by comparing it to an open/unsolved/hard mathematical problem).

The map <code>A(., .)</code> is related to the study of discontinuous [https://en.wikipedia.org/wiki/Dynamical_system dynamical systems]. When +2 and +1 are ignored, the value of <math>\ln(a/b)</math> follows this chaotic map:

<math display="block">F(x) = \begin{cases}
\ln\left(\frac{e^x-1}{4}\right) & \text{if }x > 0 \\
\ln\left(\frac{2}{e^{-x}-1}\right) & \text{if }x < 0
\end{cases}</math>

Another potential BB(6) cryptid {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}} similarly iterates upon a tuple (x,y) with one function if x < y, another function if x > y, and halts if x = y.

This Turing Machine models a [[Piecewise Affine Function]], a class of iterated functions that are known to be [[Turing complete]] in general (similar to [[Generalized Collatz Problems]]).

=== Zero-in-the-corner problem ===
This TM is equivalent to a specific instance of the "Zero in the Left-Upper Corner" problem: it halts if and only if there is a finite product of the 3x3 matrices A' and B' with a 0 in the upper-left corner, where

<math>A'=\begin{pmatrix} 11 & 4 & 2 \\ -12 & -4 & -2 \\ -10 & -4 & -1 \end{pmatrix}, B'=\begin{pmatrix} -2 & -2 & -1 \\ 5 & 4 & 2 \\ 3 & 2 & 2 \end{pmatrix}</math>

See [https://wiki.bbchallenge.org/wiki/File:BMO1_Matrix_Proof.pdf BMO1 Matrix Proof].

This problem is known to be undecidable in general, and in particular with 5 3x3 matrices. It is not known if it is decidable with 2 3x3 matrices as given here.<ref>https://arxiv.org/pdf/1404.0644</ref>

== A Backward Reasoning Approach ==
An alternative approach is to work backwards and study the points which A(a,b) maps to the line a = b. For example, the points (2,7), (3,25), (4,71), and (5,181) all eventually map to a = b. (2,7) is immediately sent to a = b because, under the a A(2, 7) = (4 + 1, 7 - 2) = (5,5)</math>(5,181) requires more steps:

<math display="block">(5,181) \rightarrow (11, 176) \rightarrow (23, 165) \rightarrow (47, 142) \rightarrow (95, 95)</math>How are these points found? It's faster not to consider individual points, but as Racheline identified, the set of lines which are mapped to a = b. Introducing an index <math>n</math>, we can rewrite A(a,b) as<math display="block">(x_{n+1}, y_{n+1}) = \begin{cases} (x_n - y_n, 4y_n + 2), & \text{if } x_n \geq y_n \\ (2x_n + 1, y_n - x_n), & \text{if } x_n < y_n \end{cases}</math> If <math>x_{n+1} = y_{n+1}</math>{{machine|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE}}, then the lines with slopes <math>y_{n+1} = m x_{n+1} + b</math> map to that line. The two possible slopes are, for <math>x_n > y_n</math>and <math>x_n < y_n</math> respectively,

<math>4y_n + 2 = m (x_n - y_n) + b \iff y_n = \frac{m}{m + 4} x_n + \frac{b - 2}{m + 4}

</math> and<math>y_n - x_n = m (2 x_n + 1) + b \iff y_n = (2m + 1) x_n + (b + m).</math>

Indexing m and b in (slope, y-intercept) space gives

<math>(m_{k-1}, b_{k-1}) = \begin{cases}\left( \frac{m_k}{m_k + 4}, \frac{b_k - 2}{m_k + 4} \right), &x_{k-1} > y_{k-1} \\ (2m_k + 1, b_k + m_k), & x_{k-1} < y_{k-1} \end{cases}</math>.

Iteratively applying this (m,b) map finds an infinite set of points which A sends to a = b. The starting point is said line, with (m, b) = (1,0). Then the two lines of points which map to points on the line (m,b) = (1,0) under a single application A have slopes and y-intercepts of <math>\left(\frac{1}{5}, -\frac{2}{5} \right) = \left(\frac{1}{1 + 4}, \frac{0-2}{1+4} \right) </math> and (3,1) = (2 + 1, 0 + 1). The four lines of points which map to (1,0) under two applications of A have slopes and y-intercepts <math>\left(\frac{1}{21}, -\frac{4}{7} \right), \left(\frac{7}{5}, -\frac{1}{5} \right), \left(\frac{3}{7}, -\frac{1}{7} \right)</math> and (7,4).
[[File:Slope intercept space after 5 iterations.png|thumb|Each point in the plotted (slope, intercept) space represents a line of points in (x,y) space that are eventually mapped to y = x by iterated application of the operation A. These points require five or fewer iterations to do so.]]
[[File:(m,b) space after 9 iterations with halting condition line.png|thumb|Each plotted point in (slope, intercept) space represents a line of points in (x,y) space which is mapped to y = x by nine or fewer iterated applications of A. If any point is on the black line, the TM in question halts.]]
To apply this to the problem at hand, we want to know if any of these generated lines contain the point (1,2), our TM-derived initial condition. The set of all lines (in position space, or (x,y) space) containing (1,2) are described by the line in (m,b) space 2 = m + b. If any of the generated points in (m,b) space sit on 2 = m + b, then the point (x,y) = (1,2) is eventually mapped by A to a point where x = y. In the second image, of (m,b) points after nine iterations, we see there are three possible locations for this to occur.
[[File:MbSpace iterations10 smallmb wline.png|center|thumb|575x575px|Each plotted point in (slope, intercept) space represents a line of points in (x,y) space which is mapped to y = x by ten or fewer iterated applications of A, with m > 2 and b > 0. If any point is on the black line, the TM in question halts. There are three possible locations. Two do not hit the line (in finite time). The third's status is unknown.]]

=== Location 1: Approaching (m = 1, b= 1) from below ===
There's two ways to see how (1,1) is not actually an intersection point. First, from Racheline, the elementary one: if m > b, m will always be greater than b, so a point where m = b is impossible.

Second, from Andrew, if one wants to generate a point near m = 1, you should create the largest possible value M to swamp out the additive +4 in the denominator of M/(M+4). M can be maximized with n iterations of the (m,b) map by only using the x < y operation. Then apply the x > y operation once for a near-unitary slope. The pair <math>(m_n, b_n)</math> formed by applying the x < y operation n times to (1,0) is <math>(2^{n+1}-1, 2^{n+1} -n-2)</math>. Apply the x > y operation to get

<math>\left( \frac{2^{n+1} - 1}{2^{n+1} + 3}, \frac{2^{n+1} -n-4}{2^{n+1}+3} \right)</math>.

Taking the limit as n goes to infinity, we get (1,1), so this TM does not reach the line 2 = m + b here in finite time.

=== Location 2: Approaching (m = 13/7, b = 4/21) from above ===
The rightmost possible intersection is the least likely: its approach towards 2 = m + b slows considerably with increasing iterations (because its limit will end up being to above this line). Empirically examining these points, they appear to be near (1.85, 0.19). After 6 through 9 iterations, the closest of the generated (m,b) points to (1.85, 0.19) are (285/151, 37/151), (1117/599, 123/599), (4445/2391, 155/797), and (17757/9559, 1831/9559). Such points are formed by n applications of the (m,b) map when x > y, then two applications of the (m,b) map when x < y, then a single additional application of the x > y and x < y (m,b) maps, in that order. A more concise notation would be <math>(>^n, <^2, >, <)</math>.

A closed form equation in n for <math>(>^n, <^2, >, <)</math> starting from (1,0) is <math>\left( \frac{13 * 4^{n+1} + 23}{7* 4^{n+1} + 5}, \frac{4^{n+2} + 6n + 65}{21 * 4^{n+1} + 15} \right)</math>. Its limit as <math>n \rightarrow \infty</math> is <math>\left( \frac{13}{7}, \frac{4}{21} \right)</math>, which is safely above 2 = m + b. This strand of points will never cause a halting condition.

Racheline showed the same by applying the bounds m > 0 and <math>b > - \frac{2}{3}</math> on the sequence <math>(<^2, >, <)</math>:

<math>\begin{align} m_0 > 0, b_0 > - \frac{2}{3} &\implies m_1 > 1, b_1 > -\frac{2}{3} \\
&\implies m_2 > 3, b_2 > \frac{1}{3} \\
&\implies m_3 > \frac{3}{7}, b_3 > -\frac{5}{21} \\
&\implies m_4 > \frac{13}{7}, b_4 > \frac{4}{21}
\end{align}</math>

Since the combination of operations is empirically determined, this isn't strictly a proof, but the moderate distance of these points from 2 = m + b means the burden of proof isn't that high.

=== Location 3: Jumping above and below b = 2 - m around m = 1.76...infinitely? ===
Notes from my (Andrew) analysis, from when I tried to repeat looking at the points closest to the not-quite-intersection of the sparse set and line b = 2 - m. I went 25 iterations of the slope map before realizing it was likely a fractal and zooming in would give me more of the same:
Slopes of points (m,b) closest to the line m = 2 - b from above and below

13/7 for n = 5 is above and to the right, 119/69 for n = 6 is below and to the left, 223/125 for n = 7 is above and to the right, 669/401 for n = 8 is below left.
Things start to get more complicated at n = 9, as the doubling of dots becomes a little overwhelming.
So many dots at n = 13 you have to zoom in
n = 9 above: 223/125, n = 9 below: 1145/651
n = 10 above: 2037/1151, n = 10 below: 1145/651 (still)
n = 11 above: 6617/3755, n = 11 below: 1145/651 (still)
n = 12 above: 6617/3755 (still), n = 12 below: 24937/14171
n = 13 above: 6617/3755 (still), n = 13 below: 38171/21681
n = 14 above: 6617/3755 (still), n = 14 below: 64639/36701
n = 15 above: 117575/66741, n = 15 below: 64639/36701 (still)
n = 16 above: 117575/66741 (still), n = 16 below: 376131/213545
n = 17 above: 611281/347027, n = 17 below: 376131/213545 (still).
b for the new point here is 2 / 347027 from being on the line!!
At n = 17, have we crossed the Rubicon? This super close point is just above the line, so is anything new now above it?
No! yowza.
n = 18 above: 611281/347027 (still), n = 18 below: 611281/347027.
n = 19 above: 611281/347027 (still), n = 19 below: 2115805/1201207
n = 20 above: 611281/347027 (still), n = 20 below: 3338367/1895261
n = 21 above:611281/347027 (still) , n = 21 below: 10673739/6059585
There's a new point next to our hero which is just to the right and just above. Above trend hitting limit point?
NO!!
n = 22 above: 208917121/118603171, n = 22 below: 20454235/11612017 I might be seeing a new trend line forming
n = 23 above: 834868865/473958819, n = 23 below: 40015227/22716881
n = 24 above: 3338675841/1895381411, n = 24 below: 40015227/22716881 (still)
n = 25 above: 79137211/44926609, n = 25 below: 239198119/135794133

I think I'm zooming in on a fractal structure and will never see the end of this.
[[File:Screenshot of (m,b) set as we zoom in on possible intersection.png|center|thumb|636x636px|To demonstrate the fractal, the generated (m,b) set after n iterations for n = 9, n = 15, n = 20, and n = 25. Note the change in scale on the horizontal and vertical axes. I'm roughly specifying another decimal place in the axes bounds as I look at smaller and smaller region. Largely a copy of post @aducharme [https://discord.com/channels/960643023006490684/1026577255754903572/1267352007811797012 July 27th, 2024 10:24 PM PT]]]
Unless we actually hit the halting condition, we can generate an infinite number of blue points arbitrarily close to the yellow line from both above and below.

It does appear that points within roughly the range 1.724 < m < 1.8556 are generated from finding all possible combinations of operations > and < after n applications, then applying <math>(<,<,<,>,<,>,<) = (<^4, (>,<)^2) = (<^4, >,<,>,<)</math>. This is equivalent to <math display="block">(m_f,b_f) = \left( \frac{104m_n + 119}{56 m_n + 69}, \frac{23m_n + b_n + 12}{56m_n + 69} \right).</math>

== Study of Simplified Model ==
@savask [https://discord.com/channels/960643023006490684/1026577255754903572/1255778174986485780 06/26/2024 11:54 PM]
Maybe we could tackle a simplified version of this problem? For example, let's remove the constant terms:

(a, b) -> (a-b, 4*b) if a > b
(a, b) -> (2*a, b-a) if b > a
(a, b) -> Halt if a = b

And let's start from config (3,17), since it appears in the run of the original machine.
The average increase in <math>\ln a</math> is

<math>\frac{-\frac{\pi^2}{12} + 3 \frac{(\ln 2)^2 }{2} + \text{Li}_2(1/4)}{\ln 3} \approx 0.15097694</math>

when modeled from the PDF

<math>f(r) = \frac{2}{\ln 3 (r+1)(r+3)}</math>

in <math>r = b/a</math>, as found by [https://discord.com/channels/960643023006490684/1026577255754903572/1256315391995809842 @LegionMammal978] and Math.SE user "Sil".<ref>https://math.stackexchange.com/questions/4939082/solving-the-functional-equation-fx-frac4x42f-frac-xx42f2x1/4939136#4939136</ref>

Note that the simplified iteration trivially cannot halt as written: after 2 steps, it reaches <math>(12, 8)</math> and becomes trapped within the families <math>(a, b) \equiv (0, 4)</math> and <math>(a, b) \equiv (4, 0) \pmod{8}</math>.

== Development of Model from TM Tape ==
@-d [https://discord.com/channels/960643023006490684/1026577255754903572/1255047256688824390 25 Jun 2024 2:29 AM ET]:
<pre>
Let f(a,b) represent (10)^a D> 1^b. By inspection, the machine visits f(0,3) f(2,2) f(1,7) f(4,5) f(0,19) f(2,18) f(6,15) f(14,8).

I got these rules for f(a,b) and verified them up to 0<=a<=100 and 1<=b<=100.
f(a,b) -> f(a-b+1,4b-1) if b < a+2
f(a,a+2) -> halt
f(a,b) -> f(2a+2,b-a-1) if b > a+2

I ran these rules from f(0,3) and gave up after reaching a,b > 2^1000000. It looks like halting becomes less and less likely. Is there a way to show this runs forever (or miraculously halts)?
</pre>

@Shawn Ligocki — [https://discord.com/channels/960643023006490684/1026577255754903572/1255371132694167591 25 Jun 2024 at 11:56 PM ET]:
<pre>
I can confirm roughly the same rules (I chose a slightly different standard config):
1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE

E(a, b, c) = 0^inf 10^a 0 10^b 1^c E> 0^inf

Base Rules:
E(a+1, b, c+2) -> E(a, b+2, c+1)
E(a+1, b, 1) -> E(a, 0, 2b+6)
E(0, b, c+2) -> E(b+2, 0, c+1)
E(0, b, 1) -> Halt(b+4)

High-level Rules:
E(a, 0, c+1) --> E(a-c-1, 0, 4c+6) if a > c
E(a, 0, c+1) --> E(2a+2, 0, c-a) if a < c
E(a, 0, c+1) --> Halt(2c+4) if a = c

Connecting to your notation @-d : f(a, b+2) -> E(a, 0, b+1)
</pre>

@Shawn Ligocki — 26 Jun 2024 at 12:25 AM
<pre>
Hm, this is interesting. I decided to track "spread" akin to what @savask and I have been looking at for the similar 3x3 TM we're looking at in ⁠bbxy . Here I define spread = abs(a - c) in config E1(a, c) = E(a, 0, c+1). Here's the results I have so far:
1 E1(2, 0) spread: [2, 2] (0.06s)
100_001 E1(10^6_557, 10^6_555) spread: [1, 10^6_557] (0.44s)
200_001 E1(10^13_124, 10^13_125) spread: [10^6_557, 10^13_125] (1.27s)
300_001 E1(10^19_670, 10^19_669) spread: [10^13_123, 10^19_670] (2.52s)
400_001 E1(10^26_235, 10^26_237) spread: [10^19_668, 10^26_237] (4.23s)
500_001 E1(10^32_799, 10^32_799) spread: [10^26_235, 10^32_799] (6.39s)
600_001 E1(10^39_350, 10^39_352) spread: [10^32_799, 10^39_352] (8.98s)
700_001 E1(10^45_930, 10^45_930) spread: [10^39_350, 10^45_930] (12.06s)
800_001 E1(10^52_486, 10^52_486) spread: [10^45_929, 10^52_486] (15.54s)
900_001 E1(10^59_046, 10^59_047) spread: [10^52_485, 10^59_047] (19.57s)
1_000_001 E1(10^65_613, 10^65_612) spread: [10^59_045, 10^65_613] (24.05s)
1_100_001 E1(10^72_154, 10^72_153) spread: [10^65_609, 10^72_154] (28.92s)
1_200_001 E1(10^78_728, 10^78_729) spread: [10^72_153, 10^78_729] (34.21s)
1_300_001 E1(10^85_288, 10^85_289) spread: [10^78_729, 10^85_289] (40.03s)
1_400_001 E1(10^91_830, 10^91_829) spread: [10^85_288, 10^91_829] (46.40s)
1_500_001 E1(10^98_394, 10^98_393) spread: [10^91_829, 10^98_394] (53.11s)
1_600_001 E1(10^104_961, 10^104_959) spread: [10^98_393, 10^104_961] (60.18s)
1_700_001 E1(10^111_523, 10^111_523) spread: [10^104_958, 10^111_523] (67.75s)
1_800_001 E1(10^118_088, 10^118_088) spread: [10^111_523, 10^118_088] (75.77s)
1_900_001 E1(10^124_631, 10^124_630) spread: [10^118_088, 10^124_631] (84.39s)
2_000_001 E1(10^131_185, 10^131_185) spread: [10^124_630, 10^131_185] (93.41s)
...
3_000_001 E1(10^196_733, 10^196_733) spread: [10^190_163, 10^196_733] (217.87s)

Here spread: [X, Y] means that the spread values (since last print) had min X, max Y
So notice that the spread is basically uniformly increasing. In fact these [X, Y] intervals hardly even overlap!
That makes me think there's something about this that makes small spread impossible (and thus halt impossible)
Or that it's like Bigfoot and it ... could go back to zero, but the chances are infinitesimal!
</pre>

savask — 26 Jun 2024 at 1:02 AM
<pre>
Maybe we can simplify a little bit more. Set (a, c) = E(a, 0, c+1) then the rules are
(a, c) -> (a-c-1, 4c+5) if a > c
(a, c) -> (2a+2, c-a-1) if a < c
(a, c) -> Halt if a = c

I like that this way they are more symmetrical with a-c-1 vs c-a-1
</pre>

Shawn Ligocki — 26 Jun 2024 at 2:33 AM
<pre>
FWIW, there is a value x ~= 1.76 such that as c -> inf: (xc, c) -> (xyc, yc) via path "rll" (right->0 [ie a > c], left->0 [ie a < c], left->0). Which would repeat forever if it were exact, but it is an unstable cycle so any slight deviation and it gets further and further away, so that doesn't seem like a reasonable proof direction :/
</pre>dyuan01 — 26 Jun 2024 at 2:32 PM
If we let A(a, c) = (a-1, c-1), we can get these rules:
```
A(a, c) -> A(a-c, 4c+2) if a > c
A(a, c) -> A(2a+1, c-a) if a < c
A(a, c) -> Halt if a = c
```
And we start with (1, 2)

I'm not sure if it even helps, but at least the rules look slightly more "human-manageable"

== Analysis by Bard ==
Under a change of coordinates, the BMO1 rules approach a 1D line in the limit as the number of steps tends to infinity. Analysing the dynamics of points on that 1D line, it is possible to prove any given point on the line either halting or looping. Unfortunately, since at finite time, the point only gets arbitrarily close to the limiting line and never reaches it, it is not clear (to me at least) how to make use of this fact to solve BMO1. See the paper at [https://wiki.bbchallenge.org/w/images/9/94/BMO1-Bard.pdf BMO1 - Bard.pdf].

== Review 2026-Apr-19 by Opus 4.7 ==
<pre>
- backward (m,b) algebra: correct. Location 1 closed form and m>b invariant verified. Location 2's
Racheline suffix bound m+b > 43/21 is a genuine lemma but relies on an empirical claim about which suffixes
can appear. Location 3 (fractal near m≈1.76) is the real unresolved obstacle.
- Bard's PDF: homogenisation and 1D limit correct; z_n→0 asserted without proof (short argument sketched in
critique); density argument fine modulo a boundary point where f'=1; odd-denominator lemma elegant and
correct; same-trajectory lemma covers branch matching but glosses the halt case (fixable via nested
intervals).
- Bottom line: neither work proves BMO1. The wiki localises the difficulty to a fractal; Bard reduces it to
irrationality of α≈0.3621250257705563 — dual views of the same single-bit obstruction. Progress likely
needs an ergodic/entropy argument on the 1D map, not more enumeration.
</pre>

== References ==
[[Category:BB(6)]]
[[Category:Potential Cryptids]]

1RB1RE 1LC0RA 0RD1LB ---1RC 1LF1RE 0LB0LE

2026-07-19T01:23:10Z

AlephSquirrel: /* Zero-in-the-corner problem */ fix link

{{machine|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}{{unsolved|Does this TM run forever?}}
{{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}, called '''[[Beaver Math Olympiad|BMO]] #1''', is a [[holdout]] [[BB(6)]] TM discovered by @-d on 25 Jun 2024 which is modeled by the [[Piecewise Affine Function]]:

<pre>
A(a, b) -> A(a-b, 4b+2) if a > b
A(a, b) -> A(2a+1, b-a) if a Halt if a = b

Start A(1, 2)
</pre>

for <code>A(a, b) = 0^inf 10^{a-1} 0 1^b E> 0^inf</code>. The configuration is always valid because <math>a \ge 1</math> is always maintained. Forward simulations of this model by @-d and Andrew Ducharme do not halt after 100,000,000 iterations of the map <code>A(a,b)</code>. It is the inspiration for the [[Beaver Math Olympiad]].

The rules and the derivation of the function condition were proved in Lean<ref>https://github.com/rwst/bbchallenge/tree/main/1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE/machine.lean</ref>.

== Relation to Other Math Problems ==
This TM is a possible [[Cryptid]] since it seems hard to predict whether we could ever end up in <code>A(n, n)</code>. However, it is not (yet) classified as a Cryptid because there are no arguments for why this TM is hard (e.g., by comparing it to an open/unsolved/hard mathematical problem).

The map <code>A(., .)</code> is related to the study of discontinuous [https://en.wikipedia.org/wiki/Dynamical_system dynamical systems]. When +2 and +1 are ignored, the value of <math>\ln(a/b)</math> follows this chaotic map:

<math display="block">F(x) = \begin{cases}
\ln\left(\frac{e^x-1}{4}\right) & \text{if }x > 0 \\
\ln\left(\frac{2}{e^{-x}-1}\right) & \text{if }x < 0
\end{cases}</math>

Another potential BB(6) cryptid {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}} similarly iterates upon a tuple (x,y) with one function if x < y, another function if x > y, and halts if x = y.

This Turing Machine models a [[Piecewise Affine Function]], a class of iterated functions that are known to be [[Turing complete]] in general (similar to [[Generalized Collatz Problems]]).

=== Zero-in-the-corner problem ===
This TM is equivalent to a specific instance of the "zero-in-the-corner" problem: it halts if and only if there is a finite product of the 3x3 matrices A' and B' with a 0 in the upper-left corner, where

<math>A'=\begin{pmatrix} 11 & 4 & 2 \\ -12 & -4 & -2 \\ -10 & -4 & -1 \end{pmatrix}, B'=\begin{pmatrix} -2 & -2 & -1 \\ 5 & 4 & 2 \\ 3 & 2 & 2 \end{pmatrix}</math>

See [https://wiki.bbchallenge.org/wiki/File:BMO1_Matrix_Proof.pdf BMO1 Matrix Proof].

== A Backward Reasoning Approach ==
An alternative approach is to work backwards and study the points which A(a,b) maps to the line a = b. For example, the points (2,7), (3,25), (4,71), and (5,181) all eventually map to a = b. (2,7) is immediately sent to a = b because, under the a A(2, 7) = (4 + 1, 7 - 2) = (5,5)</math>(5,181) requires more steps:

<math display="block">(5,181) \rightarrow (11, 176) \rightarrow (23, 165) \rightarrow (47, 142) \rightarrow (95, 95)</math>How are these points found? It's faster not to consider individual points, but as Racheline identified, the set of lines which are mapped to a = b. Introducing an index <math>n</math>, we can rewrite A(a,b) as<math display="block">(x_{n+1}, y_{n+1}) = \begin{cases} (x_n - y_n, 4y_n + 2), & \text{if } x_n \geq y_n \\ (2x_n + 1, y_n - x_n), & \text{if } x_n < y_n \end{cases}</math> If <math>x_{n+1} = y_{n+1}</math>{{machine|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE}}, then the lines with slopes <math>y_{n+1} = m x_{n+1} + b</math> map to that line. The two possible slopes are, for <math>x_n > y_n</math>and <math>x_n < y_n</math> respectively,

<math>4y_n + 2 = m (x_n - y_n) + b \iff y_n = \frac{m}{m + 4} x_n + \frac{b - 2}{m + 4}

</math> and<math>y_n - x_n = m (2 x_n + 1) + b \iff y_n = (2m + 1) x_n + (b + m).</math>

Indexing m and b in (slope, y-intercept) space gives

<math>(m_{k-1}, b_{k-1}) = \begin{cases}\left( \frac{m_k}{m_k + 4}, \frac{b_k - 2}{m_k + 4} \right), &x_{k-1} > y_{k-1} \\ (2m_k + 1, b_k + m_k), & x_{k-1} < y_{k-1} \end{cases}</math>.

Iteratively applying this (m,b) map finds an infinite set of points which A sends to a = b. The starting point is said line, with (m, b) = (1,0). Then the two lines of points which map to points on the line (m,b) = (1,0) under a single application A have slopes and y-intercepts of <math>\left(\frac{1}{5}, -\frac{2}{5} \right) = \left(\frac{1}{1 + 4}, \frac{0-2}{1+4} \right) </math> and (3,1) = (2 + 1, 0 + 1). The four lines of points which map to (1,0) under two applications of A have slopes and y-intercepts <math>\left(\frac{1}{21}, -\frac{4}{7} \right), \left(\frac{7}{5}, -\frac{1}{5} \right), \left(\frac{3}{7}, -\frac{1}{7} \right)</math> and (7,4).
[[File:Slope intercept space after 5 iterations.png|thumb|Each point in the plotted (slope, intercept) space represents a line of points in (x,y) space that are eventually mapped to y = x by iterated application of the operation A. These points require five or fewer iterations to do so.]]
[[File:(m,b) space after 9 iterations with halting condition line.png|thumb|Each plotted point in (slope, intercept) space represents a line of points in (x,y) space which is mapped to y = x by nine or fewer iterated applications of A. If any point is on the black line, the TM in question halts.]]
To apply this to the problem at hand, we want to know if any of these generated lines contain the point (1,2), our TM-derived initial condition. The set of all lines (in position space, or (x,y) space) containing (1,2) are described by the line in (m,b) space 2 = m + b. If any of the generated points in (m,b) space sit on 2 = m + b, then the point (x,y) = (1,2) is eventually mapped by A to a point where x = y. In the second image, of (m,b) points after nine iterations, we see there are three possible locations for this to occur.
[[File:MbSpace iterations10 smallmb wline.png|center|thumb|575x575px|Each plotted point in (slope, intercept) space represents a line of points in (x,y) space which is mapped to y = x by ten or fewer iterated applications of A, with m > 2 and b > 0. If any point is on the black line, the TM in question halts. There are three possible locations. Two do not hit the line (in finite time). The third's status is unknown.]]

=== Location 1: Approaching (m = 1, b= 1) from below ===
There's two ways to see how (1,1) is not actually an intersection point. First, from Racheline, the elementary one: if m > b, m will always be greater than b, so a point where m = b is impossible.

Second, from Andrew, if one wants to generate a point near m = 1, you should create the largest possible value M to swamp out the additive +4 in the denominator of M/(M+4). M can be maximized with n iterations of the (m,b) map by only using the x < y operation. Then apply the x > y operation once for a near-unitary slope. The pair <math>(m_n, b_n)</math> formed by applying the x < y operation n times to (1,0) is <math>(2^{n+1}-1, 2^{n+1} -n-2)</math>. Apply the x > y operation to get

<math>\left( \frac{2^{n+1} - 1}{2^{n+1} + 3}, \frac{2^{n+1} -n-4}{2^{n+1}+3} \right)</math>.

Taking the limit as n goes to infinity, we get (1,1), so this TM does not reach the line 2 = m + b here in finite time.

=== Location 2: Approaching (m = 13/7, b = 4/21) from above ===
The rightmost possible intersection is the least likely: its approach towards 2 = m + b slows considerably with increasing iterations (because its limit will end up being to above this line). Empirically examining these points, they appear to be near (1.85, 0.19). After 6 through 9 iterations, the closest of the generated (m,b) points to (1.85, 0.19) are (285/151, 37/151), (1117/599, 123/599), (4445/2391, 155/797), and (17757/9559, 1831/9559). Such points are formed by n applications of the (m,b) map when x > y, then two applications of the (m,b) map when x < y, then a single additional application of the x > y and x < y (m,b) maps, in that order. A more concise notation would be <math>(>^n, <^2, >, <)</math>.

A closed form equation in n for <math>(>^n, <^2, >, <)</math> starting from (1,0) is <math>\left( \frac{13 * 4^{n+1} + 23}{7* 4^{n+1} + 5}, \frac{4^{n+2} + 6n + 65}{21 * 4^{n+1} + 15} \right)</math>. Its limit as <math>n \rightarrow \infty</math> is <math>\left( \frac{13}{7}, \frac{4}{21} \right)</math>, which is safely above 2 = m + b. This strand of points will never cause a halting condition.

Racheline showed the same by applying the bounds m > 0 and <math>b > - \frac{2}{3}</math> on the sequence <math>(<^2, >, <)</math>:

<math>\begin{align} m_0 > 0, b_0 > - \frac{2}{3} &\implies m_1 > 1, b_1 > -\frac{2}{3} \\
&\implies m_2 > 3, b_2 > \frac{1}{3} \\
&\implies m_3 > \frac{3}{7}, b_3 > -\frac{5}{21} \\
&\implies m_4 > \frac{13}{7}, b_4 > \frac{4}{21}
\end{align}</math>

Since the combination of operations is empirically determined, this isn't strictly a proof, but the moderate distance of these points from 2 = m + b means the burden of proof isn't that high.

=== Location 3: Jumping above and below b = 2 - m around m = 1.76...infinitely? ===
Notes from my (Andrew) analysis, from when I tried to repeat looking at the points closest to the not-quite-intersection of the sparse set and line b = 2 - m. I went 25 iterations of the slope map before realizing it was likely a fractal and zooming in would give me more of the same:
Slopes of points (m,b) closest to the line m = 2 - b from above and below

13/7 for n = 5 is above and to the right, 119/69 for n = 6 is below and to the left, 223/125 for n = 7 is above and to the right, 669/401 for n = 8 is below left.
Things start to get more complicated at n = 9, as the doubling of dots becomes a little overwhelming.
So many dots at n = 13 you have to zoom in
n = 9 above: 223/125, n = 9 below: 1145/651
n = 10 above: 2037/1151, n = 10 below: 1145/651 (still)
n = 11 above: 6617/3755, n = 11 below: 1145/651 (still)
n = 12 above: 6617/3755 (still), n = 12 below: 24937/14171
n = 13 above: 6617/3755 (still), n = 13 below: 38171/21681
n = 14 above: 6617/3755 (still), n = 14 below: 64639/36701
n = 15 above: 117575/66741, n = 15 below: 64639/36701 (still)
n = 16 above: 117575/66741 (still), n = 16 below: 376131/213545
n = 17 above: 611281/347027, n = 17 below: 376131/213545 (still).
b for the new point here is 2 / 347027 from being on the line!!
At n = 17, have we crossed the Rubicon? This super close point is just above the line, so is anything new now above it?
No! yowza.
n = 18 above: 611281/347027 (still), n = 18 below: 611281/347027.
n = 19 above: 611281/347027 (still), n = 19 below: 2115805/1201207
n = 20 above: 611281/347027 (still), n = 20 below: 3338367/1895261
n = 21 above:611281/347027 (still) , n = 21 below: 10673739/6059585
There's a new point next to our hero which is just to the right and just above. Above trend hitting limit point?
NO!!
n = 22 above: 208917121/118603171, n = 22 below: 20454235/11612017 I might be seeing a new trend line forming
n = 23 above: 834868865/473958819, n = 23 below: 40015227/22716881
n = 24 above: 3338675841/1895381411, n = 24 below: 40015227/22716881 (still)
n = 25 above: 79137211/44926609, n = 25 below: 239198119/135794133

I think I'm zooming in on a fractal structure and will never see the end of this.
[[File:Screenshot of (m,b) set as we zoom in on possible intersection.png|center|thumb|636x636px|To demonstrate the fractal, the generated (m,b) set after n iterations for n = 9, n = 15, n = 20, and n = 25. Note the change in scale on the horizontal and vertical axes. I'm roughly specifying another decimal place in the axes bounds as I look at smaller and smaller region. Largely a copy of post @aducharme [https://discord.com/channels/960643023006490684/1026577255754903572/1267352007811797012 July 27th, 2024 10:24 PM PT]]]
Unless we actually hit the halting condition, we can generate an infinite number of blue points arbitrarily close to the yellow line from both above and below.

It does appear that points within roughly the range 1.724 < m < 1.8556 are generated from finding all possible combinations of operations > and < after n applications, then applying <math>(<,<,<,>,<,>,<) = (<^4, (>,<)^2) = (<^4, >,<,>,<)</math>. This is equivalent to <math display="block">(m_f,b_f) = \left( \frac{104m_n + 119}{56 m_n + 69}, \frac{23m_n + b_n + 12}{56m_n + 69} \right).</math>

== Study of Simplified Model ==
@savask [https://discord.com/channels/960643023006490684/1026577255754903572/1255778174986485780 06/26/2024 11:54 PM]
Maybe we could tackle a simplified version of this problem? For example, let's remove the constant terms:

(a, b) -> (a-b, 4*b) if a > b
(a, b) -> (2*a, b-a) if b > a
(a, b) -> Halt if a = b

And let's start from config (3,17), since it appears in the run of the original machine.
The average increase in <math>\ln a</math> is

<math>\frac{-\frac{\pi^2}{12} + 3 \frac{(\ln 2)^2 }{2} + \text{Li}_2(1/4)}{\ln 3} \approx 0.15097694</math>

when modeled from the PDF

<math>f(r) = \frac{2}{\ln 3 (r+1)(r+3)}</math>

in <math>r = b/a</math>, as found by [https://discord.com/channels/960643023006490684/1026577255754903572/1256315391995809842 @LegionMammal978] and Math.SE user "Sil".<ref>https://math.stackexchange.com/questions/4939082/solving-the-functional-equation-fx-frac4x42f-frac-xx42f2x1/4939136#4939136</ref>

Note that the simplified iteration trivially cannot halt as written: after 2 steps, it reaches <math>(12, 8)</math> and becomes trapped within the families <math>(a, b) \equiv (0, 4)</math> and <math>(a, b) \equiv (4, 0) \pmod{8}</math>.

== Development of Model from TM Tape ==
@-d [https://discord.com/channels/960643023006490684/1026577255754903572/1255047256688824390 25 Jun 2024 2:29 AM ET]:
<pre>
Let f(a,b) represent (10)^a D> 1^b. By inspection, the machine visits f(0,3) f(2,2) f(1,7) f(4,5) f(0,19) f(2,18) f(6,15) f(14,8).

I got these rules for f(a,b) and verified them up to 0<=a<=100 and 1<=b<=100.
f(a,b) -> f(a-b+1,4b-1) if b < a+2
f(a,a+2) -> halt
f(a,b) -> f(2a+2,b-a-1) if b > a+2

I ran these rules from f(0,3) and gave up after reaching a,b > 2^1000000. It looks like halting becomes less and less likely. Is there a way to show this runs forever (or miraculously halts)?
</pre>

@Shawn Ligocki — [https://discord.com/channels/960643023006490684/1026577255754903572/1255371132694167591 25 Jun 2024 at 11:56 PM ET]:
<pre>
I can confirm roughly the same rules (I chose a slightly different standard config):
1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE

E(a, b, c) = 0^inf 10^a 0 10^b 1^c E> 0^inf

Base Rules:
E(a+1, b, c+2) -> E(a, b+2, c+1)
E(a+1, b, 1) -> E(a, 0, 2b+6)
E(0, b, c+2) -> E(b+2, 0, c+1)
E(0, b, 1) -> Halt(b+4)

High-level Rules:
E(a, 0, c+1) --> E(a-c-1, 0, 4c+6) if a > c
E(a, 0, c+1) --> E(2a+2, 0, c-a) if a < c
E(a, 0, c+1) --> Halt(2c+4) if a = c

Connecting to your notation @-d : f(a, b+2) -> E(a, 0, b+1)
</pre>

@Shawn Ligocki — 26 Jun 2024 at 12:25 AM
<pre>
Hm, this is interesting. I decided to track "spread" akin to what @savask and I have been looking at for the similar 3x3 TM we're looking at in ⁠bbxy . Here I define spread = abs(a - c) in config E1(a, c) = E(a, 0, c+1). Here's the results I have so far:
1 E1(2, 0) spread: [2, 2] (0.06s)
100_001 E1(10^6_557, 10^6_555) spread: [1, 10^6_557] (0.44s)
200_001 E1(10^13_124, 10^13_125) spread: [10^6_557, 10^13_125] (1.27s)
300_001 E1(10^19_670, 10^19_669) spread: [10^13_123, 10^19_670] (2.52s)
400_001 E1(10^26_235, 10^26_237) spread: [10^19_668, 10^26_237] (4.23s)
500_001 E1(10^32_799, 10^32_799) spread: [10^26_235, 10^32_799] (6.39s)
600_001 E1(10^39_350, 10^39_352) spread: [10^32_799, 10^39_352] (8.98s)
700_001 E1(10^45_930, 10^45_930) spread: [10^39_350, 10^45_930] (12.06s)
800_001 E1(10^52_486, 10^52_486) spread: [10^45_929, 10^52_486] (15.54s)
900_001 E1(10^59_046, 10^59_047) spread: [10^52_485, 10^59_047] (19.57s)
1_000_001 E1(10^65_613, 10^65_612) spread: [10^59_045, 10^65_613] (24.05s)
1_100_001 E1(10^72_154, 10^72_153) spread: [10^65_609, 10^72_154] (28.92s)
1_200_001 E1(10^78_728, 10^78_729) spread: [10^72_153, 10^78_729] (34.21s)
1_300_001 E1(10^85_288, 10^85_289) spread: [10^78_729, 10^85_289] (40.03s)
1_400_001 E1(10^91_830, 10^91_829) spread: [10^85_288, 10^91_829] (46.40s)
1_500_001 E1(10^98_394, 10^98_393) spread: [10^91_829, 10^98_394] (53.11s)
1_600_001 E1(10^104_961, 10^104_959) spread: [10^98_393, 10^104_961] (60.18s)
1_700_001 E1(10^111_523, 10^111_523) spread: [10^104_958, 10^111_523] (67.75s)
1_800_001 E1(10^118_088, 10^118_088) spread: [10^111_523, 10^118_088] (75.77s)
1_900_001 E1(10^124_631, 10^124_630) spread: [10^118_088, 10^124_631] (84.39s)
2_000_001 E1(10^131_185, 10^131_185) spread: [10^124_630, 10^131_185] (93.41s)
...
3_000_001 E1(10^196_733, 10^196_733) spread: [10^190_163, 10^196_733] (217.87s)

Here spread: [X, Y] means that the spread values (since last print) had min X, max Y
So notice that the spread is basically uniformly increasing. In fact these [X, Y] intervals hardly even overlap!
That makes me think there's something about this that makes small spread impossible (and thus halt impossible)
Or that it's like Bigfoot and it ... could go back to zero, but the chances are infinitesimal!
</pre>

savask — 26 Jun 2024 at 1:02 AM
<pre>
Maybe we can simplify a little bit more. Set (a, c) = E(a, 0, c+1) then the rules are
(a, c) -> (a-c-1, 4c+5) if a > c
(a, c) -> (2a+2, c-a-1) if a < c
(a, c) -> Halt if a = c

I like that this way they are more symmetrical with a-c-1 vs c-a-1
</pre>

Shawn Ligocki — 26 Jun 2024 at 2:33 AM
<pre>
FWIW, there is a value x ~= 1.76 such that as c -> inf: (xc, c) -> (xyc, yc) via path "rll" (right->0 [ie a > c], left->0 [ie a < c], left->0). Which would repeat forever if it were exact, but it is an unstable cycle so any slight deviation and it gets further and further away, so that doesn't seem like a reasonable proof direction :/
</pre>dyuan01 — 26 Jun 2024 at 2:32 PM
If we let A(a, c) = (a-1, c-1), we can get these rules:
```
A(a, c) -> A(a-c, 4c+2) if a > c
A(a, c) -> A(2a+1, c-a) if a < c
A(a, c) -> Halt if a = c
```
And we start with (1, 2)

I'm not sure if it even helps, but at least the rules look slightly more "human-manageable"

== Analysis by Bard ==
Under a change of coordinates, the BMO1 rules approach a 1D line in the limit as the number of steps tends to infinity. Analysing the dynamics of points on that 1D line, it is possible to prove any given point on the line either halting or looping. Unfortunately, since at finite time, the point only gets arbitrarily close to the limiting line and never reaches it, it is not clear (to me at least) how to make use of this fact to solve BMO1. See the paper at [https://wiki.bbchallenge.org/w/images/9/94/BMO1-Bard.pdf BMO1 - Bard.pdf].

== Review 2026-Apr-19 by Opus 4.7 ==
<pre>
- backward (m,b) algebra: correct. Location 1 closed form and m>b invariant verified. Location 2's
Racheline suffix bound m+b > 43/21 is a genuine lemma but relies on an empirical claim about which suffixes
can appear. Location 3 (fractal near m≈1.76) is the real unresolved obstacle.
- Bard's PDF: homogenisation and 1D limit correct; z_n→0 asserted without proof (short argument sketched in
critique); density argument fine modulo a boundary point where f'=1; odd-denominator lemma elegant and
correct; same-trajectory lemma covers branch matching but glosses the halt case (fixable via nested
intervals).
- Bottom line: neither work proves BMO1. The wiki localises the difficulty to a fractal; Bard reduces it to
irrationality of α≈0.3621250257705563 — dual views of the same single-bit obstruction. Progress likely
needs an ergodic/entropy argument on the 1D map, not more enumeration.
</pre>

== References ==
[[Category:BB(6)]]
[[Category:Potential Cryptids]]

1RB1RE 1LC0RA 0RD1LB ---1RC 1LF1RE 0LB0LE

2026-07-19T01:21:30Z

AlephSquirrel: /* Relation to Other Math Problems */ Add zero-in-the-corner problem

{{machine|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}{{unsolved|Does this TM run forever?}}
{{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}, called '''[[Beaver Math Olympiad|BMO]] #1''', is a [[holdout]] [[BB(6)]] TM discovered by @-d on 25 Jun 2024 which is modeled by the [[Piecewise Affine Function]]:

<pre>
A(a, b) -> A(a-b, 4b+2) if a > b
A(a, b) -> A(2a+1, b-a) if a Halt if a = b

Start A(1, 2)
</pre>

for <code>A(a, b) = 0^inf 10^{a-1} 0 1^b E> 0^inf</code>. The configuration is always valid because <math>a \ge 1</math> is always maintained. Forward simulations of this model by @-d and Andrew Ducharme do not halt after 100,000,000 iterations of the map <code>A(a,b)</code>. It is the inspiration for the [[Beaver Math Olympiad]].

The rules and the derivation of the function condition were proved in Lean<ref>https://github.com/rwst/bbchallenge/tree/main/1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE/machine.lean</ref>.

== Relation to Other Math Problems ==
This TM is a possible [[Cryptid]] since it seems hard to predict whether we could ever end up in <code>A(n, n)</code>. However, it is not (yet) classified as a Cryptid because there are no arguments for why this TM is hard (e.g., by comparing it to an open/unsolved/hard mathematical problem).

The map <code>A(., .)</code> is related to the study of discontinuous [https://en.wikipedia.org/wiki/Dynamical_system dynamical systems]. When +2 and +1 are ignored, the value of <math>\ln(a/b)</math> follows this chaotic map:

<math display="block">F(x) = \begin{cases}
\ln\left(\frac{e^x-1}{4}\right) & \text{if }x > 0 \\
\ln\left(\frac{2}{e^{-x}-1}\right) & \text{if }x < 0
\end{cases}</math>

Another potential BB(6) cryptid {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}} similarly iterates upon a tuple (x,y) with one function if x < y, another function if x > y, and halts if x = y.

This Turing Machine models a [[Piecewise Affine Function]], a class of iterated functions that are known to be [[Turing complete]] in general (similar to [[Generalized Collatz Problems]]).

=== Zero-in-the-corner problem ===
This TM is equivalent to a specific instance of the "zero-in-the-corner" problem: it halts if and only if there is a finite product of the 3x3 matrices A' and B' with a 0 in the upper-left corner, where

<math>A'=\begin{pmatrix} 11 & 4 & 2 \\ -12 & -4 & -2 \\ -10 & -4 & -1 \end{pmatrix}, B'=\begin{pmatrix} -2 & -2 & -1 \\ 5 & 4 & 2 \\ 3 & 2 & 2 \end{pmatrix}</math>

See [https://wiki.bbchallenge.org/wiki/File:BMO1_Matrix_Proof.pdf%7CBMO1_Matrix_Proof.pdf BMO1 Matrix Proof].

== A Backward Reasoning Approach ==
An alternative approach is to work backwards and study the points which A(a,b) maps to the line a = b. For example, the points (2,7), (3,25), (4,71), and (5,181) all eventually map to a = b. (2,7) is immediately sent to a = b because, under the a A(2, 7) = (4 + 1, 7 - 2) = (5,5)</math>(5,181) requires more steps:

<math display="block">(5,181) \rightarrow (11, 176) \rightarrow (23, 165) \rightarrow (47, 142) \rightarrow (95, 95)</math>How are these points found? It's faster not to consider individual points, but as Racheline identified, the set of lines which are mapped to a = b. Introducing an index <math>n</math>, we can rewrite A(a,b) as<math display="block">(x_{n+1}, y_{n+1}) = \begin{cases} (x_n - y_n, 4y_n + 2), & \text{if } x_n \geq y_n \\ (2x_n + 1, y_n - x_n), & \text{if } x_n < y_n \end{cases}</math> If <math>x_{n+1} = y_{n+1}</math>{{machine|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE}}, then the lines with slopes <math>y_{n+1} = m x_{n+1} + b</math> map to that line. The two possible slopes are, for <math>x_n > y_n</math>and <math>x_n < y_n</math> respectively,

<math>4y_n + 2 = m (x_n - y_n) + b \iff y_n = \frac{m}{m + 4} x_n + \frac{b - 2}{m + 4}

</math> and<math>y_n - x_n = m (2 x_n + 1) + b \iff y_n = (2m + 1) x_n + (b + m).</math>

Indexing m and b in (slope, y-intercept) space gives

<math>(m_{k-1}, b_{k-1}) = \begin{cases}\left( \frac{m_k}{m_k + 4}, \frac{b_k - 2}{m_k + 4} \right), &x_{k-1} > y_{k-1} \\ (2m_k + 1, b_k + m_k), & x_{k-1} < y_{k-1} \end{cases}</math>.

Iteratively applying this (m,b) map finds an infinite set of points which A sends to a = b. The starting point is said line, with (m, b) = (1,0). Then the two lines of points which map to points on the line (m,b) = (1,0) under a single application A have slopes and y-intercepts of <math>\left(\frac{1}{5}, -\frac{2}{5} \right) = \left(\frac{1}{1 + 4}, \frac{0-2}{1+4} \right) </math> and (3,1) = (2 + 1, 0 + 1). The four lines of points which map to (1,0) under two applications of A have slopes and y-intercepts <math>\left(\frac{1}{21}, -\frac{4}{7} \right), \left(\frac{7}{5}, -\frac{1}{5} \right), \left(\frac{3}{7}, -\frac{1}{7} \right)</math> and (7,4).
[[File:Slope intercept space after 5 iterations.png|thumb|Each point in the plotted (slope, intercept) space represents a line of points in (x,y) space that are eventually mapped to y = x by iterated application of the operation A. These points require five or fewer iterations to do so.]]
[[File:(m,b) space after 9 iterations with halting condition line.png|thumb|Each plotted point in (slope, intercept) space represents a line of points in (x,y) space which is mapped to y = x by nine or fewer iterated applications of A. If any point is on the black line, the TM in question halts.]]
To apply this to the problem at hand, we want to know if any of these generated lines contain the point (1,2), our TM-derived initial condition. The set of all lines (in position space, or (x,y) space) containing (1,2) are described by the line in (m,b) space 2 = m + b. If any of the generated points in (m,b) space sit on 2 = m + b, then the point (x,y) = (1,2) is eventually mapped by A to a point where x = y. In the second image, of (m,b) points after nine iterations, we see there are three possible locations for this to occur.
[[File:MbSpace iterations10 smallmb wline.png|center|thumb|575x575px|Each plotted point in (slope, intercept) space represents a line of points in (x,y) space which is mapped to y = x by ten or fewer iterated applications of A, with m > 2 and b > 0. If any point is on the black line, the TM in question halts. There are three possible locations. Two do not hit the line (in finite time). The third's status is unknown.]]

=== Location 1: Approaching (m = 1, b= 1) from below ===
There's two ways to see how (1,1) is not actually an intersection point. First, from Racheline, the elementary one: if m > b, m will always be greater than b, so a point where m = b is impossible.

Second, from Andrew, if one wants to generate a point near m = 1, you should create the largest possible value M to swamp out the additive +4 in the denominator of M/(M+4). M can be maximized with n iterations of the (m,b) map by only using the x < y operation. Then apply the x > y operation once for a near-unitary slope. The pair <math>(m_n, b_n)</math> formed by applying the x < y operation n times to (1,0) is <math>(2^{n+1}-1, 2^{n+1} -n-2)</math>. Apply the x > y operation to get

<math>\left( \frac{2^{n+1} - 1}{2^{n+1} + 3}, \frac{2^{n+1} -n-4}{2^{n+1}+3} \right)</math>.

Taking the limit as n goes to infinity, we get (1,1), so this TM does not reach the line 2 = m + b here in finite time.

=== Location 2: Approaching (m = 13/7, b = 4/21) from above ===
The rightmost possible intersection is the least likely: its approach towards 2 = m + b slows considerably with increasing iterations (because its limit will end up being to above this line). Empirically examining these points, they appear to be near (1.85, 0.19). After 6 through 9 iterations, the closest of the generated (m,b) points to (1.85, 0.19) are (285/151, 37/151), (1117/599, 123/599), (4445/2391, 155/797), and (17757/9559, 1831/9559). Such points are formed by n applications of the (m,b) map when x > y, then two applications of the (m,b) map when x < y, then a single additional application of the x > y and x < y (m,b) maps, in that order. A more concise notation would be <math>(>^n, <^2, >, <)</math>.

A closed form equation in n for <math>(>^n, <^2, >, <)</math> starting from (1,0) is <math>\left( \frac{13 * 4^{n+1} + 23}{7* 4^{n+1} + 5}, \frac{4^{n+2} + 6n + 65}{21 * 4^{n+1} + 15} \right)</math>. Its limit as <math>n \rightarrow \infty</math> is <math>\left( \frac{13}{7}, \frac{4}{21} \right)</math>, which is safely above 2 = m + b. This strand of points will never cause a halting condition.

Racheline showed the same by applying the bounds m > 0 and <math>b > - \frac{2}{3}</math> on the sequence <math>(<^2, >, <)</math>:

<math>\begin{align} m_0 > 0, b_0 > - \frac{2}{3} &\implies m_1 > 1, b_1 > -\frac{2}{3} \\
&\implies m_2 > 3, b_2 > \frac{1}{3} \\
&\implies m_3 > \frac{3}{7}, b_3 > -\frac{5}{21} \\
&\implies m_4 > \frac{13}{7}, b_4 > \frac{4}{21}
\end{align}</math>

Since the combination of operations is empirically determined, this isn't strictly a proof, but the moderate distance of these points from 2 = m + b means the burden of proof isn't that high.

=== Location 3: Jumping above and below b = 2 - m around m = 1.76...infinitely? ===
Notes from my (Andrew) analysis, from when I tried to repeat looking at the points closest to the not-quite-intersection of the sparse set and line b = 2 - m. I went 25 iterations of the slope map before realizing it was likely a fractal and zooming in would give me more of the same:
Slopes of points (m,b) closest to the line m = 2 - b from above and below

13/7 for n = 5 is above and to the right, 119/69 for n = 6 is below and to the left, 223/125 for n = 7 is above and to the right, 669/401 for n = 8 is below left.
Things start to get more complicated at n = 9, as the doubling of dots becomes a little overwhelming.
So many dots at n = 13 you have to zoom in
n = 9 above: 223/125, n = 9 below: 1145/651
n = 10 above: 2037/1151, n = 10 below: 1145/651 (still)
n = 11 above: 6617/3755, n = 11 below: 1145/651 (still)
n = 12 above: 6617/3755 (still), n = 12 below: 24937/14171
n = 13 above: 6617/3755 (still), n = 13 below: 38171/21681
n = 14 above: 6617/3755 (still), n = 14 below: 64639/36701
n = 15 above: 117575/66741, n = 15 below: 64639/36701 (still)
n = 16 above: 117575/66741 (still), n = 16 below: 376131/213545
n = 17 above: 611281/347027, n = 17 below: 376131/213545 (still).
b for the new point here is 2 / 347027 from being on the line!!
At n = 17, have we crossed the Rubicon? This super close point is just above the line, so is anything new now above it?
No! yowza.
n = 18 above: 611281/347027 (still), n = 18 below: 611281/347027.
n = 19 above: 611281/347027 (still), n = 19 below: 2115805/1201207
n = 20 above: 611281/347027 (still), n = 20 below: 3338367/1895261
n = 21 above:611281/347027 (still) , n = 21 below: 10673739/6059585
There's a new point next to our hero which is just to the right and just above. Above trend hitting limit point?
NO!!
n = 22 above: 208917121/118603171, n = 22 below: 20454235/11612017 I might be seeing a new trend line forming
n = 23 above: 834868865/473958819, n = 23 below: 40015227/22716881
n = 24 above: 3338675841/1895381411, n = 24 below: 40015227/22716881 (still)
n = 25 above: 79137211/44926609, n = 25 below: 239198119/135794133

I think I'm zooming in on a fractal structure and will never see the end of this.
[[File:Screenshot of (m,b) set as we zoom in on possible intersection.png|center|thumb|636x636px|To demonstrate the fractal, the generated (m,b) set after n iterations for n = 9, n = 15, n = 20, and n = 25. Note the change in scale on the horizontal and vertical axes. I'm roughly specifying another decimal place in the axes bounds as I look at smaller and smaller region. Largely a copy of post @aducharme [https://discord.com/channels/960643023006490684/1026577255754903572/1267352007811797012 July 27th, 2024 10:24 PM PT]]]
Unless we actually hit the halting condition, we can generate an infinite number of blue points arbitrarily close to the yellow line from both above and below.

It does appear that points within roughly the range 1.724 < m < 1.8556 are generated from finding all possible combinations of operations > and < after n applications, then applying <math>(<,<,<,>,<,>,<) = (<^4, (>,<)^2) = (<^4, >,<,>,<)</math>. This is equivalent to <math display="block">(m_f,b_f) = \left( \frac{104m_n + 119}{56 m_n + 69}, \frac{23m_n + b_n + 12}{56m_n + 69} \right).</math>

== Study of Simplified Model ==
@savask [https://discord.com/channels/960643023006490684/1026577255754903572/1255778174986485780 06/26/2024 11:54 PM]
Maybe we could tackle a simplified version of this problem? For example, let's remove the constant terms:

(a, b) -> (a-b, 4*b) if a > b
(a, b) -> (2*a, b-a) if b > a
(a, b) -> Halt if a = b

And let's start from config (3,17), since it appears in the run of the original machine.
The average increase in <math>\ln a</math> is

<math>\frac{-\frac{\pi^2}{12} + 3 \frac{(\ln 2)^2 }{2} + \text{Li}_2(1/4)}{\ln 3} \approx 0.15097694</math>

when modeled from the PDF

<math>f(r) = \frac{2}{\ln 3 (r+1)(r+3)}</math>

in <math>r = b/a</math>, as found by [https://discord.com/channels/960643023006490684/1026577255754903572/1256315391995809842 @LegionMammal978] and Math.SE user "Sil".<ref>https://math.stackexchange.com/questions/4939082/solving-the-functional-equation-fx-frac4x42f-frac-xx42f2x1/4939136#4939136</ref>

Note that the simplified iteration trivially cannot halt as written: after 2 steps, it reaches <math>(12, 8)</math> and becomes trapped within the families <math>(a, b) \equiv (0, 4)</math> and <math>(a, b) \equiv (4, 0) \pmod{8}</math>.

== Development of Model from TM Tape ==
@-d [https://discord.com/channels/960643023006490684/1026577255754903572/1255047256688824390 25 Jun 2024 2:29 AM ET]:
<pre>
Let f(a,b) represent (10)^a D> 1^b. By inspection, the machine visits f(0,3) f(2,2) f(1,7) f(4,5) f(0,19) f(2,18) f(6,15) f(14,8).

I got these rules for f(a,b) and verified them up to 0<=a<=100 and 1<=b<=100.
f(a,b) -> f(a-b+1,4b-1) if b < a+2
f(a,a+2) -> halt
f(a,b) -> f(2a+2,b-a-1) if b > a+2

I ran these rules from f(0,3) and gave up after reaching a,b > 2^1000000. It looks like halting becomes less and less likely. Is there a way to show this runs forever (or miraculously halts)?
</pre>

@Shawn Ligocki — [https://discord.com/channels/960643023006490684/1026577255754903572/1255371132694167591 25 Jun 2024 at 11:56 PM ET]:
<pre>
I can confirm roughly the same rules (I chose a slightly different standard config):
1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE

E(a, b, c) = 0^inf 10^a 0 10^b 1^c E> 0^inf

Base Rules:
E(a+1, b, c+2) -> E(a, b+2, c+1)
E(a+1, b, 1) -> E(a, 0, 2b+6)
E(0, b, c+2) -> E(b+2, 0, c+1)
E(0, b, 1) -> Halt(b+4)

High-level Rules:
E(a, 0, c+1) --> E(a-c-1, 0, 4c+6) if a > c
E(a, 0, c+1) --> E(2a+2, 0, c-a) if a < c
E(a, 0, c+1) --> Halt(2c+4) if a = c

Connecting to your notation @-d : f(a, b+2) -> E(a, 0, b+1)
</pre>

@Shawn Ligocki — 26 Jun 2024 at 12:25 AM
<pre>
Hm, this is interesting. I decided to track "spread" akin to what @savask and I have been looking at for the similar 3x3 TM we're looking at in ⁠bbxy . Here I define spread = abs(a - c) in config E1(a, c) = E(a, 0, c+1). Here's the results I have so far:
1 E1(2, 0) spread: [2, 2] (0.06s)
100_001 E1(10^6_557, 10^6_555) spread: [1, 10^6_557] (0.44s)
200_001 E1(10^13_124, 10^13_125) spread: [10^6_557, 10^13_125] (1.27s)
300_001 E1(10^19_670, 10^19_669) spread: [10^13_123, 10^19_670] (2.52s)
400_001 E1(10^26_235, 10^26_237) spread: [10^19_668, 10^26_237] (4.23s)
500_001 E1(10^32_799, 10^32_799) spread: [10^26_235, 10^32_799] (6.39s)
600_001 E1(10^39_350, 10^39_352) spread: [10^32_799, 10^39_352] (8.98s)
700_001 E1(10^45_930, 10^45_930) spread: [10^39_350, 10^45_930] (12.06s)
800_001 E1(10^52_486, 10^52_486) spread: [10^45_929, 10^52_486] (15.54s)
900_001 E1(10^59_046, 10^59_047) spread: [10^52_485, 10^59_047] (19.57s)
1_000_001 E1(10^65_613, 10^65_612) spread: [10^59_045, 10^65_613] (24.05s)
1_100_001 E1(10^72_154, 10^72_153) spread: [10^65_609, 10^72_154] (28.92s)
1_200_001 E1(10^78_728, 10^78_729) spread: [10^72_153, 10^78_729] (34.21s)
1_300_001 E1(10^85_288, 10^85_289) spread: [10^78_729, 10^85_289] (40.03s)
1_400_001 E1(10^91_830, 10^91_829) spread: [10^85_288, 10^91_829] (46.40s)
1_500_001 E1(10^98_394, 10^98_393) spread: [10^91_829, 10^98_394] (53.11s)
1_600_001 E1(10^104_961, 10^104_959) spread: [10^98_393, 10^104_961] (60.18s)
1_700_001 E1(10^111_523, 10^111_523) spread: [10^104_958, 10^111_523] (67.75s)
1_800_001 E1(10^118_088, 10^118_088) spread: [10^111_523, 10^118_088] (75.77s)
1_900_001 E1(10^124_631, 10^124_630) spread: [10^118_088, 10^124_631] (84.39s)
2_000_001 E1(10^131_185, 10^131_185) spread: [10^124_630, 10^131_185] (93.41s)
...
3_000_001 E1(10^196_733, 10^196_733) spread: [10^190_163, 10^196_733] (217.87s)

Here spread: [X, Y] means that the spread values (since last print) had min X, max Y
So notice that the spread is basically uniformly increasing. In fact these [X, Y] intervals hardly even overlap!
That makes me think there's something about this that makes small spread impossible (and thus halt impossible)
Or that it's like Bigfoot and it ... could go back to zero, but the chances are infinitesimal!
</pre>

savask — 26 Jun 2024 at 1:02 AM
<pre>
Maybe we can simplify a little bit more. Set (a, c) = E(a, 0, c+1) then the rules are
(a, c) -> (a-c-1, 4c+5) if a > c
(a, c) -> (2a+2, c-a-1) if a < c
(a, c) -> Halt if a = c

I like that this way they are more symmetrical with a-c-1 vs c-a-1
</pre>

Shawn Ligocki — 26 Jun 2024 at 2:33 AM
<pre>
FWIW, there is a value x ~= 1.76 such that as c -> inf: (xc, c) -> (xyc, yc) via path "rll" (right->0 [ie a > c], left->0 [ie a < c], left->0). Which would repeat forever if it were exact, but it is an unstable cycle so any slight deviation and it gets further and further away, so that doesn't seem like a reasonable proof direction :/
</pre>dyuan01 — 26 Jun 2024 at 2:32 PM
If we let A(a, c) = (a-1, c-1), we can get these rules:
```
A(a, c) -> A(a-c, 4c+2) if a > c
A(a, c) -> A(2a+1, c-a) if a < c
A(a, c) -> Halt if a = c
```
And we start with (1, 2)

I'm not sure if it even helps, but at least the rules look slightly more "human-manageable"

== Analysis by Bard ==
Under a change of coordinates, the BMO1 rules approach a 1D line in the limit as the number of steps tends to infinity. Analysing the dynamics of points on that 1D line, it is possible to prove any given point on the line either halting or looping. Unfortunately, since at finite time, the point only gets arbitrarily close to the limiting line and never reaches it, it is not clear (to me at least) how to make use of this fact to solve BMO1. See the paper at [https://wiki.bbchallenge.org/w/images/9/94/BMO1-Bard.pdf BMO1 - Bard.pdf].

== Review 2026-Apr-19 by Opus 4.7 ==
<pre>
- backward (m,b) algebra: correct. Location 1 closed form and m>b invariant verified. Location 2's
Racheline suffix bound m+b > 43/21 is a genuine lemma but relies on an empirical claim about which suffixes
can appear. Location 3 (fractal near m≈1.76) is the real unresolved obstacle.
- Bard's PDF: homogenisation and 1D limit correct; z_n→0 asserted without proof (short argument sketched in
critique); density argument fine modulo a boundary point where f'=1; odd-denominator lemma elegant and
correct; same-trajectory lemma covers branch matching but glosses the halt case (fixable via nested
intervals).
- Bottom line: neither work proves BMO1. The wiki localises the difficulty to a fractal; Bard reduces it to
irrationality of α≈0.3621250257705563 — dual views of the same single-bit obstruction. Progress likely
needs an ergodic/entropy argument on the 1D map, not more enumeration.
</pre>

== References ==
[[Category:BB(6)]]
[[Category:Potential Cryptids]]

File:BMO1 Matrix Proof.pdf

2026-07-19T01:16:09Z

AlephSquirrel:

Proof of equivalence between BMO1 and a specific instance of the zero-in-the-corner problem.