Codds cellulära automat

En enkel konfiguration i Codds cellulära automat. Signaler passerar längs en tråd som är gjord av celler i tillstånd 1 (blå) som täcks av celler i tillstånd 2 (röd). Två signaltåg cirkulerar runt en slinga och dupliceras vid en T-korsning till en sektion med öppen tråd. Den första (7-0) gör att den mantlade änden av tråden exponeras. Den andra (6-0) täcker om den exponerade änden och lämnar tråden en cell längre än tidigare.

Codds cellulära automat är en cellulär automat (CA) utarbetad av den brittiske datavetaren Edgar F. Codd 1968. Den designades för att återskapa beräknings- och konstruktionsuniversaliteten hos von Neumanns CA men med färre tillstånd: 8 istället för 29. Codd visade att det var möjligt att göra en självreproducerande maskin i hans CA, på ett liknande sätt som von Neumanns universella konstruktör , men gav aldrig en fullständig implementering.

Historia

På 1940- och 50-talen ställde John von Neumann följande problem:

Vilken typ av logisk organisation räcker för att en automat ska kunna reproducera sig själv?

Han kunde konstruera en cellulär automat med 29 tillstånd, och med den en universell konstruktor . Codd, som bygger på von Neumanns arbete, hittade en enklare maskin med åtta tillstånd. Detta modifierade von Neumanns fråga:

Vilken typ av logisk organisation krävs för att en automat ska kunna reproducera sig själv?

Tre år efter Codds arbete visade Edwin Roger Banks en 4-stats CA i sin doktorsavhandling som också var kapabel till universell beräkning och konstruktion, men återigen inte implementerade en självreproducerande maskin. John Devore, i sin magisteravhandling från 1973, finjusterade Codds regler för att kraftigt reducera storleken på Codds design, till den grad att den kunde implementeras i den tidens datorer. Databandet för självreplikering var dock för långt; Devores ursprungliga design kunde senare slutföra replikering med Golly . Christopher Langton gjorde ytterligare en justering av Codds cellulära automat 1984 för att skapa Langtons loopar , som uppvisade självreplikering med mycket färre celler än vad som behövs för självreproduktion i tidigare regler, till priset av att ta bort möjligheten till universell beräkning och konstruktion.

Jämförelse av CA-regeluppsättningar

CA	antal stater	symmetrier	beräknings- och konstruktionsuniversell	storlek på självreproducerande maskin
von Neumann	29	ingen	ja	130 622 celler
Codd	8	rotationer	ja	283 126 588 celler
Devore	8	rotationer	ja	94 794 celler
Banks IV (Banks IV Cellular Automaton)	2 - 4	rotationer och reflektioner	ja	Någonstans runt 100 000 000 000 celler
Langtons slingor	8	rotationer	Nej	86 celler

Specifikation

Konstruktionsarmen i Codds CA kan flyttas till position med hjälp av de kommandon som anges i texten. Här svänger armen åt vänster, sedan åt höger, skriver sedan en cell innan den dras tillbaka längs samma väg.

Codds CA har åtta tillstånd som bestäms av ett von Neumann-kvarter med rotationssymmetri.

Tabellen nedan visar de signaltåg som behövs för att utföra olika uppgifter. Vissa av signaltågen måste separeras av två blanksteg (tillstånd 1) på tråden för att undvika störningar, så det "förlänga" signaltåget som används i bilden överst visas här som '70116011'.

syfte	signaltåg
förlänga	70116011
extend_left	4011401150116011
extend_right	5011501140116011
dra tillbaka	4011501160116011
retract_left	5011601160116011
retract_right	4011601160116011
märke	701160114011501170116011
radera	601170114011501160116011
känsla	70117011
keps	40116011
inject_sheath	701150116011
inject_trigger	60117011701160116011

Universell datorkonstruktör

Codd designade en självreplikerande dator i den cellulära automaten, baserad på Wangs W-maskin . Designen var dock så kolossal att den undvek implementering fram till 2009, då Tim Hutton konstruerade en explicit konfiguration. Det fanns några mindre fel i Codds design, så Huttons implementering skiljer sig något, både i konfigurationen och regeluppsättningen.

Se även

^ von Neumann, John; Burks, Arthur W. (1966). " Teori om självreproducerande automater. " . www.walenz.org. Arkiverad från originalet 2008-01-05 . Hämtad 2012-01-28 .
^ Codd, Edgar F. (1968). Cellulära automater . Academic Press, New York.
^ ^a ^b Banks, Edwin (1971). Informationsbearbetning och överföring i cellulära automater . Doktorsavhandling, MIT, Institutionen för maskinteknik.
^ Langton, CG (1984). "Självreproduktion i cellulär automat" (PDF) . Physica D: Icke-linjära fenomen . 10 (1–2): 135–144. Bibcode : 1984PhyD...10..135L . doi : 10.1016/0167-2789(84)90256-2 . hdl : 2027.42/24968 .
^ ^a ^b Hutton, Tim J. (2010). "Codds självreplikerande dator" (PDF) . Konstgjort liv . 16 (2): 99–117. doi : 10.1162/artl.2010.16.2.16200 . PMID 20067401 . S2CID 10049331 .
^ "Roger Banks bevis på universell beräkning i cellulära automater" .

externa länkar

Rule Table Repository har övergångstabellen för Codds CA .
Golly - stöder Codds CA tillsammans med Game of Life och andra regeluppsättningar.
Ladda ner hela maskinen (13MB) och mer information.
[1] visar mer om Banks IV.

[vonNeumann66-1] von Neumann, John; Burks, Arthur W. (1966). " Teori om självreproducerande automater. " . www.walenz.org. Arkiverad från originalet 2008-01-05 . Hämtad 2012-01-28 .

[Codd68-2] Codd, Edgar F. (1968). Cellulära automater . Academic Press, New York.

[Banks1971-3] Banks, Edwin (1971). Informationsbearbetning och överföring i cellulära automater . Doktorsavhandling, MIT, Institutionen för maskinteknik.

[Langton84-4] Langton, CG (1984). "Självreproduktion i cellulär automat" (PDF) . Physica D: Icke-linjära fenomen . 10 (1–2): 135–144. Bibcode : 1984PhyD...10..135L . doi : 10.1016/0167-2789(84)90256-2 . hdl : 2027.42/24968 .

[Hutton2010-5] Hutton, Tim J. (2010). "Codds självreplikerande dator" (PDF) . Konstgjort liv . 16 (2): 99–117. doi : 10.1162/artl.2010.16.2.16200 . PMID 20067401 . S2CID 10049331 .

[6] "Roger Banks bevis på universell beräkning i cellulära automater" .