Pebble Automaton

From BusyBeaverWiki
Revision as of 04:53, 13 November 2026 by Sligocki (talk | contribs) (→Cryptids: Add Golems and Oddball Golem analysis)
Jump to navigation Jump to search

A pebble automaton is a type of cellular automaton introduced by AlephSquirrel, based on a Codeforces problem, also called Pebble Automaton.[1] Each cell contains a non-negative number of pebbles, and the number of pebbles in the cell determines how many pebbles to push to each neighbor. Though in the original problem, the behavior of a cell also depended on the cell's location, the cellular automaton removes this dependence. Investigation so far has primarily focused on 1-dimensional pebble automata, but multi-dimensional pebble automata could be considered.

Pebble automata have been informally shown to be Turing-complete via a reduction to 2-register Register machines.[2]

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

We say a pebble automaton has stabilized if no pebbles are moving; for any k in the configuration, L(k) = R(k) = 0.

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): n --> L(n) | S(n) | R(n)

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

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

If there are over 10 pebbles, lowercase letters are used for numbers greater than 9 (a=10, b=11, etc.)

n peBBle(n) Champion
1 = 0 00
2 = 1 00_01
3 = 3 00_01_20
4 = 6 00_01_20_03
5 = 11 00_11_03_21_04
6 = 17 00_11_03_21_40_15
7 = 28 00_11_03_21_10_33_61
8 = 63 00_11_03_21_50_30_24_70
9 = 63,577 00_02_01_40_14_12_00_52_81
10 = 5,778 00_02_01_40_14_12_00_17_63_18
11 ≥ 810,626,821 00_00_30_40_12_51_07_20_41_12_19

Analysis

peBBle(5)

.5.....
.14....
.311...
..41...
.212...
1.3.1..
1..31..
1...4..
1..211.
1.1.21.
1.11.2.
1.111.1

peBBle(6)

...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

peBBle(7)

..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

peBBle(8)

.....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

peBBle(9)

The champion performs a Collatz-like function.

Analysis:

A(n) := 6 0^n 3
B(n) := 6 0^n 21

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

Cryptids

The Golems

There are 22 remaining peBBle(11) holdouts which can be reduced to 10 equivalency classes and 7 distinct paths:[1]

#1: 00_00_03_01_14_60_12_51_--_81_35 | path 1
#5: 00_00_03_01_14_60_13_51_80_--_16 | path 1
#9: 00_00_03_01_14_60_13_51_--_81_15 | path 1
#f: 00_00_03_01_14_60_13_71_17_--_18 | path 2
#g: 00_00_03_01_14_60_13_71_52_--_28 | path 3
#h: 00_00_03_01_14_60_13_71_71_--_28 | path 3
#i: 00_00_03_01_20_60_13_70_--_71_44 | path 4
#k: 00_00_03_01_20_60_13_71_80_--_54 | path 5
#l: 00_00_03_01_20_60_13_71_81_--_54 | path 6
#m: 00_00_03_31_11_60_21_16_54_--_19 | path 7 - oddball

These are the golems. These have intricate rules, but the common case is somewhat well behaved (sort of like a two phase version of BMO1).

Oddball Golem

00_00_03_31_11_60_21_16_54_--_19, the "oddball" golem follows the rules:[2]

  #### State A(a, b, c, d) := 7 .ᵃ⁻¹1 .ᵇ⁻¹1 .ᶜ⁻¹1 .ᵈ⁻¹1
       (Invariants: a ≡ 2 (mod 3),  b ≥ 0,  c ≥ 1,  d ≥ 1)
    A(a, 0, 1, 1) ⟶ D(a + 1,  1,  3,  2)
    A(a, 0, 1, 2) ⟶ Inf
    A(a, 0, 1, d) ⟶ C(a + 1,  3,  2,  d - 3)         if d ≥ 3
    A(a, 0, 2, d) ⟶ Inf
    A(a, 0, c, d) ⟶ B(a + 3,  2,  c - 3,  d)         if c ≥ 3
    A(a, b, c, d) ⟶ A(a + 3,  b - 1,  c,  d)         if b ≥ 1

  #### State B(a, b, c, d) := 1 .ᵃ⁻¹7 .ᵇ⁻¹1 .ᶜ⁻¹1 .ᵈ⁻¹1
       (Invariants: a ≥ 0,  b ≡ 2 (mod 3),  c ≥ 0,  d ≥ 1,  a + c ≥ 1)
    B(0, b, c, d) ⟶ B(1,  b,  c,  d)             (here c ≥ 1, or b ≥ 5 if c = 0)
    B(1, 2, 0, d) ⟶ Inf
    B(1, b, 0, d) ⟶ C(6b + d - 10,  3,  2,  0)       if b ≥ 5
    B(1, b, c, d) ⟶ A(2,  b - 2,  c,  d)             if c ≥ 1
    B(a, b, 0, 1) ⟶ D(a - 2,  b + 1,  3,  2)         if a ≥ 2
    B(a, b, 0, 2) ⟶ Inf                              if a ≥ 2
    B(a, b, 0, d) ⟶ C(a - 2,  b + 3,  2,  d - 3)     if a ≥ 2, d ≥ 3
    B(a, b, c, d) ⟶ B(a - 2,  b + 3,  c - 1,  d)     if a ≥ 2, c ≥ 1

  #### State C(a, b, c, d) := 1 .ᵃ⁻¹1 .ᵇ⁻¹7 .ᶜ⁻¹1 .ᵈ⁻¹1
       (Invariants: a ≥ 0,  b ≥ 0,  c ≡ 2 (mod 3),  d ≥ 0,  a + b ≥ 1)
    C(a, 0, c, d) ⟶ C(a - 1,  1,  c,  d)         (here a ≥ 1)
    C(0, 1, c, d) ⟶ Inf
    C(a, 1, c, 0) ⟶ Inf                              if a ≥ 1
    C(a, 1, c, d) ⟶ B(a + 1,  2,  c - 2,  d)         if a ≥ 1, d ≥ 1
    C(a, 2, c, 0) ⟶ Inf
    C(0, 2, c, d) ⟶ Inf                              if d ≥ 1
    C(a, b, c, 0) ⟶ D(a,  b - 2,  c + 3,  2)         if b ≥ 3
    C(a, b, c, d) ⟶ C(a,  b - 2,  c + 3,  d - 1)     if b ≥ 2, d ≥ 1, (a, b) ≠ (0, 2)

  #### State D(a, b, c, d) := 1 .ᵃ⁻¹1 .ᵇ⁻¹1 .ᶜ⁻¹7 .ᵈ⁻¹1
       (Invariants: a ≥ 0,  b ≥ 1,  c ≥ 0,  d ≡ 2 (mod 3))
    D(0, 1, 0, d) ⟶ Halt                                 (the ONLY reachable halting transition!)
    D(a, b, 0, d) ⟶ D(a,  b - 1,  1,  d)             if (a, b) ≠ (0, 1)
    D(a, b, 1, d) ⟶ C(a,  b + 1,  2,  d - 2)
    D(a, b, c, d) ⟶ D(a,  b,  c - 2,  d + 3)         if c ≥ 2

Start: B(2, 2, 33, 5)

Here . represents 0 and if any variable is 0, that really means the two adjacent piles are combined, so D(0, 1, 2, 3) = 21.7..1 and B(0, 1, 2, 3) = 81.1..1 etc. These rules simplify in the "common case":[3]

00_00_03_31_11_60_21_16_54_--_19

Well-behaved zone:
  B(a, 2, c, d) with d≥3
  C(a, b, 2, d) with a≥2

if a ≤ 2c - 6:
  B(2k,   2, c, d)  ->  B(9k+5, 2, c-k-3, d)
  B(2k+1, 2, c, d)  ->  B(9k+5, 2, c-k-3, d)
if a ≥ 2c + 4:
  B(a, 2, c, d)  ->  C(a-2c-2, 3c+5, 2, d-3)  with a-2c-2 ≥ 2

if b ≥ 2d + 3:
  C(a, b, 2, 2k)    ->  C(a, b-4k-1, 2, 9k+6)
  C(a, b, 2, 2k+1)  ->  C(a, b-4k-4, 2, 9k+12)
if b ≤ 2d - 6:
  C(a, 2k,   2, d)  ->  B(a,   2, 3k, d-k)  with d-k ≥ 3
  C(a, 2k+1, 2, d)  ->  B(a+1, 2, 3k, d-k)  with d-k ≥ 3

Start: B(2, 2, 33, 5)

These rule continue to apply and it remains in the well-behaved zone as long as a is not too close to 2c (in B configs) or b too close to 2d (in C configs). If it leaves the well-behaved zone it has a chance to either halt or become provably infinite or to return to the well-behaved zone later. Empirically, it does not leave the well-behaved zone for 100k steps starting from B(2, 2, 33, 5). As it runs further, the variables grow exponentially and so the "chance" of hitting either of these narrow windows becomes more and more unlikely (similar to BMO1). Thus it appears that it probviously never leave the well-behaved zone again.

Hand-made Cryptids

A 12 pebble automaton has been created that is modeled by a Piecewise Affine Function, similar to BMO1:

00_00_00_40_10_00_00_08_41_11_00_a1

Let A(u,v) := 1 0^(u-2) a 0^(v-1) 1

A(u,v) -> A(4u-1, v-u) if u<v
A(u,v) -> A(u-v, 4v+1) if u>v+1
A(u,v) -> halt         if u=v or u=v+1

start: A(3,1)

An 86 pebble automaton has been produced by hand to display Hydra-like behavior:

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

It may be interpreted in the following way:

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)...

Other notable machines

Golems

The "golems" are a group of 22 holdouts in peBBle(11). They appear to be modeled by complex systems of equations, making them potential Cryptids. Discord user Sheep noted that they can be categorized into 7 unique "paths"[3], though the details may differ on how they behave if they encounter an improbable position.[4]

Golems text
Golem no. Machine Note
#1 00_00_03_01_14_60_13_71_17_--_18
#2 00_00_30_10_41_06_31_15_08_--_19
#3 00_00_03_31_11_60_21_16_54_--_19
#4 00_00_30_10_02_06_31_17_08_--_45
#5 00_00_30_10_02_06_31_17_18_--_45
#6 00_00_30_10_41_06_31_15_08_--_14
#7 00_00_30_10_02_06_31_07_--_17_1a
#8 00_00_30_10_41_06_21_15_--_18_1a
#9 00_00_30_10_41_06_31_15_--_18_1a
#10 00_00_03_01_14_60_13_51_80_--_19
#11 00_00_03_01_20_60_13_70_--_71_44
#12 00_00_03_01_14_60_12_51_--_81_44
#13 00_00_03_01_14_60_13_51_--_81_44
#14 00_00_03_01_14_60_13_51_--_81_15
#15 00_00_03_01_14_60_13_51_80_--_16
#16 00_00_03_01_14_60_12_51_--_81_35
#17 00_00_03_01_14_60_13_51_--_81_35
#18 00_00_03_01_14_60_13_51_--_81_22
#19 00_00_03_01_14_60_13_51_--_81_24
#20 00_00_30_10_41_06_31_15_08_--_11
#21 00_00_03_01_14_60_13_71_52_--_28
#22 00_00_03_01_14_60_13_71_71_--_28

Sources

External resources