Pebble Automaton: Difference between revisions

Latest revision as of 20:56, 4 November 2026

This article is a stub. You can help the BusyBeaverWiki by expanding it.

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

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

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

External resources

[1] ttps://codeforces.com/gym/106465/problem/B

[2] ttps://discord.com/channels/960643023006490684/1535695107448381591/1567607590970458274

[3] ttps://discord.com/channels/960643023006490684/1535695107448381591/1566012271719616573

[4] ttps://discord.com/channels/960643023006490684/1535695107448381591/1566013254764073081

[1]

[2]

[3]

[4]

Pebble Automaton: Difference between revisions

Latest revision as of 20:56, 4 November 2026

Contents

Definition

Busy Beaver function

Analysis

peBBle(5)

peBBle(6)

peBBle(7)

peBBle(8)

peBBle(9)

Cryptids

Other notable machines

Golems

Sources

External resources

Navigation menu

@@ Line 1: / Line 1: @@
-A pebble automaton is defined by two integer functions L(n) and R(n), defined over positive integers n, under the constraints:
+{{Stub}}
+A pebble automaton is a type of [[cellular automaton]] introduced by AlephSquirrel, based on a Codeforces problem, also called Pebble Automaton.<ref>https://codeforces.com/gym/106465/problem/B</ref> 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.
-* L(n) >= 0
+Pebble automata have been informally shown to be [[Turing-complete]] via a reduction to 2-register [[Register machine|Register machines]].<ref>https://discord.com/channels/960643023006490684/1535695107448381591/1567607590970458274</ref>
-* 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.
+== 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, 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)))
+* 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, and R(n) to its right neighbor.
+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 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.
+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): <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, lowercase letters are used for numbers greater than 9 (a=10, b=11, etc.)
 {| class="wikitable"
 |+
 !n
-!Value
+!peBBle(n)
 !Champion
 |-
 |1
-|0
+|= 0
-|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
+|<code>00</code>
 |-
 |2
-|1
+|= 1
-|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
+|<code>00_01</code>
-<code>2 --> 0 | 1 | 1</code>
 |-
 |3
-|3
+|= 3
-|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
+|<code>00_01_20</code>
-<code>2 --> 1 | 1 | 0</code>
+|-
-<code>3 --> 0 | 1 | 2</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
+|= 63,577
+|<code>00_02_01_40_14_12_00_52_81</code>
+|-
+|10
+|= 5,778
+|<code>00_02_01_40_14_12_00_17_63_18</code>
+|-
+|11
+|≥ 810,626,821
+|<code>00_00_30_40_12_51_07_20_41_12_19</code>
+|}
+== Analysis ==
+=== peBBle(5) ===
+<syntaxhighlight line="1">
+.5.....
+.14....
+.311...
+..41...
+.212...
+.3.1..
+..31..
+...4..
+..211.
+.1.21.
+.11.2.
+.111.1
+</syntaxhighlight>
+=== peBBle(6) ===
+<syntaxhighlight line="1">
+...6.....
+..1.5....
+..141....
+..312....
+...5.1...
+..41.1...
+.212.1...
+.3.11...
+..311...
+...41...
+..212...
+.1.3.1..
+.1..31..
+.1...4..
+.1..211.
+.1.1.21.
+.1.11.2.
+.1.111.1
+</syntaxhighlight>
+=== peBBle(7) ===
+<syntaxhighlight line="1">
+..7.......
+.6.1......
+.31......
+.3.4......
+..511.....
+.1411.....
+.3121.....
+..5.2.....
+.141.1....
+.312.1....
+..5.11....
+.14.11....
+.31111....
+..4111....
+.21211....
+.3.21....
+..4.2....
+.212.1...
+.3.11...
+..311...
+...41...
+..212...
+.1.3.1..
+.1..31..
+.1...4..
+.1..211.
+.1.1.21.
+.1.11.2.
+.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..........
+...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 lang="text">
+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)
+-(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 ==
+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]]:
+<pre>
+_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)
+</pre>
+An 86 pebble automaton has been produced by hand to display [[Hydra]]-like behavior:
+<pre>
+--> 0 | 1 | 0
+--> 0 | 0 | 2
+--> 0 | 0 | 3
+--> 0 | 0 | 5
+--> 0 | 6 | 0
+--> 0 | 1 | 6
+--> 0 | 2 | 6
+--> 9 | 0 | 0
+--> 12 | 0 | 0
+--> 0 | 14 | 0
+--> 6 | 9 | 0
+--> 17 | 0 | 0
+--> 0 | 24 | 0
+--> 0 | 2 | 23
+--> 0 | 1 | 25
+--> 24 | 3 | 0
+--> 26 | 2 | 0
+--> 27 | 2 | 0
+--> 27 | 3 | 0
+--> 0 | 32 | 0
+--> 0 | 33 | 0
+--> 0 | 2 | 33
+--> 0 | 3 | 35
+--> 0 | 0 | 39
+--> 0 | 0 | 40
+--> 1 | 40 | 0
+--> 0 | 39 | 6
+--> 0 | 0 | 78
+--> 0 | 79 | 0
+--> 24 | 15 | 45
+--> 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>
+== 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"<ref>https://discord.com/channels/960643023006490684/1535695107448381591/1566012271719616573</ref>, though the details may differ on how they behave if they encounter an improbable position.<ref>https://discord.com/channels/960643023006490684/1535695107448381591/1566013254764073081</ref>
+{| class="wikitable"
+|+ Golems text
+|-
+! Golem no. !! Machine !! Note
+|-
+| #1 || <code>00_00_03_01_14_60_13_71_17_--_18</code> ||
+|-
+| #2 || <code>00_00_30_10_41_06_31_15_08_--_19</code> ||
+|-
+| #3 || <code>00_00_03_31_11_60_21_16_54_--_19</code> ||
+|-
+| #4 || <code>00_00_30_10_02_06_31_17_08_--_45</code> ||
+|-
+| #5 || <code>00_00_30_10_02_06_31_17_18_--_45</code> ||
+|-
+| #6 || <code>00_00_30_10_41_06_31_15_08_--_14</code> ||
+|-
+| #7 || <code>00_00_30_10_02_06_31_07_--_17_1a</code> ||
+|-
+| #8 || <code>00_00_30_10_41_06_21_15_--_18_1a</code> ||
+|-
+| #9 || <code>00_00_30_10_41_06_31_15_--_18_1a</code> ||
+|-
+| #10 || <code>00_00_03_01_14_60_13_51_80_--_19</code> ||
+|-
+| #11 || <code>00_00_03_01_20_60_13_70_--_71_44</code> ||
+|-
+| #12 || <code>00_00_03_01_14_60_12_51_--_81_44</code> ||
+|-
+| #13 || <code>00_00_03_01_14_60_13_51_--_81_44</code> ||
+|-
+| #14 || <code>00_00_03_01_14_60_13_51_--_81_15</code> ||
+|-
+| #15 || <code>00_00_03_01_14_60_13_51_80_--_16</code> ||
+|-
+| #16 || <code>00_00_03_01_14_60_12_51_--_81_35</code> ||
+|-
+| #17 || <code>00_00_03_01_14_60_13_51_--_81_35</code> ||
+|-
+| #18 || <code>00_00_03_01_14_60_13_51_--_81_22</code> ||
+|-
+| #19 || <code>00_00_03_01_14_60_13_51_--_81_24</code> ||
+|-
+| #20 || <code>00_00_30_10_41_06_31_15_08_--_11</code> ||
+|-
+| #21 || <code>00_00_03_01_14_60_13_71_52_--_28</code> ||
+|-
+| #22 || <code>00_00_03_01_14_60_13_71_71_--_28</code> ||
 |}
 == Sources ==
-Discord thread: https://discord.com/channels/960643023006490684/1535695107448381591
+* Discord thread: https://discord.com/channels/960643023006490684/1535695107448381591
+<references />
+== 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: Difference between revisions

Latest revision as of 20:56, 4 November 2026

Definition

Busy Beaver function

Analysis

peBBle(5)

peBBle(6)

peBBle(7)

peBBle(8)

peBBle(9)

Cryptids

Other notable machines

Golems

Sources

External resources

Navigation menu

Search