Автомат фон Неймана

Клітинний автомат фон Неймана - клітинний автомат, розроблений фон Нейманом за сприяння Станіслава Улама для дослідження можливості створення самовідтворюваних машин.

Одна з простих конфігурацій в клітинному автоматі фон Неймана. Двійковий сигнал циркулює вздовж петлі з синіх комірок, використовуючи перехід між звичайним і збудженим станом передавальних комірок. Комутувальна комірка дублює сигнал в червону лінію, що складається з комірок особливого передавального стану. Сигнал проходить по лінії і створює нову комірку. Двійковий сигнал 1011 кодує східно-орієнтований передавальний стан, таким чином продовжуючи лінію вправо. У процесі створення нова комірка, керована бінарної послідовністю, проходить ряд сенсибілізованих станів.

Визначення

Конфігурація

Клітинний автомат в загальному вигляді є впорядкованою множиною кінцевих автоматів, які обмінюються інформацією з сусідніми автоматами. У клітинному автоматі фон Неймана комірки впорядковані у вигляді двомірної прямокутної решітки і взаємодіють з чотирма прилеглими комірками, що утворюють окіл фон Неймана. Решітка вважається має нескінченний розмір в обох напрямках, а комірки - ідентичними в плані правил переходу. Зміна станів всіх осередків відбувається синхронно.

Стани

Кожен кінцевий автомат в просторі фон Неймана може приймати одне з 29 станів:

1. базовий стан U
2. транзитні (або чутливі) стани
   1. S
   2. S₀
   3. S₀₀
   4. S₀₁
   5. S₀₀₀
   6. S₁
   7. S₁₀
   8. S₁₁
3. конфлюентні стани
   1. C₀₀
   2. C₁₀
   3. C₀₁
   4. C₁₁
4. звичайний передавальний стан
   1. T₀₀ вправо
   2. T₀₁ вверх
   3. T₀₂ вліво
   4. T₀₃ вниз
5. спеціальний передавальний стан
   1. T₁₀ вправо
   2. T₁₁ вверх
   3. T₁₂ вліво
   4. T₁₃ вниз

Кожне з передавальних станів (8 станів) також характеризується збудженістю / непорушенням (зелені / сині стрілочки), що дає в результаті 16 передавальних станів. Збуджений стан переносить дані зі швидкістю 1 біт за такт. Конфлюентних стану мають затримку на один такт, і таким чином можуть зберігати 2 біти інформації.

Правила переходу передавальних станів

Потік інформації між комірками визначається властивістю спрямованості. Застосовуються наступні правила:

• Передавальному стану застосовують оператор АБО до вхідних сигналів, тобто комірка в передавальному стані (звичайному або спеціальному) перейде в збуджену на такті t+1 якщо будь-який з вхідних сигналів є збудженим на такті t

• Стани передаються між передавальними комірками відповідно властивості спрямованості.

• Звичайні та спеціальні передавальні стани є «антагоністами»:

• • Якщо осередок А на такті t в звичайному збудженому передавальному стані вказує на комірку В в будь-якому спеціальному передавальному стані, то на такті t+1 комірка В перейде в базовий стан U. Особливий передавальний стан буде «знищено».

• • Аналогічне подія відбудеться, якщо комірка в спеціальному передавальному стані буде вказувати на звичайну передавальну комірку.

Правила переходу конфлюентних станів

Наступні правила застосовуються до конфлюентних станів:

• Конфлюентні комірки залишаються поза передачею даних між собою.

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

• Дані не передаються в напрямку, протилежної спрямованості передавальної комірки.

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

• Конфлюентні комірки служать мостами між звичайними і спеціальними передавальними комірками.

• Конфлюентні комірки застосовують оператор І до вхідних сигналів.

• Конфлюентні комірки затримують сигнал на один такт довше, ніж звичайні передавальні комірки.

Правила переходу транзитних станів

Дев'ять типів осередків, які можуть бути створені в КА фон Неймана. Тут двійкові сигнали проходять по звичайних передавальних комірках, створюючи нові осередки на кінці ліній. Наприклад, двійковий рядок 1011 показаний в п'ятій лінії, створює спеціальний передавальний стан з напрямком вправо. Взаємодія між передавальними лініями відсутня, що дозволяє щільно упаковувати комірки.

У початковому стані більша частина клітинного простору є «порожньою», тобто заповненою комірками в стані U. Отримавши вхідний сигнал від передавальної комірки, сусідня комірка в стані U переходить в транзитний стан, проходить ряд станів і виявляється в одному з передавальних або конфлюентних станів. Це кінцевий стан визначається послідовністю вхідних сигналів. Тобто транзитні стани можуть розглядатися як точки біфуркації на шляху від базового стану до передавальних і конфлюентних. У наступних правилах послідовність вхідних сигналів вказана в дужках двійковій рядком:

• комірка в базовому стані U, отримавши сигнал, переходить в стан S (1)
• комірка в стані S, не отримавши сигнал, переходить в S₀ (10)
  • комірка в стані S₀, не отримавши сигнал, переходить в S₀₀ (100)
    • комірка S₀₀, не отримавши сигнал, переходить в S₀₀₀ (1000)
      • комірка S₀₀₀, не отримавши сигнал, переходить в T₀₀ (10000)
      • комірка S₀₀₀, отримавши сигнал, переходить в T₀₁ (10001)
    • комірка S₀₀, отримавши сигнал, переходить в T₀₂ (1001)
  • комірка S₀, отримавши сигнал, переходить в S₀₁ (101)
    • комірка S₀₁, не отримавши сигнал, переходить в T₀₃ (1010)
    • комірка S₀₁, отримавши сигнал, переходить в T₁₀ (1011)
• комірка S, отримавши сигнал, переходить в S₁ (11)
  • комірка S₁, не отримавши сигнал, переходить в S₁₀ (110)
    • комірка S₁₀, не отримавши сигнал, переходить в T₁₁ (1100)
    • комірка S₁₀, отримавши сигнал, переходить в T₁₂ (1101)
  • комірка S₁, отримавши сигнал, переходить в S₁₁ (111)
    • комірка S₁₁, не отримавши сигнал, переходить в T₁₃ (1110)
    • комірка S₁₁, отримавши сигнал, переходить в C₀₀ (1111)

Руйнувальні правила

Приблизно 4000 бітів даних конструюють складний патерн. Тут використовується різновид КА фон Неймана з 32 станами, відома як Hutton32.

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

• Вхідний сигнал від звичайної передавальної комірки, отриманий спеціальної передавальною коміркою, переводить цю комірку в базовий.

Модифікації

Одним з різновидів автомата фон Неймана є автомат Нобілі, в якому введено додаткові стани для забезпечення пам'яті і можливості перетину сигналів без інтерференції, для чого використана можливість зберігання інформації групами клітин. Остання функція вимагає три додаткових стани, в силу чого автомат Нобілі має 32 стани, а не 29. Є винаходом (італ. Renato Nobili), професора фізики університету Падуя, Італія. Фон Нейман навмисно виключив стани, призначені для перетину сигналів.

Конфлюентний стан змінено таким чином, щоб передавати незалежно один від одного два сигнали,які одночасно прийшли, або запам'ятовувати і передавати з затримкою вхідні сигнали.

Ще одним різновидом є автомат Хаттона (англ. Hutton), що допускає реплікацію кільцевих структур (див. Langton's loops англійською мовою).

Література

• Von Neumann, J. and A. W. Burks (1966). Theory of self-reproducing automata. Urbana, University of Illinois Press. [1] чи [2]