Pebble Automaton: Difference between revisions

Latest revision as of 16:35, 22 August 2026

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

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.

It is not proven that it is Turing-Complete but it probably is since some automata can 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

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

TODO

peBBle(9)

The champion performs a Collatz-like function.

Analysis:

A(n) := 60^n3
B(n) := 60^n21

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

Sources

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

External resources

Uiua simulator

@@ 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]]. 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.
-* L(n) >= 0
+It is not proven that it is Turing-Complete but it probably is since some automata can compute Collatz-like functions.
-* 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, R(n) to its right neighbor and S(n) stay.
-Informally, when a cell has n pebbles, it pushes L(n) to its left neighbor, and R(n) to its right neighbor.
+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.
+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, we can extend the notation with letters, like with hexadecimal colors.
 {| class="wikitable"
 |+
 !n
-!Value
+!peBBle(n)
 !Champion
 |-
 |1
 |0
-|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
+|<code>00</code>
 |-
 |2
 |1
-|<code><nowiki>1 --> 0 | 1 | 0</nowiki></code>
+|<code>00_01</code>
-<code>2 --> 0 | 1 | 1</code>
 |-
 |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
+|≥ 63577
+|<code>00_02_01_40_14_12_00_52_81</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) ===
+TODO
+=== peBBle(9) ===
+The champion performs a [[Collatz-like]] function.
+Analysis:
+<syntaxhighlight line="1">
+A(n) := 60^n3
+B(n) := 60^n21
+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>
 == Sources ==
 Discord thread: https://discord.com/channels/960643023006490684/1535695107448381591
+== External resources ==
+[https://gist.github.com/AlephSquirrel/9ada4b14b675d18fe8755b200b20509d Uiua simulator]
+[[Category:Functions]]
+[[Category:Stubs]]

Pebble Automaton: Difference between revisions

Latest revision as of 16:35, 22 August 2026

Contents

Definition

Busy Beaver function

Analysis

peBBle(5)

peBBle(6)

peBBle(7)

peBBle(8)

peBBle(9)

Sources

External resources

Navigation menu

Pebble Automaton: Difference between revisions

Latest revision as of 16:35, 22 August 2026

Definition

Busy Beaver function

Analysis

peBBle(5)

peBBle(6)

peBBle(7)

peBBle(8)

peBBle(9)

Sources

External resources

Navigation menu

Search