Автомат фон Неймана
Клітинний автомат фон Неймана - клітинний автомат, розроблений фон Нейманом за сприяння Станіслава Улама для дослідження можливості створення самовідтворюваних машин.
![](../I/VonNeumann_CA_demo.gif)
Визначення
Конфігурація
Клітинний автомат в загальному вигляді є впорядкованою множиною кінцевих автоматів, які обмінюються інформацією з сусідніми автоматами. У клітинному автоматі фон Неймана комірки впорядковані у вигляді двомірної прямокутної решітки і взаємодіють з чотирма прилеглими комірками, що утворюють окіл фон Неймана. Решітка вважається має нескінченний розмір в обох напрямках, а комірки - ідентичними в плані правил переходу. Зміна станів всіх осередків відбувається синхронно.
Стани
Кожен кінцевий автомат в просторі фон Неймана може приймати одне з 29 станів:
- базовий стан U
- транзитні (або чутливі) стани
- S
- S0
- S00
- S01
- S000
- S1
- S10
- S11
- конфлюентні стани
- C00
- C10
- C01
- C11
- звичайний передавальний стан
- T00 вправо
- T01 вверх
- T02 вліво
- T03 вниз
- спеціальний передавальний стан
- T10 вправо
- T11 вверх
- T12 вліво
- T13 вниз
Кожне з передавальних станів (8 станів) також характеризується збудженістю / непорушенням (зелені / сині стрілочки), що дає в результаті 16 передавальних станів. Збуджений стан переносить дані зі швидкістю 1 біт за такт. Конфлюентних стану мають затримку на один такт, і таким чином можуть зберігати 2 біти інформації.
Правила переходу передавальних станів
Потік інформації між комірками визначається властивістю спрямованості. Застосовуються наступні правила:
- Передавальному стану застосовують оператор АБО до вхідних сигналів, тобто комірка в передавальному стані (звичайному або спеціальному) перейде в збуджену на такті t+1 якщо будь-який з вхідних сигналів є збудженим на такті t
- Стани передаються між передавальними комірками відповідно властивості спрямованості.
- Звичайні та спеціальні передавальні стани є «антагоністами»:
- Якщо осередок А на такті t в звичайному збудженому передавальному стані вказує на комірку В в будь-якому спеціальному передавальному стані, то на такті t+1 комірка В перейде в базовий стан U. Особливий передавальний стан буде «знищено».
- Аналогічне подія відбудеться, якщо комірка в спеціальному передавальному стані буде вказувати на звичайну передавальну комірку.
Правила переходу конфлюентних станів
Наступні правила застосовуються до конфлюентних станів:
- Конфлюентні комірки залишаються поза передачею даних між собою.
- Конфлюентні комірки приймають вхідні сигнали від однієї або декількох звичайних передавальних комірок і видають їх передавальним коміркам (звичайним або спеціальним), які не вказують на поточну комірку.
- Дані не передаються в напрямку, протилежної спрямованості передавальної комірки.
- Дані, що зберігаються конфлюентною коміркою, губляться, якщо у неї немає прилеглих передавальних комірок (які не вказують на неї).
- Конфлюентні комірки служать мостами між звичайними і спеціальними передавальними комірками.
- Конфлюентні комірки застосовують оператор І до вхідних сигналів.
- Конфлюентні комірки затримують сигнал на один такт довше, ніж звичайні передавальні комірки.
Правила переходу транзитних станів
![](../I/VonNeumann_CA_construction_demo.gif)
У початковому стані більша частина клітинного простору є «порожньою», тобто заповненою комірками в стані U. Отримавши вхідний сигнал від передавальної комірки, сусідня комірка в стані U переходить в транзитний стан, проходить ряд станів і виявляється в одному з передавальних або конфлюентних станів. Це кінцевий стан визначається послідовністю вхідних сигналів. Тобто транзитні стани можуть розглядатися як точки біфуркації на шляху від базового стану до передавальних і конфлюентних. У наступних правилах послідовність вхідних сигналів вказана в дужках двійковій рядком:
- комірка в базовому стані U, отримавши сигнал, переходить в стан S (1)
- комірка в стані S, не отримавши сигнал, переходить в S0 (10)
- комірка в стані S0, не отримавши сигнал, переходить в S00 (100)
- комірка S00, не отримавши сигнал, переходить в S000 (1000)
- комірка S000, не отримавши сигнал, переходить в T00 (10000)
- комірка S000, отримавши сигнал, переходить в T01 (10001)
- комірка S00, отримавши сигнал, переходить в T02 (1001)
- комірка S00, не отримавши сигнал, переходить в S000 (1000)
- комірка S0, отримавши сигнал, переходить в S01 (101)
- комірка S01, не отримавши сигнал, переходить в T03 (1010)
- комірка S01, отримавши сигнал, переходить в T10 (1011)
- комірка в стані S0, не отримавши сигнал, переходить в S00 (100)
- комірка S, отримавши сигнал, переходить в S1 (11)
- комірка S1, не отримавши сигнал, переходить в S10 (110)
- комірка S10, не отримавши сигнал, переходить в T11 (1100)
- комірка S10, отримавши сигнал, переходить в T12 (1101)
- комірка S1, отримавши сигнал, переходить в S11 (111)
- комірка S11, не отримавши сигнал, переходить в T13 (1110)
- комірка S11, отримавши сигнал, переходить в C00 (1111)
- комірка S1, не отримавши сигнал, переходить в S10 (110)
Руйнувальні правила
![](../I/Pixel_golly.gif)
- Вхідний сигнал від спеціальної передавальної комірки, отриманий коміркою в конфлюентному або звичайному передавальному стані, переводить цю комірку в базовий.
- Вхідний сигнал від звичайної передавальної комірки, отриманий спеціальної передавальною коміркою, переводить цю комірку в базовий.
Модифікації
Одним з різновидів автомата фон Неймана є автомат Нобілі, в якому введено додаткові стани для забезпечення пам'яті і можливості перетину сигналів без інтерференції, для чого використана можливість зберігання інформації групами клітин. Остання функція вимагає три додаткових стани, в силу чого автомат Нобілі має 32 стани, а не 29. Є винаходом Ренато Нобілі (італ. Renato Nobili), професора фізики університету Падуя, Італія. Фон Нейман навмисно виключив стани, призначені для перетину сигналів.
Конфлюентний стан змінено таким чином, щоб передавати незалежно один від одного два сигнали,які одночасно прийшли, або запам'ятовувати і передавати з затримкою вхідні сигнали.
Ще одним різновидом є автомат Хаттона (англ. Hutton), що допускає реплікацію кільцевих структур (див. Langton's loops англійською мовою).