Von Neumann géppuska

A von Neumann cellás automata  egy cellás automata , amelyet Neumann János fejlesztett ki Stanisław Ulam segítségével, hogy megvizsgálja az önreplikáló gépek létrehozásának lehetőségét .

Definíció

Konfiguráció

Általában a cellás automata véges automaták rendezett halmaza, amelyek információt cserélnek a szomszédos automatákkal. Egy von Neumann sejtautomatában a sejtek egy kétdimenziós téglalap alakú rácsban vannak elrendezve, és kölcsönhatásba lépnek négy közvetlenül szomszédos sejttel, amelyek egy von Neumann szomszédságot alkotnak . Feltételezzük, hogy a rács mindkét irányban végtelen méretű, és a cellák az átmenet szabályait tekintve azonosak. Az összes sejt állapotának változása szinkronban történik.

Államok

A Neumann-tér minden állapotgépe 29 állapot egyikét veheti fel:

1. alapállapot U
2. tranzitív (vagy érzékeny) állapotok
   1. S
   2. S0_ _
   3. S00_ _
   4. S01_ _
   5. S000_ _
   6. S1_ _
   7. S 10
   8. S 11
3. összefolyó államok
   1. C00_ _
   2. C 10
   3. C01_ _
   4. C 11
4. normál átviteli állapot
   1. T 00 jobbra
   2. T 01 fel
   3. T 02 maradt
   4. T 03 le
5. speciális átviteli állapot
   1. T 10 jobb
   2. T 11 felfelé
   3. T 12 maradt
   4. T 13 le

Az átviteli állapotok mindegyikére (8 állapot) is jellemző a gerjesztés/nem gerjesztettség (zöld/kék nyilak), ami összesen 16 átviteli állapotot ad. A gerjesztett állapot órajelenként 1 bit sebességgel továbbítja az adatokat. Az összefolyó állapotok egy ciklus késleltetéssel rendelkeznek, és így 2 bitnyi információt tárolhatnak.

Átviteli állapot átmeneti szabályok

A cellák közötti információáramlást az irányítottsági tulajdonság határozza meg. A következő szabályok érvényesek:

• Az átviteli állapotok egy VAGY operátort alkalmaznak a bemeneti jelekre, azaz egy átviteli állapotban lévő cella (normál vagy speciális) a t+1 órajelen gerjeszt, ha a bemeneti jelek bármelyike ​​a t órajelen gerjesztődik.
• Az állapotok átvitele az átviteli cellák között az iránytulajdonság szerint történik.
• A közönséges és különleges átviteli állapotok „antagonisták”:
  • Ha az A cella a t órajelben normál gerjesztett adóállapotban a B cellára mutat bármilyen speciális adóállapotban, akkor t+1 órajelnél B cella az U alapállapotba kerül . A speciális adóállapot „megsemmisül”.
  • Hasonló esemény következik be, ha egy speciális átviteli állapotban lévő cella egy normál adó cellára mutat.

Összefolyó állapotok átmenetének szabályai

Az összefolyó államokra a következő szabályok vonatkoznak:

• Az összefolyó sejtek nem továbbítanak adatokat egymás között.
• Az összefolyó sejtek egy vagy több normál átviteli cellától fogadják a bemeneteket, és továbbítják azokat az olyan (normál vagy speciális) átviteli celláknak, amelyek nem mutatnak az aktuális cellára.
• Az adatátvitel nem az adó cellával ellentétes irányban történik.
• Az összefolyó cella által tárolt adatok elvesznek, ha nincsenek szomszédos átviteli cellái (nem mutatnak rá).
• Az összefolyó sejtek hidakként szolgálnak a hagyományos és a speciális adósejtek között.
• Az összefolyó cellák az ÉS operátort alkalmazzák a bemeneti jelekre.
• A konfluens sejtek egy ciklussal tovább késleltetik a jelet, mint a hagyományos továbbító sejtek.

Átmeneti szabályok

A kezdeti állapotban a sejttér nagy része "üres", azaz tele van U állapotú cellákkal . Miután bemenő jelet kapott egy adó cellától, az U állapotú szomszédos cella tranzit állapotba kerül, állapotok sorozatán megy keresztül, és az adó vagy konfluens állapotok egyikébe kerül. Ezt a végső állapotot a bemeneti jelek sorrendje határozza meg. Azaz a tranzitállapotok bifurkációs pontoknak tekinthetők az alapállapotból az átvivő és összefolyó állapotok felé vezető úton. A következő szabályokban a bemeneti jelek sorrendjét zárójelben bináris karakterlánc jelzi:

• az U alapállapotú cella, miután kapott egy jelet, S (1) állapotba megy
• Az S állapotú cella jel vétele nélkül S 0 (10) állapotba megy
  • Az S 0 állapotú cella jel vétele nélkül az S 00 (100) állapotba megy
    • Az S 00 cella jel vétele nélkül az S 000 (1000) cellára megy
      • Az S 000 cella jel vétele nélkül a T 00 -ra (10000) megy
      • Az S 000 cella , miután kapott egy jelet, a T 01 -re (10001) megy
    • Az S 00 cella , miután kapott egy jelet, a T 02 (1001) elemre lép
  • Az S 0 cella , miután kapott egy jelet, az S 01 (101) elemre lép
    • Az S 01 cella jel vétele nélkül a T 03 -ra (1010) megy
    • Az S 01 cella , miután kapott egy jelet, a T 10 -re (1011) megy
• Az S cella , miután kapott egy jelet, az S 1 -be megy (11)
  • az S 1 cella jel vétele nélkül az S 10 (110) cellára megy
    • az S 10 cella jel vétele nélkül a T 11 -re (1100) megy
    • Az S 10 cella , miután kapott egy jelet, a T 12 -re (1101) megy
  • Az S 1 cella , miután kapott egy jelet, az S 11 -re (111) megy
    • Az S 11 cella jel vétele nélkül a T 13 -ra (1110) megy
    • Az S 11 cella , miután kapott egy jelet, a C 00 -ra (1111) lép

Szabályok megszegése

• Egy speciális adócellától érkező bemeneti jel, amelyet egy konfluens vagy normál átviteli állapotban lévő cella fogad, a cellát alapállapotba helyezi.
• Egy normál adócellától kapott bemeneti jel, amelyet egy speciális adócella fogad, ezt a cellát alapcellává alakítja.

Módosítások

A von Neumann automata egyik változata a Nobili automata , amelyben további állapotokat vezetnek be a memória és a jelek interferencia nélküli keresztezésének biztosítására, amihez az információ cellacsoportonkénti tárolásának lehetőségét használják. Az utolsó funkcióhoz három további állapot szükséges, ezért a Nobili automatának 32 állapota van, nem 29. Ez Renato Nobili ( olaszul  Renato Nobili ) , a Padovai Egyetem fizikaprofesszorának találmánya . Von Neumann szándékosan kizárta a jelzőátkelőhelyekre szánt állapotokat.

Az összefolyó állapotot úgy változtatjuk meg, hogy két egyidejűleg érkező jelet egymástól függetlenül továbbítson, vagy a bemeneti jeleket késleltetetten tárolja és továbbítsa.

Egy másik változat a Hutton automata , amely lehetővé teszi a gyűrűs struktúrák replikációját (lásd Langton hurkok angolul  ) .

Lásd még

• Von Neumann gép

Linkek

• J. von Neumann, Az önreprodukáló automaták elmélete. M.: Mir, 1971.