Von Neumann kampgevær

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. oktober 2021; checks kræver 2 redigeringer .

Von Neumann -celleautomaten  er en cellulær automat udviklet af John von Neumann med bistand fra Stanisław Ulam for at undersøge muligheden for at skabe selvreplikerende maskiner .

Definition

Konfiguration

Generelt er en cellulær automat et ordnet sæt af endelige automater , der udveksler information med naboautomater. I en von Neumann cellulær automat, er celler ordnet i et todimensionalt rektangulært gitter og interagerer med fire direkte tilstødende celler, der danner et von Neumann-kvarter . Gitteret antages at være af uendelig størrelse i begge retninger, og cellerne er identiske med hensyn til overgangsregler. Ændringen i alle cellers tilstande sker synkront.

Stater

Hver statsmaskine i von Neumann-rummet kan tage en af ​​29 tilstande:

1. basistilstand U
2. transitive (eller følsomme) tilstande
   1. S
   2. S0 _
   3. S00 _
   4. S01 _
   5. S000 _
   6. S1 _
   7. S 10
   8. S 11
3. sammenflydende stater
   1. C00 _
   2. C 10
   3. C01 _
   4. C 11
4. normal sendetilstand
   1. T 00 højre
   2. T 01 op
   3. T 02 tilbage
   4. T 03 nede
5. særlig transmissionstilstand
   1. T 10 højre
   2. T 11 op
   3. T 12 tilbage
   4. T 13 nede

Hver af de transmitterende tilstande (8 tilstande) er også karakteriseret ved excitation/ikke-excitation (grønne/blå pile), hvilket giver i alt 16 sendetilstande. Den exciterede tilstand overfører data med en hastighed på 1 bit pr. ur. Sammenflydende tilstande har en forsinkelse på en cyklus og kan således lagre 2 informationsbits.

Overførselsregler for overgangstilstand

Informationsstrømmen mellem celler bestemmes af retningsbestemt egenskab. Følgende regler gælder:

• Sendetilstande anvender en OR-operator til inputsignalerne, dvs. en celle i en sendetilstand (almindelig eller speciel) vil gå til exciteret ved ur t+1 , hvis nogen af ​​inputsignalerne er exciteret ved ur t
• Tilstande overføres mellem transmitterende celler i henhold til retningsegenskaben.
• Almindelige og specielle sendetilstande er "antagonister":
  • Hvis celle A ved ur t i den normale exciterede sendetilstand peger på celle B i en speciel sendetilstand, så vil celle B ved ur t+1 gå til basistilstanden U. Den særlige sendetilstand vil blive "ødelagt".
  • En lignende hændelse vil opstå, hvis en celle i en speciel sendetilstand peger på en normal sendecelle.

Regler for overgangen af ​​sammenflydende stater

Følgende regler gælder for sammenflydende stater:

• Sammenflydende celler overfører ikke data mellem sig.
• Sammenflydende celler modtager input fra en eller flere normale transmitterende celler og leverer dem til transmitterende celler (almindelige eller specielle), der ikke peger på den aktuelle celle.
• Data transmitteres ikke i den modsatte retning af den transmitterende celle.
• De data, der er lagret af en sammenflydende celle, går tabt, hvis den ikke har nogen tilstødende transmitterende celler (ikke peger på den).
• Sammenflydende celler tjener som broer mellem konventionelle og specialtransmitterceller.
• Sammenflydende celler anvender AND-operatoren til inputsignaler.
• Sammenflydende celler forsinker signalet en cyklus længere end konventionelle transmitterende celler.

Overgangsregler

I den indledende tilstand er det meste af det cellulære rum "tomt", det vil sige fyldt med celler i U -tilstand . Efter at have modtaget et inputsignal fra en transmitterende celle, går en nabocelle i tilstand U ind i en transittilstand, går gennem en række tilstande og ender i en af ​​de transmitterende eller sammenflydende tilstande. Denne endelige tilstand bestemmes af rækkefølgen af ​​indgangssignaler. Det vil sige, at transittilstande kan betragtes som bifurkationspunkter på vej fra basistilstanden til transmitterende og sammenflydende tilstande. I de følgende regler er sekvensen af ​​inputsignaler angivet i parentes med en binær streng:

• cellen i basistilstanden U , efter at have modtaget et signal, går ind i tilstanden S (1)
• celle i tilstand S , uden at modtage et signal, går til tilstand S 0 (10)
  • celle i tilstand S 0 , uden at modtage et signal, går til S 00 (100)
    • celle S 00 , uden at modtage et signal, går til S 000 (1000)
      • celle S 000 , uden at modtage et signal, går til T 00 (10000)
      • celle S 000 , efter at have modtaget et signal, går til T 01 (10001)
    • celle S 00 , efter at have modtaget et signal, går til T 02 (1001)
  • celle S 0 , efter at have modtaget et signal, går til S 01 (101)
    • celle S 01 , uden at modtage et signal, går til T 03 (1010)
    • celle S01 , efter at have modtaget et signal , går til T 10 (1011)
• celle S , efter at have modtaget et signal, går til S 1 (11)
  • celle S 1 , uden at modtage et signal, går til S 10 (110)
    • celle S10 , uden at modtage et signal, går til T 11 (1100 )
    • celle S10 , efter at have modtaget et signal, går til T12 ( 1101 )
  • celle S1 , efter at have modtaget et signal, går til S11 ( 111 )
    • celle S11 , uden at modtage et signal, går til T 13 (1110 )
    • celle S11 , efter at have modtaget et signal , går til C 00 (1111)

At bryde regler

• Et inputsignal fra en speciel transmitterende celle, modtaget af en celle i en sammenflydende eller normal sendetilstand, sætter denne celle i basistilstanden.
• Et inputsignal fra en normal sendecelle modtaget af en speciel sendecelle konverterer denne celle til basiscellen.

Ændringer

En af varianterne af von Neumann -automaten er Nobili-automaten , hvor yderligere tilstande introduceres for at give hukommelse og mulighed for at krydse signaler uden interferens, hvortil muligheden for at lagre information efter grupper af celler bruges. Den sidste funktion kræver tre yderligere tilstande, hvilket er grunden til, at Nobili-automaten har 32 tilstande, ikke 29. Det er opfindelsen af ​​Renato Nobili ( italiensk:  Renato Nobili ), professor i fysik ved University of Padua , Italien . Von Neumann udelukkede bevidst stater beregnet til signalovergange.

Den sammenflydende tilstand ændres på en sådan måde, at der transmitteres to samtidigt ankommende signaler uafhængigt af hinanden, eller for at lagre og transmittere indgangssignaler med en forsinkelse.

En anden variation er Hutton - automaten , som tillader replikering af ringstrukturer (se Langtons sløjfer på engelsk  ) .

Se også

• Von Neumann maskine

Links

• J. von Neumann, Teori om selvreproducerende automater. M.: Mir, 1971.

Conways Game of Life og andre cellulære automater
Konfigurationsklasser	Oscillator Rive Stilleben Rumskib Pistol Lokomotiv fortærer Refleks opdrætter Lang levetid Pladsholder Edens Have
Konfigurationer	Svævefly Blok R-pentomino Pentadecatlon
Vilkår	Moore kvarter Von Neumann-kvarteret lysets hastighed
Andre rumfartøjer på et todimensionelt gitter	Livsagtig Dag og nat Liv uden død vildt liv frø Andet sandbunke model Von Neumann kampgevær Wireworld Ant Langton Critters Worms of Paterson
Et-dimensionelt rumfartøj	Elementær KA ( Regel 30 Regel 90 Regel 110 Regel 184 ) Shooter-synkroniseringsproblem
Software og algoritmer	Golly Mireks hashlife
KA-forskere	John Horton Conway Bill Gosper Martin Gardner Richard Kenneth Guy Brian Silverman John Wilder Tukey John von Neumann Edward Moore Stephen Wolfram