Von Neumann celulární automat - Von Neumann cellular automaton

Jednoduchá konfigurace v von Neumannově celulárním automatu. Binární signál je opakovaně předáván kolem smyčky modrého vodiče pomocí buzení a klidového stavu běžné přenosové stavy. Soutoková buňka duplikuje signál na délku červeného drátu, který se skládá z speciální přenosové stavy. Signál prochází tímto drátem a na konci vytvoří novou buňku. Tento konkrétní signál (1011) kóduje speciální stav přenosu na východ, čímž pokaždé prodlužuje červený vodič o jednu buňku. Během výstavby prochází nová buňka několika senzibilizovanými stavy, které jsou směrovány binární sekvencí.

Von Neumann celulární automaty jsou původním výrazem mobilní automaty, jehož vývoj byl podněcován návrhy na John von Neumann jeho blízký přítel a kolega matematik Stanislaw Ulam. Jejich původním účelem bylo poskytnout vhled do logických požadavků pro automatická replikace stroje a byly použity u von Neumanna univerzální konstruktor.

Nobiliho buněčný automat je variace von Neumannova buněčného automatu, rozšířená o schopnost konfluentních buněk křížit signály a ukládat informace. První vyžaduje další tři stavy, proto má Nobiliho buněčný automat 32 stavů, nikoli 29. Huttonův buněčný automat je další variantou, která umožňuje smyčku dat, analogickou k Langtonovy smyčky, replikovat.

Definice

Konfigurace

Obecně celulární automaty (CA) tvoří uspořádání konečné automaty (FSA), které sedí v pozičních vztazích mezi sebou navzájem, přičemž každý FSA si vyměňuje informace s těmi dalšími FSA, ke kterým je pozičně přilehlý. V von Neumannově buněčném automatu stroje s konečným stavem (nebo buňky) jsou uspořádány do dvourozměrného Kartézská mřížka a rozhraní s okolními čtyřmi buňkami. Protože von Neumannův buněčný automat byl prvním příkladem použití tohoto uspořádání, je znám jako sousedství von Neumann.

Sada FSA definuje a buněčný prostor nekonečné velikosti. Všechny FSA jsou identické z hlediska funkce přechodu stavu nebo sady pravidel.

The sousedství (funkce seskupení) je součástí funkce přechodu stavu a definuje pro každou buňku sadu dalších buněk, na kterých závisí stav dané buňky.

Všechny buňky provádějí své přechody synchronně, v kroku s univerzálními „hodinami“ jako v synchronním digitálním obvodu.

Státy

Každý FSA von Neumannova buněčného prostoru může přijmout kterýkoli z 29 stavů sady pravidel. Sada pravidel je seskupena do pěti ortogonálních podmnožin. Každý stav zahrnuje barvu buňky v programu celulárních automatů Golly v (červená, zelená, modrá). Oni jsou

  1. A přízemní Stát U   (48, 48, 48)
  2. the přechod nebo senzibilizovaný stavy (v 8 substrátech)
    1. S (nově senzibilizovaný)   (255, 0, 0)
    2. S0 - (senzibilizováno, protože pro jeden cyklus nebyl přijat žádný vstup)   (255, 125, 0)
    3. S00 - (senzibilizovaný, nepřijal žádný vstup po dobu dvou cyklů)   (255, 175, 50)
    4. S000 - (senzibilizovaný, po dobu tří cyklů nedostal žádný vstup)   (251, 255, 0)
    5. S01 - (senzibilizováno, neobdrželi žádný vstup pro jeden cyklus a poté vstup pro jeden cyklus)   (255, 200, 75)
    6. S1 - (senzibilizovaný, obdržel vstup pro jeden cyklus)   (255, 150, 25)
    7. S10 - (senzibilizovaný, obdržel vstup pro jeden cyklus a poté žádný vstup pro jeden cyklus)   (255, 255, 100)
    8. S11 - (senzibilizovaný, přijímající vstup po dobu dvou cyklů)   (255, 250, 125)
  3. the soutok stavy (ve 4 stavech buzení)
    1. C00 - v klidu (a bude také v klidu v dalším cyklu)   (0, 255, 128)
    2. C01 - next-excited (now quiescent, but will be excited next cycle)   (33, 215, 215)
    3. C10 - nadšený (ale v příštím cyklu bude v klidu)   (255, 255, 128)
    4. C11 - vzrušený další vzrušený (aktuálně vzrušený a bude vzrušený další cyklus)   (255, 128, 64)
  4. the obyčejný přenos stavy (ve 4 směrech, vzrušené nebo klidové, 8 stavů)
    1. Směr na sever (vzrušený a klidný)   (36, 200, 36)   (106, 106, 255)
    2. Směr na jih (vzrušený a klidný)   (106, 255, 106)   (139, 139, 255)
    3. Směr na západ (vzrušený a klidný)   (73, 255, 73)   (122, 122, 255)
    4. Orientovaný na východ (vzrušený a klidný)   (27, 176, 27)   (89, 89, 255)
  5. the speciální převodovka stavy (ve 4 směrech, vzrušené nebo klidové, 8 stavů)
    1. Směr na sever (vzrušený a klidný)   (191, 73, 255)   (255, 56, 56)
    2. Směr na jih (vzrušený a klidný)   (203, 106, 255)   (255, 89, 89)
    3. Směr na západ (vzrušený a klidný)   (197, 89, 255)   (255, 73, 73)
    4. Orientovaný na východ (vzrušený a klidný)   (185, 56, 255)   (235, 36, 36)

"Vzrušené" stavy přenášejí data rychlostí jednoho bitu na krok přechodu stavu.

Všimněte si, že konfluentní stavy mají vlastnost zpoždění jednoho cyklu, takže účinně drží dvě bity dat v daném okamžiku.

Pravidla stavu přenosu

Tok bitů mezi buňkami je indikován vlastností direction. Platí následující pravidla:

  • Stavy přenosu aplikují operátor OR na vstupy, což znamená, že buňka ve stavu přenosu (obyčejný nebo speciální) bude v okamžiku vzrušena t + 1 -li žádný vstupů, které na něj ukazují, je v čase vzrušeno t
  • Data procházejí z buňky A v normálním stavu přenosu do sousední buňky B v běžném vysílacím stavu podle vlastnosti směru A (pokud B je také zaměřen na A, v takovém případě data zmizí).
  • Data procházejí z buňky A ve zvláštním stavu přenosu do sousední buňky B ve zvláštním stavu přenosu, podle stejných pravidel jako pro běžné stavy přenosu.
  • Dvě podmnožiny stavů přenosu, obyčejný a speciální, jsou vzájemně nepřátelské:
    • Vzhledem k buňce A v čase t ve vzrušeném běžném stavu přenosu
    • ukázal na buňku B v jakémkoli zvláštním stavu přenosu
    • v čase t + 1 buňka B se stane základním stavem. Speciální přenosová buňka byla „zničena“.
    • podobná sekvence nastane v případě buňky ve zvláštním stavu přenosu „směřující“ k buňce v normálním stavu přenosu

Soutěžní státní pravidla

Pro konkrétní státy platí následující zvláštní pravidla:

  • Konfluentní státy mezi sebou nepředávají data.
  • Konfluentní stavy přijímají vstup z jednoho nebo více běžných přenosových stavů a ​​dodávají výstup do přenosových stavů, běžných i speciálních, které nejsou směrovány do konfluentního stavu.
  • Data se nepřenášejí proti vlastnosti směru stavu přenosu.
  • Data uchovávaná konfluentním stavem jsou ztracena, pokud tento stát nemá sousední stav přenosu, který také není namířen na konfluentní stav.
  • Buňky konfluentního stavu se tedy používají jako „můstky“ z přenosových vedení obyčejných do speciálních přenosových stavových buněk.
  • Konfluentní stav aplikuje operátor AND na vstupy, pouze „uloží“ vzrušený vstup, pokud jsou vzrušeny všechny potenciální vstupy současně.
  • Konfluentní buňky zpožďují signály o jednu generaci více než OTS buňky; to je nutné kvůli parita omezení.

Stavební pravidla

Devět typů buněk, které lze zkonstruovat v CA von Neumanna. Zde binární signály procházejí devíti běžnými přenosovými linkami a vytvářejí novou buňku, když se na konci setkají se základním stavem. Například binární řetězec 1011 je zobrazen na pátém řádku a vytváří speciální stav přenosu orientovaný na východ - jedná se o stejný proces, jaký se používá v automatu v horní části této stránky. Všimněte si, že neexistuje žádná interakce mezi sousedními dráty, na rozdíl od v Drátový svět například umožňující kompaktní balení komponent.

Zpočátku je velká část buněčného prostoru, vesmíru buněčného automatu, „prázdná“, skládající se z buněk v základním stavu U. Když je dáno vstupní buzení ze sousedního běžného nebo zvláštního vysílacího stavu, buňka v základním stavu se stane „senzibilizovanou“, která bude procházet řadou stavů, než bude konečně „odpočívat“ v klidovém stavu přenosu nebo konfluentního stavu.

Volba, do kterého cílového stavu buňka dosáhne, je určena posloupností vstupních signálů. Proto lze přechodové / senzibilizované stavy považovat za uzly a rozdvojení strom vedoucí ze základního stavu do každého z klidového přenosu a konfluentních stavů.

V následujícím stromu se posloupnost vstupů po každém kroku zobrazí jako binární řetězec:

  • buňka v základním stavu U, po zadání, přejde na S (nově senzibilizovaný) stav v příštím cyklu (1)
  • buňka v S stát, bez zadání, přejde do S0 stav (10)
    • buňka v S0 stát, bez zadání, přejde do S00 stav (100)
      • buňka v S00 stát, bez zadání, přejde do S000 stav (1000)
        • buňka v S000 stav, vzhledem k tomu, že není zadán žádný vstup, přejde do normálního stavu přenosu orientovaného na východ (10 000)
        • buňka v S000 stát, po zadání vstupu, přejde do normálního stavu přenosu na sever (10001)
      • buňka v S00 stav, po zadání vstupu, přejde do západního normálního stavu přenosu (1001)
    • buňka v S0 stát, po zadání vstupu, přejde do S01 stát (101)
      • buňka v S01 stav, vzhledem k tomu, že není zadán žádný vstup, přejde do běžného stavu přenosu na jih (1010)
      • buňka v S01 stát, po zadání vstupu, přejde do východního zvláštního stavu přenosu (1011)
  • buňka v S stát, po zadání vstupu, přejde do S1 stát (11)
    • buňka v S1 stát, bez zadání, přejde do S10 stát (110)
      • buňka v S10 stát, vzhledem k tomu, že není zadán žádný údaj, přejde do severního zvláštního stavu přenosu (1100)
      • buňka v S10 stát, po zadání vstupu, přejde do západního zvláštního stavu přenosu (1101)
    • buňka v S1 stát, po zadání vstupu, přejde do S11 stát (111)
      • buňka v S11 stav, bez zadání, přejde do stavu zvláštního přenosu na jih (1110)
      • buňka v S11 state, daný vstup, přejde do klidového konfluentního stavu C00 (1111)

Všimněte si, že:

  • jeden další vstupní cyklus (čtyři po počáteční senzibilizaci) je zapotřebí k vytvoření normálního vysílacího stavu na východ nebo na sever než kterýkoli z ostatních států (které vyžadují tři vstupní cykly po počáteční senzibilizaci),
  • "výchozí" klidový stav, jehož výsledkem je konstrukce, je normální směr přenosu na východ - který vyžaduje počáteční vstup senzibilizace a poté čtyři cykly bez vstupu.

Pravidla ničení

Zhruba 4 000 bitů dat ve svinuté „pásce“ vytvářející složitý vzor. Používá se 32stupňová variace celulárních automatů von Neumann známých jako Hutton32.
  • Vstup do buňky konfluentního stavu z buňky speciálního přenosu způsobí, že buňka konfluentního stavu bude redukována zpět do základního stavu.
  • Podobně bude mít vstup do buňky běžného stavu přenosu z buňky stavu zvláštního přenosu výsledek toho, že buňka stavu normálního přenosu bude snížena zpět do základního stavu.
  • Naopak vstup do speciální buňky stavu přenosu z buňky stavu běžného přenosu povede k tomu, že buňka stavu zvláštního přenosu bude snížena zpět do základního stavu.

Viz také

Reference

  • Von Neumann, J. a A. W. Burks (1966). Teorie samoreprodukčních automatů. Urbana, University of Illinois Press. [1]

externí odkazy