Pebble Automaton
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.1peBBle(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.1peBBle(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.1peBBle(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.1peBBle(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)...