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

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

Кожен кінцевий автомат в просторі фон Неймана може приймати одне з 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.

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

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