Automat komórkowy Codda

Prosta konfiguracja w automacie komórkowym Codda. Sygnały przechodzą przewodem złożonym z ogniw w stanie 1 (kolor niebieski) osłoniętym ogniwami w stanie 2 (kolor czerwony). Dwa ciągi sygnałów krążą wokół pętli i są powielane w trójniku na otwartym odcinku drutu. Pierwszy (7-0) powoduje odsłonięcie osłoniętego końca drutu. Drugi (6-0) ponownie osłoni odsłonięty koniec, pozostawiając drut o jedną komórkę dłuższy niż poprzednio.

Automat komórkowy Codda to automat komórkowy (CA) opracowany przez brytyjskiego informatyka Edgara F. Codda w 1968 r. Został zaprojektowany w celu odtworzenia uniwersalności obliczeniowej i konstrukcyjnej CA von Neumanna, ale z mniejszą liczbą stanów: 8 zamiast 29. Codd pokazał, że w jego CA można stworzyć samoreprodukującą się maszynę, podobnie jak uniwersalny konstruktor von Neumanna , ale nigdy nie dał pełnej implementacji.

Historia

W latach czterdziestych i pięćdziesiątych John von Neumann postawił następujący problem:

Jaki rodzaj logicznej organizacji jest wystarczający, aby automat mógł się reprodukować?

Był w stanie skonstruować automat komórkowy z 29 stanami, a wraz z nim uniwersalny konstruktor . Codd, opierając się na pracy von Neumanna, znalazł prostszą maszynę z ośmioma stanami. To zmodyfikowało pytanie von Neumanna:

Jaki rodzaj organizacji logicznej jest niezbędny , aby automat mógł się reprodukować?

Trzy lata po pracy Codda Edwin Roger Banks pokazał w swojej rozprawie doktorskiej 4-stanowy CA, który był również zdolny do uniwersalnych obliczeń i konstrukcji, ale ponownie nie zaimplementował samoreprodukującej się maszyny. John Devore w swojej pracy magisterskiej z 1973 roku zmodyfikował zasady Codda, aby znacznie zmniejszyć rozmiar projektu Codda do tego stopnia, że można go było zaimplementować na komputerach tamtych czasów. Jednak taśma z danymi do samodzielnej replikacji była zbyt długa; Oryginalny projekt Devore był później w stanie dokończyć replikację przy użyciu Golly . Christopher Langton dokonał kolejnego ulepszenia automatu komórkowego Codda w 1984 roku, aby stworzyć pętle Langtona , wykazujące samoreplikację ze znacznie mniejszą liczbą komórek niż ta potrzebna do samoreprodukcji w poprzednich regułach, kosztem usunięcia zdolności do uniwersalnych obliczeń i konstrukcji.

Porównanie zestawów reguł CA

CA	liczba stanów	symetrie	uniwersalne obliczeniowo i konstrukcyjne	wielkość samoreprodukującej się maszyny
von Neumanna	29	nic	Tak	130 622 komórek
Codd	8	obroty	Tak	283 126 588 komórek
Pożerać	8	obroty	Tak	94 794 komórek
Banki IV (banki IV automat komórkowy)	2 - 4	obroty i odbicia	Tak	Gdzieś około 100 000 000 000 komórek
pętle Langtona	8	obroty	NIE	86 komórek

Specyfikacja

Ramię konstrukcyjne w CA Codda można przesunąć na miejsce za pomocą poleceń wymienionych w tekście. Tutaj ramię skręca w lewo, potem w prawo, a następnie zapisuje komórkę, po czym cofa się tą samą ścieżką.

CA Codda ma osiem stanów określonych przez sąsiedztwo von Neumanna z symetrią obrotową.

Poniższa tabela przedstawia ciągi sygnałowe potrzebne do wykonania różnych zadań. Niektóre ciągi sygnałowe muszą być oddzielone dwoma spacjami (stan 1) na przewodzie, aby uniknąć zakłóceń, więc ciąg sygnałowy „przedłużenia” użyty na obrazku u góry pojawia się tutaj jako „70116011”.

zamiar	pociąg sygnałowy
rozszerzyć	70116011
rozszerzenie_w lewo	4011401150116011
rozszerz_w prawo	5011501140116011
wycofać	4011501160116011
retract_left	5011601160116011
cofnij_w prawo	4011601160116011
ocena	701160114011501170116011
usuwać	601170114011501160116011
sens	70117011
czapka	40116011
osłona_wstrzykiwania	701150116011
inject_trigger	60117011701160116011

Uniwersalny konstruktor komputerów

Codd zaprojektował samoreplikujący się komputer w automacie komórkowym, oparty na W-maszynie Wanga . Jednak projekt był tak kolosalny, że unikał wdrożenia do 2009 roku, kiedy Tim Hutton skonstruował wyraźną konfigurację. W projekcie Codda było kilka drobnych błędów, więc implementacja Huttona różni się nieco, zarówno pod względem konfiguracji, jak i zestawu reguł.

Zobacz też

^ von Neumann, Jan; Burks, Arthur W. (1966). „ Teoria samoodtwarzających się automatów ” . www.walenz.org. Zarchiwizowane od oryginału w dniu 2008-01-05 . Źródło 2012-01-28 .
^ Codd, Edgar F. (1968). Automaty komórkowe . Prasa Akademicka, Nowy Jork.
^ ^a ^b Banki, Edwin (1971). Przetwarzanie i przesyłanie informacji w automatach komórkowych . Praca doktorska, MIT, Wydział Inżynierii Mechanicznej.
^ Langton, CG (1984). „Samopowielanie w automatach komórkowych” (PDF) . Physica D: Zjawiska nieliniowe . 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). „Samopowielający się komputer Codda” (PDF) . Sztuczne życie . 16 (2): 99–117. doi : 10.1162/artl.2010.16.2.16200 . PMID 20067401 . S2CID 10049331 .
^ „Dowód Rogera Banksa na uniwersalne obliczenia w automatach komórkowych” .

Linki zewnętrzne

Repozytorium tabeli reguł zawiera tabelę przejść dla urzędu certyfikacji Codda .
Golly - obsługuje CA Codda wraz z Game of Life i innymi zestawami reguł.
Pobierz pełną maszynę (13 MB) i więcej szczegółów.
[1] pokazuje więcej na temat Banks IV.

[vonNeumann66-1] von Neumann, Jan; Burks, Arthur W. (1966). „ Teoria samoodtwarzających się automatów ” . www.walenz.org. Zarchiwizowane od oryginału w dniu 2008-01-05 . Źródło 2012-01-28 .

[Codd68-2] Codd, Edgar F. (1968). Automaty komórkowe . Prasa Akademicka, Nowy Jork.

[Banks1971-3] Banki, Edwin (1971). Przetwarzanie i przesyłanie informacji w automatach komórkowych . Praca doktorska, MIT, Wydział Inżynierii Mechanicznej.

[Langton84-4] Langton, CG (1984). „Samopowielanie w automatach komórkowych” (PDF) . Physica D: Zjawiska nieliniowe . 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). „Samopowielający się komputer Codda” (PDF) . Sztuczne życie . 16 (2): 99–117. doi : 10.1162/artl.2010.16.2.16200 . PMID 20067401 . S2CID 10049331 .

[6] „Dowód Rogera Banksa na uniwersalne obliczenia w automatach komórkowych” .