Útočná puška von Neumann

Von Neumannův celulární automat  je celulární automat vyvinutý Johnem von Neumannem s pomocí Stanisława Ulama , aby prozkoumal možnost vytvoření sebereplikujících se strojů .

Definice

Konfigurace

Obecně je celulární automat uspořádaná množina konečných automatů , které si vyměňují informace se sousedními automaty. Ve von Neumannově buněčném automatu jsou buňky uspořádány do dvourozměrné pravoúhlé mřížky a interagují se čtyřmi přímo sousedícími buňkami tvořícími von Neumannovo okolí . Předpokládá se, že mřížka má nekonečnou velikost v obou směrech a buňky jsou identické z hlediska pravidel přechodu. Ke změně stavů všech buněk dochází synchronně.

Státy

Každý stavový automat ve von Neumannově prostoru může mít jeden z 29 stavů:

1. základní stav U
2. tranzitivní (neboli citlivé) stavy
   1. S
   2. S0 _
   3. S00 _
   4. S01 _
   5. S000 _
   6. S1 _
   7. S 10
   8. S 11
3. souvislé státy
   1. C00 _
   2. C 10
   3. C01 _
   4. C 11
4. normální stav vysílání
   1. T 00 správně
   2. T 01 nahoru
   3. T 02 vlevo
   4. T 03 dolů
5. zvláštní stav přenosu
   1. T 10 vpravo
   2. T 11 nahoru
   3. T 12 vlevo
   4. T 13 dolů

Každý z vysílacích stavů (8 stavů) je také charakterizován buzení/nebuzení (zelené/modré šipky), což dává celkem 16 vysílacích stavů. Vybuzený stav přenáší data rychlostí 1 bit za hodinu. Konfluentní stavy mají zpoždění jednoho cyklu, a tak mohou uložit 2 bity informace.

Pravidla přechodu stavu přenosu

Tok informací mezi buňkami je určen vlastností směrovosti. Platí následující pravidla:

• Vysílací stavy aplikují na vstupní signály operátor OR, tj. buňka ve vysílacím stavu (běžném nebo speciálním) přejde na buzení v čase t+1 , pokud je některý ze vstupních signálů vybuzen v čase t .
• Stavy jsou přenášeny mezi vysílacími buňkami podle směrové vlastnosti.
• Běžné a speciální vysílací stavy jsou „antagonisté“:
  • Jestliže buňka A v hodinách t v normálním excitovaném vysílacím stavu ukazuje na buňku B v jakémkoli speciálním vysílacím stavu, pak v čase t+1 buňka B přejde do základního stavu U. Zvláštní vysílací stav bude „zničen“.
  • K podobné události dojde, pokud buňka ve speciálním vysílajícím stavu ukazuje na normální vysílací buňku.

Pravidla pro přechod splývajících stavů

Následující pravidla platí pro splývající státy:

• Konfluentní buňky mezi sebou nepřenášejí data.
• Konfluentní buňky přijímají vstupy z jedné nebo více normálních vysílacích buněk a poskytují je vysílacím buňkám (běžným nebo speciálním), které nesměřují na aktuální buňku.
• Data nejsou přenášena v opačném směru než vysílající buňka.
• Data uložená konfluentní buňkou jsou ztracena, pokud nemá žádné sousední vysílací buňky (neukazující na ni).
• Konfluentní buňky slouží jako mosty mezi konvenčními a speciálními buňkami vysílače.
• Konfluentní buňky aplikují operátor AND na vstupní signály.
• Konfluentní buňky zpožďují signál o jeden cyklus déle než konvenční vysílací buňky.

Přechodová pravidla

V počátečním stavu je většina buněčného prostoru „prázdná“, to znamená, že je vyplněna buňkami ve stavu U. Po přijetí vstupního signálu z vysílací buňky přejde sousední buňka ve stavu U do tranzitního stavu, projde řadou stavů a ​​skončí v jednom z vysílacích nebo konfluentních stavů. Tento konečný stav je určen posloupností vstupních signálů. To znamená, že tranzitní stavy lze považovat za bifurkační body na cestě ze základního stavu k vysílacím a konfluentním. V následujících pravidlech je sekvence vstupních signálů označena v závorkách binárním řetězcem:

• buňka v základním stavu U po přijetí signálu přejde do stavu S (1)
• buňka ve stavu S , aniž by přijala signál, přejde do stavu S 0 (10)
  • buňka ve stavu S 0 , aniž by přijala signál, přejde do S 00 (100)
    • buňka S 00 , aniž by přijala signál, přejde na S 000 (1000)
      • buňka S 000 bez příjmu signálu přejde na T 00 (10 000)
      • buňka S 000 po přijetí signálu přejde na T 01 (10001)
    • buňka S 00 po přijetí signálu přejde na T 02 (1001)
  • buňka S 0 po přijetí signálu přejde na S 01 (101)
    • buňka S 01 bez příjmu signálu přejde na T 03 (1010)
    • buňka S 01 po přijetí signálu přejde na T 10 (1011)
• buňka S po přijetí signálu přejde na S 1 (11)
  • buňka S 1 , aniž by přijala signál, přejde na S 10 (110)
    • buňka S 10 , aniž by přijala signál, přejde na T 11 (1100)
    • buňka S 10 po přijetí signálu přejde na T 12 (1101)
  • buňka S 1 po přijetí signálu přejde na S 11 (111)
    • buňka S 11 , aniž by přijala signál, přejde na T 13 (1110)
    • buňka S 11 po přijetí signálu přejde na C 00 (1111)

Porušení pravidel

• Vstupní signál ze speciální vysílací buňky, přijatý buňkou v konfluentním nebo normálním vysílacím stavu, uvede tuto buňku do základního stavu.
• Vstupní signál z normální vysílací buňky přijatý speciální vysílací buňkou převádí tuto buňku na základní buňku.

Úpravy

Jednou z odrůd von Neumannova automatu je automat Nobili , ve kterém jsou zavedeny další stavy pro zajištění paměti a možnosti křížení signálů bez rušení, pro které se využívá možnost ukládání informací po skupinách buněk. Poslední funkce vyžaduje tři další stavy, což je důvod, proč má automat Nobili 32 stavů, nikoli 29. Je to vynález Renato Nobili ( italsky  Renato Nobili ), profesora fyziky na univerzitě v Padově v Itálii . Von Neumann záměrně vyloučil státy určené pro přechody signálů.

Konfluentní stav se mění tak, aby se přenášely dva současně přicházející signály nezávisle na sobě, nebo aby se vstupní signály ukládaly a vysílaly se zpožděním.

Další variací je Huttonův automat , který umožňuje replikaci prstencových struktur (viz Langtonovy smyčky v angličtině  ) .

Viz také

• Von Neumannův stroj

Odkazy

• J. von Neumann, Teorie samoreprodukujících se automatů. M.: Mir, 1971.