Елементарний клітинний автомат

У математиці та теорії обчислюваності елементарний клітинний автомат — найпростіший можливий варіант клітинного автомата — одновимірний клітинний автомат, у якому є два можливих стани (позначені 0 і 1), а правило для визначення стану клітини в наступному поколінні залежить лише від поточного стану клітини та двох її безпосередніх сусідів.^[2] Існує елементарний клітинний автомат (правило 110, визначене нижче), який здатний виконувати універсальні обчислення, і, отже, є однією з найпростіших можливих моделей обчислень.

• Поверхня — одновимірна стрічка;
• клітина може набувати лише одного з двох значень (0 та 1); може мати лише двох сусідів;
• правила записуються у вигляді шаблонів і мають назви, котрі відповідають десятковому поданню двійкового числа, утвореного з наведених у шаблоні значень нового стану клітинки. Шаблон містить лише 8 значень. Наприклад, шаблон для правила 86 такий:

• вивід — для виведення переважно використовується двовимірний малюнок (поверхня), кожен рядок якого представляє результат обчислення клітинного автомата, завдяки чому можна побачити не лише поточний стан автомата але і його історію.

Є 8 = 2³ можливих конфігурацій для комірки та двох її безпосередніх сусідів. Правило, що визначає клітинний автомат, має задавати наступний стан для кожної з цих конфігурацій, тобто, існує 256 = 2²³ можливих елементарних клітинних автоматів. Стівен Вольфрам запропонував схему, відому як код Вольфрама^[en], де кожному правилу надано номер від 0 до 255, який став стандартним. Щоб дізнатись його:

• записують за порядком усі можливі поточні конфігурації (111, 110, … , 001, 000),
• в тому самому порядку записують стани, породжені кожною з цих конфігурацій,
• інтерпретують результат як двійкове ціле число.

Це число використовують, як номер правила автомата. Наприклад, 110₁₀ = 01101110₂. Отже, правило 110 визначається правилом переходу:

Хоча існує 256 можливих правил, багато з них тривіально еквівалентні одне одному аж до простого перетворення основної геометрії.

Першим таким перетворенням є відбиття відносно вертикальної осі, і результат застосування цього перетворення до даного правила називають дзеркальним правилом. Ці правила демонструватимуть однакову поведінку аж до відбиття відносно вертикальної осі, тому є еквівалентними в обчислювальному сенсі.

Наприклад, якщо визначення правила 110 відбити відносно вертикальної осі, то вийде таке правило (правило 124):

Правила, які збігаються зі своїм дзеркальними правилами, називають амфіхіральними. З 256 елементарних клітинних автоматів 64 є амфіхіральними.

Друге таке перетворення полягає в обміні ролями 0 і 1 у визначенні. Результат застосування цього перетворення до певного правила називають доповняльним правилом. Наприклад, якщо це перетворення застосувати до правила 110, отримаємо таке правило:

і після змінення порядку виявляється, що це правило 137:

Існує 16 правил, які збігаються з доповняльними правилами.

Зрештою, ці два перетворення можна застосувати до правила послідовно, й отримати дзеркальне доповняльне правило. Наприклад, дзеркальним доповняльним правилом для правила 110 є правило 193. Є 16 правил, які збігаються з їхніми дзеркальними доповняльними правилами.

З 256 елементарних клітинних автоматів є 88 нееквівалентних за цими перетвореннями.

Виявляється, що відбиття і доповнення є автоморфізмами моноїда одновимірних клітинних автоматів, оскільки вони обидва зберігають композицію.

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

Згенерована послідовність 1, 3, 5, 11, 21, 43, 85, 171, … послідовність A001045 з Онлайн енциклопедії послідовностей цілих чисел, OEIS. Це послідовність чисел Якобсталя, яка має твірну функцію

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

Вона має вираз замкненої форми

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

Правило 156 створює таку саму послідовність.

Згенерована послідовність: 1, 5, 21, 85, 341, 1365, 5461, 21845, … (послідовність A002450 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[3] Її твірна функція

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

Вона має вираз замкненої форми

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

Зауважте, що правила 58, 114, 122, 178, 186, 242 і 250 генерують однакові послідовності.

Згенерована послідовність: 1, 7, 17, 119, 273, 1911, 4369, 30583, … (послідовність A118108 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[4] Вона має твірну функцію

${\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}}}$.

Згенерована послідовність: 1, 3, 5, 15, 17, 51, 85, 255, … (послідовність A001317 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[5] Її можна отримати, взявши послідовні рядки трикутника Паскаля за модулем 2 та інтерпретуючи їх як цілі числа в двійковій системі, які можна графічно подати трикутником Серпінського.

Згенерована послідовність: 1, 5, 17, 85, 257, 1285, 4369, 21845, … (послідовність A038183 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[6] Її можна отримати, взявши послідовні рядки трикутника Паскаля за модулем 2 та інтерпретуючи їх як цілі числа за основою 4. Зауважте, що правила 18, 26, 82, 146, 154, 210 і 218 генерують однакові послідовності.

Згенерована послідовність: 1, 7, 27, 119, 427, 1879, 6827, 30039, … (послідовність A118101 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[7] Її можна виразити як

${\displaystyle a(t)={\begin{cases}1,&{\mbox{якщо }}t=0\\[5px]7,&{\mbox{якщо }}t=1\\[7px]{\dfrac {1+5\cdot 4^{n}}{3}},&{\mbox{якщо }}t{\mbox{ парне }}\\[7px]{\dfrac {10+11\cdot 4^{n}}{6}},&{\mbox{якщо }}t{\mbox{ непарне }}\end{cases}}}$.

Її твірна функція

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

Згенерована послідовність: 1, 6, 20, 120, 272, 1632, 5440, 32640, … (послідовність A117998 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[8] Це послідовність, створена за правилом 60 (дзеркальне правило), помножена на послідовні степені 2.

Згенерована послідовність: 1, 6, 28, 104, 496, 1568, 7360, 27520, 130304, 396800, … (послідовність A117999 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[9] Правило 110 має цікаву властивість: воно повне за Тюрінгом і, отже, придатне для універсальних обчислень.^[10]

Згенерована послідовність: 1, 7, 21, 107, 273, 1911, 5189, 28123, … (послідовність A038184 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[11] Її можна отримати, взявши коефіцієнти послідовних степенів (1+x+x²) за модулем 2 та інтерпретуючи їх як цілі числа в двійковій системі.

Згенерована послідовність: 1, 7, 29, 115, 477, 1843, 7645, 29491, … (послідовність A118171 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[12] Її твірна функція

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

Згенерована послідовність 1, 3, 5, 15, 29, 55, 93, 247, … (послідовність A118173 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[13] Її твірна функція

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

Згенерована послідовність: 1, 7, 29, 119, 477, 1911, 7645, 30583, … (послідовність A037576 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[14] Її твірна функція

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

Згенерована послідовність: 1, 3, 7, 15, 31, 63, 127, 255, … (послідовність A000225 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[15] Це послідовність чисел Мерсенна, яка має твірну функцію

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

Її вираз замкненої форми

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

Правило 252 створює таку саму послідовність.

Згенерована послідовність: 1, 7, 31, 127, 511, 2047, 8191, 32767, … (послідовність A083420 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).^[16] Це кожне друге з послідовності чисел Мерсенна, твірна функція така:

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

Вираз замкненої форми

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

Правило 254 генерує таку саму послідовність.

На малюнках зображено просторово-часові діаграми, на яких кожен рядок пікселів показує клітини автомата в один момент часу зі збільшенням часу вниз. Всі вони починаються зі стану автомата, в якому одна клітина, піксель у центрі верхнього ряду пікселів, перебуває в стані 1, а всі інші клітини — 0.

• 
  Правило 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^[17]
• 
  Правило 31
• 
  Правило 32
• 
  Правило 33
• 
  Правило 34
• 
  Правило 35
• 
  Правило 36
• 
  Правило 37
• 
  Правило 38
• 
  Правило 39
• 
  Правило 40
• 
  Правило 41
• 
  Правило 42
• 
  Правило 43
• 
  Правило 44
• 
  Правило 45
• 
  Правило 46
• 
  Правило 47
• 
  Правило 48
• 
  Правило 49
• 
  Правило 50^[3]
• 
  Правило 51
• 
  Правило 52
• 
  Правило 53
• 
  Правило 54^[4]
• 
  Правило 55
• 
  Правило 56
• 
  Правило 57
• 
  Правило 58
• 
  Правило 59
• 
  Правило 60^[5]
• 
  Правило 61
• 
  Правило 62^[18]
• 
  Правило 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^[6]
• 
  Правило 91
• 
  Правило 92
• 
  Правило 93
• 
  Правило 94^[7]
• 
  Правило 95
• 
  Правило 96
• 
  Правило 97
• 
  Правило 98
• 
  Правило 99

Другий спосіб дослідити поведінку цих автоматів — вивчити їхню історію, починаючи з випадкового стану. Цю поведінку можна краще зрозуміти з точки зору класів Вольфрама. Вольфрам наводить такі приклади типових правил кожного класу:

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

Кожен обчислений результат розміщується під джерелом цього результату, створюючи двовимірне подання еволюції системи.

У наведеній нижче галереї для кожного з 88 нееквівалентних правил показано еволюцію від випадкових початкових умов. Під кожним зображенням наведено номер правила, використаного для створення зображення, а в дужках включено номери еквівалентних правил, створених відбиттям або доповненням, якщо вони існують.^[19] Як ішлося вище, відбите правило створить відбите зображення, тоді як доповняльне правило створить зображення з обміном чорного та білого.

• 
  Правило 0 (255)
• 
  Правило 1 (127)
• 
  Правило 2 (16, 191, 247)
• 
  Правило 3 (17, 63, 119)
• 
  Правило 4 (223)
• 
  Правило 5 (95)
• 
  Правило 6 (20, 159, 215)
• 
  Правило 7 (21, 31, 87)
• 
  Правило 8 (64, 239, 253)
• 
  Правило 9 (65, 111, 125)
• 
  Правило 10 (80, 175, 245)
• 
  Правило 11 (47, 81, 117)
• 
  Правило 12 (68, 207, 221)
• 
  Правило 13 (69, 79, 93)
• 
  Правило 14 (84, 143, 213)
• 
  Правило 15 (85)
• 
  Правило 18 (183)
• 
  Правило 19 (55)
• 
  Правило 22 (151)
• 
  Правило 23
• 
  Правило 24 (66, 189, 231)
• 
  Правило 25 (61, 67, 103)
• 
  Правило 26 (82, 167, 181)
• 
  Правило 27 (39, 53, 83)
• 
  Правило 28 (70, 157, 199)
• 
  Правило 29 (71)
• 
  Правило 30^[17] (86, 135, 149)
• 
  Правило 32 (251)
• 
  Правило 33 (123)
• 
  Правило 34 (48, 187, 243)
• 
  Правило 35 (49, 59, 115)
• 
  Правило 36 (219)
• 
  Правило 37 (91)
• 
  Правило 38 (52, 155, 211)
• 
  Правило 40 (96, 235, 249)
• 
  Правило 41 (97, 107, 121)
• 
  Правило 42 (112, 171, 241)
• 
  Правило 43 (113)
• 
  Правило 44 (100, 203, 217)
• 
  Правило 45 (75, 89, 101)
• 
  Правило 46 (116, 139, 209)
• 
  Правило 50^[3] (179)
• 
  Правило 51
• 
  Правило 54^[4] (147)
• 
  Правило 56 (98, 185, 227)
• 
  Правило 57 (99)
• 
  Правило 58 (114, 163, 177)
• 
  Правило 60^[5] (102, 153, 195)
• 
  Правило 62^[18] (118, 131, 145)
• 
  Правило 72 (237)
• 
  Правило 73 (109)
• 
  Правило 74 (88, 173, 229)
• 
  Правило 76 (205)
• 
  Правило 77
• 
  Правило 78 (92, 141, 197)
• 
  Правило 90^[6] (165)
• 
  Правило 94^[7] (133)
• 
  Правило 104 (233)
• 
  Правило 105
• 
  Правило 106 (120, 169, 225)
• 
  Правило 108 (201)
• 
  Правило 110^[9] (124, 137, 193)
• 
  Правило 122 (161)
• 
  Правило 126^[20] (129)
• 
  Правило 128 (254)
• 
  Правило 130 (144, 190, 246)
• 
  Правило 132 (222)
• 
  Правило 134 (148, 158, 214)
• 
  Правило 136 (192, 238, 252)
• 
  Правило 138 (174, 208, 244)
• 
  Правило 140 (196, 206, 220)
• 
  Правило 142 (212)
• 
  Правило 146 (182)
• 
  Правило 150^[11]
• 
  Правило 152 (188, 194, 230)
• 
  Правило 154 (166, 180, 210)
• 
  Правило 156 (198)
• 
  Правило 160 (250)
• 
  Правило 162 (176, 186, 242)
• 
  Правило 164 (218)
• 
  Правило 168 (224, 234, 248)
• 
  Правило 170 (240)
• 
  Правило 172 (202, 216, 228)
• 
  Правило 178
• 
  Правило 184 (226)
• 
  Правило 200 (236)
• 
  Правило 204
• 
  Правило 232

У деяких випадках поведінка клітинного автомата не відразу очевидна. Наприклад, для Правила 62^[18] взаємодійні структури розвиваються як у Класі 4. Але в цих взаємодіях принаймні одна зі структур анігілюється, тому автомат зрештою переходить у повторюваний стан і клітинний автомат належить до класу 2.

Правило 73 належить до класу 2, оскільки щоразу, коли з'являється дві послідовні одиниці, оточені нулями, вони зберігаються в наступних поколіннях. Це створює «стіни», які блокують потік інформації між різними частинами масиву. Існує скінченна кількість можливих конфігурацій у секції між двома стінами, тому автомат повинен зрештою почати повторюватися всередині кожної секції, хоча період може бути дуже довгим, якщо секція достатньо широка. Ці стіни утворюються з імовірністю 1 для цілком випадкових початкових умов. Однак, якщо довжина послідовностей 0 або 1 завжди непарна, то автомат демонструє поведінку класу 3, оскільки стіни ніколи не можуть утворитися.

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

1. ↑ R.Ugalde, Laurence. Elementary cellular automaton in the Fōrmulæ programming language. Fōrmulæ. Процитовано 9 червня 2024.
2. ↑ Weisstein, Eric W. Elementary Cellular Automaton(англ.) на сайті Wolfram MathWorld.
3. ↑ ^{а б в} Weisstein, Eric W. Правило 50(англ.) на сайті Wolfram MathWorld.
4. ↑ ^{а б в г} Weisstein, Eric W. Правило 54(англ.) на сайті Wolfram MathWorld.
5. ↑ ^{а б в} Weisstein, Eric W. Правило 60(англ.) на сайті Wolfram MathWorld.
6. ↑ ^{а б в} Weisstein, Eric W. Правило 90(англ.) на сайті Wolfram MathWorld.
7. ↑ ^{а б в} Weisstein, Eric W. Правило 94(англ.) на сайті Wolfram MathWorld.
8. ↑ Weisstein, Eric W. Правило 102(англ.) на сайті Wolfram MathWorld.
9. ↑ ^{а б} Weisstein, Eric W. Правило 110(англ.) на сайті Wolfram MathWorld.
10. ↑ Cook, Matthew (25 червня 2009). A Concrete View of Rule 110 Computation. Electronic Proceedings in Theoretical Computer Science. 1: 31—55. arXiv:0906.3248. doi:10.4204/EPTCS.1.4. ISSN 2075-2180.
11. ↑ ^{а б} Weisstein, Eric W. Правило 150(англ.) на сайті Wolfram MathWorld.
12. ↑ Weisstein, Eric W. Правило 158(англ.) на сайті Wolfram MathWorld.
13. ↑ Weisstein, Eric W. Правило 188(англ.) на сайті Wolfram MathWorld.
14. ↑ Weisstein, Eric W. Правило 190(англ.) на сайті Wolfram MathWorld.
15. ↑ Weisstein, Eric W. Правило 220(англ.) на сайті Wolfram MathWorld.
16. ↑ Weisstein, Eric W. Правило 222(англ.) на сайті Wolfram MathWorld.
17. ↑ ^{а б} Weisstein, Eric W. Правило 30(англ.) на сайті Wolfram MathWorld.
18. ↑ ^{а б в} Weisstein, Eric W. Правило 62(англ.) на сайті Wolfram MathWorld.
19. ↑ Wolfram, Stephen (1994). Tables of Cellular Automaton Properties. Cellular Automata and Complexity: Collected Papers (PDF). Westview Press. с. 516—521. ISBN 0-201-62716-7.
20. ↑ Weisstein, Eric W. Правило 126(англ.) на сайті Wolfram MathWorld.
21. ↑ Martínez, Genaro Juárez; Adamatzky, Andrew; McIntosh, Harold V. (1 квітня 2006). Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates (PDF). Chaos, Solitons & Fractals. 28 (1): 100—111. Bibcode:2006CSF....28..100M. doi:10.1016/j.chaos.2005.05.013. ISSN 0960-0779.

• «Елементарні клітинні автомати» в атласі простих програм Wolfram [Архівовано 12 липня 2013 у Wayback Machine.]
• 32-байтовий виконуваний файл MS-DOS який малює клітинний автомат (за замовчуванням — правило 110)
• Демонстрація всіх правил, вибраних навмання
• Мінімальна емуляція КА зі синтаксичним аналізатором правил Вольфрама онлайн на ванільному Javascript
• Wolfram Elementary Cellular Automata (The Nature of Code)^{[недоступне посилання з вересня 2019]}