Pebble Automaton

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

• L(n) ≥ 0
• R(n) ≥ 0
• L(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)) + L(p(x+1, t)) + (p(x,t) - L(p(x,t)) - R(p(x,t)))

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

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.

n	peBBln(n)	Champion
1	0	1 --> 0 | 1 | 0
2	1	1 --> 0 | 1 | 0 2 --> 0 | 1 | 1
3	3	1 --> 0 | 1 | 0 2 --> 1 | 1 | 0 3 --> 0 | 1 | 2
4	≥ 6	1 --> 0 | 1 | 0 2 --> 0 | 1 | 1 3 --> 2 | 1 | 0 4 --> 0 | 1 | 3
5	≥ 11	1 --> 0 | 1 | 0 2 --> 1 | 0 | 1 3 --> 0 | 0 | 3 4 --> 2 | 1 | 1 5 --> 0 | 1 | 4
6	≥ 17	1 --> 0 | 1 | 0 2 --> 1 | 0 | 1 3 --> 0 | 0 | 3 4 --> 2 | 1 | 1 5 --> 4 | 1 | 0 6 --> 1 | 0 | 5
7	≥ 28	1 --> 0 | 1 | 0 2 --> 1 | 0 | 1 3 --> 0 | 0 | 3 4 --> 2 | 1 | 1 5 --> 1 | 4 | 0 6 --> 3 | 0 | 3 7 --> 6 | 0 | 1

Sources

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