Элементарный клеточный автомат

В математике и теории вычислимости , элементарный клеточный автомат является одномерными клеточными автоматами , где есть два возможные состояние (меченые 0 и 1) и правила для определения состояния ячейки в следующем поколении зависит только от текущего состояния ячейка и два ее ближайших соседа. Существует элементарный клеточный автомат ( правило 110 , определенное ниже), который способен к универсальным вычислениям , и как таковой является одной из простейших возможных моделей вычислений.

Система нумерации [ править ]

Существует 8 = 2 ³ возможных конфигурации для ячейки и двух ее ближайших соседей. Правило, определяющее клеточный автомат, должно определять результирующее состояние для каждой из этих возможностей, поэтому существует 256 = 2 ^{2 3} возможных элементарных клеточных автомата. Стивен Вольфрам предложил схему, известную как код Вольфрама , для присвоения каждому правилу номера от 0 до 255, которая стала стандартной. Каждая возможная текущая конфигурация записывается в порядке 111, 110, ..., 001, 000, а результирующее состояние для каждой из этих конфигураций записывается в том же порядке и интерпретируется как двоичное представление целого числа. Это число принято за номер правила автомата. Например, 110 _d = 01101110₂ . Итак, правило 110 определяется правилом перехода:

Размышления и дополнения [ править ]

Хотя существует 256 возможных правил, многие из них тривиально эквивалентны друг другу вплоть до простого преобразования базовой геометрии. Первое такое преобразование - это отражение через вертикальную ось, и результат применения этого преобразования к заданному правилу называется зеркальным правилом . Эти правила будут демонстрировать такое же поведение вплоть до отражения через вертикальную ось, и поэтому эквивалентны в вычислительном смысле.

Например, если определение правила 110 отображается вертикальной линией, получается следующее правило (правило 124):

Правила, которые совпадают с их зеркальным правилом, называются амфихиральными . Из 256 элементарных клеточных автоматов 64 амфихиральны.

Второе такое преобразование - поменять местами 0 и 1 в определении. Результат применения этого преобразования к данному правилу называется дополнительным правилом . Например, если это преобразование применяется к правилу 110, мы получаем следующее правило

и после изменения порядка мы обнаруживаем, что это правило 137:

Есть 16 правил, которые совпадают с их дополнительными правилами.

Наконец, два предыдущих преобразования могут быть последовательно применены к правилу для получения зеркально отраженного дополнительного правила. Например, зеркальным дополнительным правилом правила 110 является правило 193. Существует 16 правил, которые аналогичны своим зеркальным дополнительным правилам.

Из 256 элементарных клеточных автоматов 88 неэквивалентны относительно этих преобразований.

Одиночные истории 1 [ править ]

Один из методов, используемых для изучения этих автоматов, состоит в том, чтобы проследить его историю с начальным состоянием всех нулей, кроме одной ячейки с 1. Когда номер правила четный (так что вход 000 не приводит к 1), он делает смысл интерпретировать состояние в каждый момент времени t как целое число, выраженное в двоичном формате, создавая последовательность целых чисел a ( t ). Во многих случаях эти последовательности имеют простые выражения в замкнутой форме или производящую функцию с простой формой. Следует отметить следующие правила:

Правило 28 [ править ]

Сгенерированная последовательность: 1, 3, 5, 11, 21, 43, 85, 171, ... (последовательность A001045 в OEIS ). Это последовательность чисел Якобсталя с производящей функцией

${\ displaystyle {\ frac {1 + 2x} {(1 + x) (1-2x)}}}$.

Имеет выражение в закрытой форме

${\ Displaystyle а (т) = {\ гидроразрыва {4 \ cdot 2 ^ {т} - (- 1) ^ {т}} {3}}}$

Правило 156 генерирует ту же последовательность.

Правило 50 [ править ]

Сгенерированная последовательность: 1, 5, 21, 85, 341, 1365, 5461, 21845, ... (последовательность A002450 в OEIS ). У этого есть производящая функция

${\displaystyle {\frac {1}{(1-x)(1-4x)}}}$.

Имеет выражение в закрытой форме

${\displaystyle a(t)={\frac {4\cdot 4^{t}-1}{3}}}$.

Обратите внимание, что правила 58, 114, 122, 178, 186, 242 и 250 генерируют одну и ту же последовательность.

Правило 54 [ править ]

Сгенерированная последовательность: 1, 7, 17, 119, 273, 1911, 4369, 30583, ... (последовательность A118108 в OEIS ). У этого есть производящая функция

${\displaystyle {\frac {1+7x}{(1-x^{2})(1-16x^{2})}}}$.

Имеет выражение в закрытой форме

${\displaystyle a(t)={\frac {22\cdot 4^{t}-6(-4)^{t}-4+3(-1)^{t}}{15}}}$.

Правило 60 [ править ]

Сгенерированная последовательность: 1, 3, 5, 15, 17, 51, 85, 255, ... (последовательность A001317 в OEIS ). Это может быть получено, если взять последовательные строки треугольника Паскаля по модулю 2 и интерпретировать их как целые числа в двоичной системе, которые могут быть графически представлены в виде треугольника Серпинского .

Правило 90 [ править ]

Сгенерированная последовательность: 1, 5, 17, 85, 257, 1285, 4369, 21845, ... (последовательность A038183 в OEIS ). Этого можно добиться, взяв последовательные строки треугольника Паскаля по модулю 2 и интерпретируя их как целые числа с основанием 4. Обратите внимание, что правила 18, 26, 82, 146, 154, 210 и 218 генерируют одну и ту же последовательность.

Правило 94 [ править ]

Сгенерированная последовательность: 1, 7, 27, 119, 427, 1879, 6827, 30039, ... (последовательность A118101 в OEIS ). Это можно выразить как

${\displaystyle a(t)={\begin{cases}1,&{\mbox{if }}t=0\\[5px]7,&{\mbox{if }}t=1\\[7px]{\dfrac {1+5\cdot 4^{n}}{3}},&{\mbox{if }}t{\mbox{ is even otherwise}}\\[7px]{\dfrac {10+11\cdot 4^{n}}{6}},&{\mbox{if }}t{\mbox{ is odd otherwise}}\end{cases}}}$.

У этого есть производящая функция

${\displaystyle {\frac {(1+2x)(1+5x-16x^{4})}{(1-x^{2})(1-16x^{2})}}}$.

Правило 102 [ править ]

Сгенерированная последовательность: 1, 6, 20, 120, 272, 1632, 5440, 32640, ... (последовательность A117998 в OEIS ). Это просто последовательность, сгенерированная правилом 60 (которое является его правилом зеркала), умноженная на последовательные степени двойки.

Правило 110 [ править ]

Сгенерированная последовательность: 1, 6, 28, 104, 496, 1568, 7360, 27520, 130304, 396800, ... (последовательность A117999 в OEIS ). Правило 110 обладает, возможно, удивительным свойством: оно полно по Тьюрингу и, следовательно, способно к универсальным вычислениям . ^[1]

Правило 150 [ править ]

Сгенерированная последовательность: 1, 7, 21, 107, 273, 1911, 5189, 28123, ... (последовательность A038184 в OEIS ). Это можно получить, взяв коэффициенты последовательных степеней (1+ x + x ² ) по модулю 2 и интерпретируя их как целые числа в двоичной системе.

Правило 158 [ править ]

Сгенерированная последовательность: 1, 7, 29, 115, 477, 1843, 7645, 29491, ... (последовательность A118171 в OEIS ). У этого есть производящая функция

${\displaystyle {\frac {1+7x+12x^{2}-4x^{3}}{(1-x^{2})(1-16x^{2})}}}$.

Правило 188 [ править ]

Сгенерированная последовательность: 1, 3, 5, 15, 29, 55, 93, 247, ... (последовательность A118173 в OEIS ). У этого есть производящая функция

${\displaystyle {\frac {1+3x+4x^{2}+12x^{3}+8x^{4}-8x^{5}}{(1-x^{2})(1-16x^{4})}}}$.

Правило 190 [ править ]

Сгенерированная последовательность: 1, 7, 29, 119, 477, 1911, 7645, 30583, ... (последовательность A037576 в OEIS ). У этого есть производящая функция

${\displaystyle {\frac {1+3x}{(1-x^{2})(1-4x)}}}$.

Правило 220 [ править ]

Сгенерированная последовательность: 1, 3, 7, 15, 31, 63, 127, 255, ... (последовательность A000225 в OEIS ). Это последовательность чисел Мерсенна с производящей функцией

${\displaystyle {\frac {1}{(1-x)(1-2x)}}}$.

Имеет выражение в закрытой форме

${\displaystyle a(t)=2\cdot 2^{t}-1}$.

Обратите внимание, что правило 252 генерирует ту же последовательность.

Правило 222 [ править ]

Сгенерированная последовательность: 1, 7, 31, 127, 511, 2047, 8191, 32767, ... (последовательность A083420 в OEIS ). Это каждая вторая запись в последовательности чисел Мерсенна и имеет производящую функцию

${\displaystyle {\frac {1+2x}{(1-x)(1-4x)}}}$.

Имеет выражение в закрытой форме

${\displaystyle a(t)=2\cdot 4^{t}-1}$.

Обратите внимание, что правило 254 генерирует ту же последовательность.

Изображения для правил 0-99 [ править ]

Они начинаются с одного пикселя.

• Правило 0

• Правило 1

• Правило 2

• Правило 3

• Правило 4

• Правило 5.

• Правило 6

• Правило 7

• Правило 8

• Правило 9

• Правило 10

• Правило 11

• Правило 12

• Правило 13

• Правило 14

• Правило 15.

• Правило 16

• Правило 17

• Правило 18

• Правило 19

• Правило 20.

• Правило 21

• Правило 22

• Правило 23

• Правило 24

• Правило 25

• Правило 26

• Правило 27

• Правило 28

• Правило 29

• Правило 30

• Правило 31

• Правило 32

• Правило 33

• Правило 34

• Правило 35

• Правило 36

• Правило 37

• Правило 38

• Правило 39

• Правило 40

• Правило 41

• Правило 42

• Правило 43

• Правило 44

• Правило 45

• Правило 46

• Правило 47

• Правило 48

• Правило 49

• Правило 50

• Правило 51

• Правило 52

• Правило 53

• Правило 54

• Правило 55

• Правило 56

• Правило 57

• Правило 58

• Правило 59

• Правило 60

• Правило 61

• Правило 62

• Правило 63

• Правило 64

• Правило 65

• Правило 66

• Правило 67

• Правило 68

• Правило 69

• Правило 70

• Правило 71

• Правило 72

• Правило 73

• Правило 74

• Правило 75

• Правило 76

• Правило 77

• Правило 78

• Правило 79

• Правило 80

• Правило 81

• Правило 82

• Правило 83

• Правило 84

• Правило 85

• Правило 86

• Правило 87

• Правило 88

• Правило 89

• Правило 90

• Правило 91

• Правило 92

• Правило 93

• Правило 94

• Правило 95

• Правило 96

• Правило 97

• Правило 98

• Правило 99

Случайное начальное состояние [ править ]

Второй способ исследовать поведение этих автоматов - изучить их историю, начиная со случайного состояния. Это поведение можно лучше понять с точки зрения классов Wolfram. Вольфрам приводит следующие примеры в качестве типичных правил каждого класса. ^[2]

• Класс 1: Клеточные автоматы, которые быстро сходятся к однородному состоянию. Примерами являются правила 0, 32, 160 и 232.
• Класс 2: клеточные автоматы, которые быстро переходят в повторяющееся или стабильное состояние. Примерами являются правила 4, 108, 218 и 250.
• Класс 3: Клеточные автоматы, которые остаются в случайном состоянии. Примеры: правила 22, 30, 126, 150, 182.
• Класс 4: Клеточные автоматы, которые образуют области повторяющихся или стабильных состояний, но также образуют структуры, которые сложным образом взаимодействуют друг с другом. Примером может служить правило 110 . Было показано, что правило 110 допускает универсальные вычисления . ^[3]

Каждый вычисленный результат помещается в источник этих результатов, создавая двумерное представление эволюции системы. Следующие 88 неэквивалентных правил основаны на случайных начальных условиях:

• Правило 0

• Правило 1

• Правило 2

• Правило 3

• Правило 4

• Правило 5.

• Правило 6

• Правило 7

• Правило 8

• Правило 9

• Правило 10

• Правило 11

• Правило 12

• Правило 13

• Правило 14

• Правило 15.

• Правило 18

• Правило 19

• Правило 22

• Правило 23

• Правило 24

• Правило 25

• Правило 26

• Правило 27

• Правило 28

• Правило 29

• Правило 30

• Правило 32

• Правило 33

• Правило 34

• Правило 35

• Правило 36

• Правило 37

• Правило 38

• Правило 40

• Правило 41

• Правило 42

• Правило 43

• Правило 44

• Правило 45

• Правило 46

• Правило 50

• Правило 51

• Правило 54

• Правило 56

• Правило 57

• Правило 58

• Правило 60

• Правило 62

• Правило 72

• Правило 73

• Правило 74

• Правило 76

• Правило 77

• Правило 78

• Правило 90

• Правило 94

• Правило 104

• Правило 105

• Правило 106

• Правило 108

• Правило 110

• Правило 122

• Правило 126

• Правило 128

• Правило 130

• Правило 132

• Правило 134

• Правило 136

• Правило 138

• Правило 140

• Правило 142

• Правило 146

• Правило 150

• Правило 152

• Правило 154

• Правило 156

• Правило 160

• Правило 162

• Правило 164

• Правило 168

• Правило 170

• Правило 172

• Правило 178

• Правило 184

• Правило 200

• Правило 204

• Правило 232

Необычные случаи [ править ]

В некоторых случаях поведение клеточного автомата не сразу очевидно. Например, для правила 62 взаимодействующие структуры развиваются как в классе 4. Но в этих взаимодействиях по крайней мере одна из структур уничтожается, поэтому автомат в конечном итоге переходит в повторяющееся состояние, а клеточный автомат относится к классу 2. ^[4]

Правило 73 относится к классу 2 ^[5], потому что каждый раз, когда есть две последовательные единицы, окруженные нулями, эта функция сохраняется в последующих поколениях. Это эффективно создает стены, которые блокируют поток информации между различными частями массива. Существует конечное количество возможных конфигураций в секции между двумя стенами, поэтому автомат в конечном итоге должен начать повторяться внутри каждой секции, хотя период может быть очень длинным, если секция достаточно широкая. Эти стены будут формироваться с вероятностью 1 при полностью случайных начальных условиях. Однако, если добавлено условие, что длины серий последовательных нулей или единиц всегда должны быть нечетными, то автомат будет отображать поведение класса 3, поскольку стены никогда не могут образоваться.

Правило 54 относится к Классу 4 ^[6] и, похоже, может быть универсальным вычислением, но не было изучено так тщательно, как Правило 110. Было каталогизировано множество взаимодействующих структур, которых в совокупности должно быть достаточно для универсальности. ^[7]

Ссылки [ править ]

• Вайсштейн, Эрик В. "Элементарный клеточный автомат" . MathWorld .
• Вайсштейн, Эрик В. «Правило 30» . MathWorld .
• Вайсштейн, Эрик В. «Правило 50» . MathWorld .
• Вайсштейн, Эрик В. «Правило 54» . MathWorld .
• Вайсштейн, Эрик В. «Правило 60» . MathWorld .
• Вайсштейн, Эрик В. «Правило 62» . MathWorld .
• Вайсштейн, Эрик В. «Правило 90» . MathWorld .
• Вайсштейн, Эрик В. «Правило 94» . MathWorld .
• Вайсштейн, Эрик В. «Правило 102» . MathWorld .
• Вайсштейн, Эрик В. «Правило 110» . MathWorld .
• Вайсштейн, Эрик В. «Правило 126» . MathWorld .
• Вайсштейн, Эрик В. «Правило 150» . MathWorld .
• Вайсштейн, Эрик В. «Правило 158» . MathWorld .
• Вайсштейн, Эрик В. «Правило 182» . MathWorld .
• Вайсштейн, Эрик В. «Правило 188» . MathWorld .
• Вайсштейн, Эрик В. «Правило 190» . MathWorld .
• Вайсштейн, Эрик В. «Правило 220» . MathWorld .
• Вайсштейн, Эрик В. «Правило 222» . MathWorld .

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с элементарными клеточными автоматами .

• "Элементарные клеточные автоматы" в Атласе простых программ Вольфрама
• Отрисовка исполняемого файла MS-DOS длиной 32 байта клеточным автоматом ( по умолчанию правило 110 )
• Витрина всех правил, выбранных наугад
• Минимальная эмуляция CA с помощью парсера правил Wolfram онлайн на ванильном Javascript