Von Neumann rynnäkkökivääri

Von Neumann -soluautomaatti  on soluautomaatti , jonka John von Neumann on kehittänyt Stanisław Ulamin avustuksella tutkiakseen mahdollisuutta luoda itseään replikoivia koneita .

Määritelmä

Kokoonpano

Yleensä solukkoautomaatti on määrätty joukko äärellisiä automaatteja , jotka vaihtavat tietoa viereisten automaattien kanssa. Von Neumann-soluautomaatissa solut on järjestetty kaksiulotteiseen suorakaiteen muotoiseen hilaan ja ne ovat vuorovaikutuksessa neljän suoraan vierekkäisen solun kanssa muodostaen von Neumannin naapuruston . Ruudukon oletetaan olevan äärettömän kokoinen molempiin suuntiin, ja solut ovat identtisiä siirtymäsääntöjen suhteen. Kaikkien solujen tilojen muutos tapahtuu synkronisesti.

Osavaltiot

Jokainen tilakone Neumannin avaruudessa voi ottaa yhden 29 tilasta:

1. perustila U
2. transitiiviset (tai herkät) tilat
   1. S
   2. S0 _
   3. S00 _
   4. S01 _
   5. S000 _
   6. S1_ _
   7. S 10
   8. S 11
3. yhtyviä valtioita
   1. C00 _
   2. C 10
   3. C01 _
   4. C 11
4. normaali lähetystila
   1. T 00 oikein
   2. T 01 ylös
   3. T 02 jäljellä
   4. T 03 alas
5. erityinen lähetystila
   1. T 10 oikein
   2. T 11 ylös
   3. T 12 jäljellä
   4. T 13 alas

Jokaiselle lähetystilalle (8 tilaa) on myös tunnusomaista jännitys/ei-viritys (vihreät/siniset nuolet), mikä antaa yhteensä 16 lähetystilaa. Herätetty tila siirtää dataa nopeudella 1 bitti kelloa kohden. Konfluenteilla tiloilla on yhden syklin viive, ja siten ne voivat tallentaa 2 bittiä tietoa.

Siirtotilan siirtymäsäännöt

Tiedonkulku solujen välillä määräytyy suuntausominaisuuden mukaan. Seuraavat säännöt ovat voimassa:

• Lähetystilat käyttävät OR-operaattoria tulosignaaleihin, eli lähetystilassa (normaali tai erityinen) oleva solu virittyy kellolla t+1 , jos jokin tulosignaaleista viritetään kellolla t
• Tilat siirretään lähettävien solujen välillä suuntaomaisuuden mukaan.
• Tavalliset ja erityiset lähetystilat ovat "antagonisteja":
  • Jos solu A kellolla t normaalissa viritetyssä lähetystilassa osoittaa soluun B missä tahansa erityisessä lähetystilassa, niin kellolla t+1 solu B siirtyy perustilaan U. Erityinen lähetystila "tuhoaa".
  • Samanlainen tapahtuma tapahtuu, jos erityisessä lähetystilassa oleva solu osoittaa normaaliin lähettävään soluun.

Konfluenttien tilojen siirtymisen säännöt

Seuraavia sääntöjä sovelletaan yhteenliittyviin valtioihin:

• Konfluentit solut eivät siirrä tietoja keskenään.
• Konfluentit solut vastaanottavat syötteitä yhdestä tai useammasta normaalista lähettävästä solusta ja toimittavat ne lähettäville soluille (tavallisille tai erityisille), jotka eivät osoita nykyiseen soluun.
• Dataa ei lähetetä lähettävän solun vastakkaiseen suuntaan.
• Konfluentin solun tallentamat tiedot menetetään, jos sillä ei ole vierekkäisiä lähettäviä soluja (ei osoita siihen).
• Konfluentit solut toimivat siltoina tavanomaisten ja erikoisten lähetinsolujen välillä.
• Konfluentit solut käyttävät AND-operaattoria tulosignaaleihin.
• Konfluentit solut viivästävät signaalia yhden syklin pidempään kuin perinteiset lähettävät solut.

Siirtymäsäännöt

Alkutilassa suurin osa solutilasta on "tyhjää" eli täynnä U -tilassa olevia soluja . Vastaanotettuaan tulosignaalin lähettävältä solulta, naapurisolu tilassa U siirtyy siirtotilaan, käy läpi sarjan tiloja ja päätyy johonkin lähettävästä tai konfluenttitilasta. Tämä lopullinen tila määräytyy tulosignaalien sekvenssin mukaan. Toisin sanoen kauttakulkutiloja voidaan pitää haaroittumispisteinä matkalla perustilasta lähettävään ja konfluenttiin. Seuraavissa säännöissä tulosignaalien järjestys on merkitty suluissa binäärimerkkijonolla:

• solu perustilassa U , vastaanotettuaan signaalin, menee tilaan S (1)
• solu tilassa S , vastaanottamatta signaalia, siirtyy tilaan S 0 (10)
  • solu tilassa S 0 , vastaanottamatta signaalia, siirtyy kohtaan S 00 (100)
    • solu S 00 siirtyy vastaanottamatta signaalia S 000 (1000)
      • solu S 000 siirtyy vastaanottamatta signaalia T 00 : een (10 000)
      • solu S 000 , vastaanotettuaan signaalin, siirtyy T 01 : een (10001)
    • solu S 00 , vastaanotettuaan signaalin, siirtyy T 02 : een (1001)
  • solu S 0 , vastaanotettuaan signaalin, siirtyy S 01 :een (101)
    • solu S 01 siirtyy vastaanottamatta signaalia T 03 : een (1010)
    • solu S 01 , vastaanotettuaan signaalin, siirtyy T 10 : een (1011)
• solu S , vastaanotettuaan signaalin, siirtyy S 1 :een (11)
  • solu S1 siirtyy vastaanottamatta signaalia S 10 : een (110)
    • solu S 10 siirtyy vastaanottamatta signaalia T 11 : een (1100)
    • solu S 10 , vastaanotettuaan signaalin, siirtyy T 12 : een (1101)
  • solu S1 , vastaanotettuaan signaalin, siirtyy S 11 :een ( 111 )
    • solu S 11 siirtyy vastaanottamatta signaalia T 13 : een (1110)
    • solu S11 , vastaanotettuaan signaalin, siirtyy C 00 :een ( 1111)

Sääntöjen rikkominen

• Tulosignaali erityisestä lähettävästä solusta, jonka solu vastaanottaa konfluentissa tai normaalissa lähetystilassa, asettaa solun perustilaan.
• Erityisen lähettävän solun vastaanottama normaalin lähettävän solun tulosignaali muuntaa solun kantasoluksi.

Muutokset

Yksi von Neumannin automaatin lajikkeista on Nobili-automaatti , jossa lisätiloja tuodaan muistin ja signaalien ylittämisen ilman häiriöitä varten, jolloin käytetään mahdollisuutta tallentaa tietoa soluryhmittäin. Viimeinen toiminto vaatii kolme lisätilaa, minkä vuoksi Nobili-automaatissa on 32 tilaa, ei 29. Se on Italian Padovan yliopiston fysiikan professorin Renato Nobilin ( italiaksi  Renato Nobili ) keksintö . Von Neumann sulki tietoisesti pois tilat, jotka oli tarkoitettu opasteristeyksiin.

Konfluenttitilaa muutetaan siten, että se lähettää kaksi samanaikaisesti saapuvaa signaalia toisistaan ​​riippumatta tai tallentaa ja lähettää tulosignaaleja viiveellä.

Toinen muunnelma on Hutton - automaatti , joka mahdollistaa rengasrakenteiden replikoinnin (katso Langtonin silmukat englanniksi  ) .

Katso myös

• Von Neumann kone

Linkit

• J. von Neumann, Itseään toistuvien automaattien teoria. M.: Mir, 1971.