Pebble Automaton
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
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, we can extend the notation with letters, like with hexadecimal colors.
| 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 | ≥ 63577 | 00_02_01_40_14_12_00_52_81
|
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
No cryptids have been found through exhaustive search, but there have been cryptids created by hand.
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+1 or u=v 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)...