pętle Langtona

Pętla Langtona w konfiguracji początkowej.

Pętle Langtona to szczególny „gatunek” sztucznego życia w automacie komórkowym stworzonym w 1984 roku przez Christophera Langtona . Składają się z pętli komórek zawierających informację genetyczną, która przepływa w sposób ciągły wokół pętli i na zewnątrz wzdłuż „ramienia” (lub pseudonóżki ), które stanie się pętlą potomną. „Geny” instruują go, aby wykonał trzy skręty w lewo, kończąc pętlę, która następnie odłącza się od rodzica.

Historia

W 1952 roku John von Neumann stworzył pierwszy automat komórkowy (CA) w celu stworzenia samoreplikującej się maszyny . Ten automat był z konieczności bardzo złożony ze względu na jego uniwersalność obliczeniową i konstrukcyjną. W 1968 roku Edgar F. Codd zredukował liczbę stanów z 29 w CA von Neumanna do 8 w swoim . Kiedy Christopher Langton zrezygnował z warunku uniwersalności, był w stanie znacznie zmniejszyć złożoność automatu. Jego samoreplikujące się pętle są oparte na jednym z najprostszych elementów automatu Codda, emiterze okresowym.

Specyfikacja

Pętle Langtona działają w CA, który ma 8 stanów i wykorzystuje sąsiedztwo von Neumanna z symetrią obrotową. Tabelę przejść można znaleźć tutaj: [1] .

Podobnie jak w przypadku CA Codda , pętle Langtona składają się z drutów w osłonie. Sygnały przemieszczają się biernie wzdłuż przewodów, aż dotrą do otwartych końców, kiedy wykonywane jest polecenie, które niosą.

Kolonia pętli. Te w środku są "martwe".

Kolonie

Ze względu na szczególną właściwość „pseudopodiów” pętli nie są one w stanie odtworzyć się w przestrzeni zajmowanej przez inną pętlę. Tak więc, gdy pętla zostanie otoczona, nie jest w stanie się rozmnażać, w wyniku czego powstaje koralowa kolonia z cienką warstwą rozmnażających się organizmów otaczających rdzeń nieaktywnych „martwych” organizmów. O ile nie zapewni się nieograniczonej przestrzeni, wielkość kolonii będzie ograniczona. Maksymalna populacja będzie asymptotyczna do ${\ Displaystyle \ textstyle \ lewo \ lfloor {\ Frac {A} {121}} \ prawo \$ rfloor } jest całkowitym polem przestrzeni w komórkach.

Kodowanie genomu

Kod genetyczny pętli jest przechowywany jako seria niezerowych par stanów. Genom standardowej pętli jest przedstawiony na rysunku u góry i można go przedstawić jako serię ponumerowanych stanów, zaczynając od skrzyżowania T i biegnąc zgodnie z ruchem wskazówek zegara: 70-70-70-70-70-70-40-40. Komenda '70' powoduje przesunięcie końca drutu o jedną komórkę, natomiast sekwencja '40-40' powoduje obrót w lewo. Stan 3 jest używany jako tymczasowy znacznik dla kilku etapów.

Podczas gdy role stanów 0,1,2,3,4 i 7 są podobne do CA Codda, pozostałe stany 5 i 6 są używane zamiast tego do pośredniczenia w procesie replikacji pętli. Po zakończeniu pętli stan 5 przesuwa się w kierunku przeciwnym do ruchu wskazówek zegara wzdłuż osłony pętli macierzystej do następnego rogu, powodując utworzenie następnego ramienia w innym kierunku. Stan 6 tymczasowo dołącza do genomu pętli potomnej i inicjalizuje rosnące ramię w następnym rogu, do którego dociera.

Genom jest używany w sumie sześć razy: raz, aby rozszerzyć nibynóżkę do pożądanego miejsca, cztery razy, aby zakończyć pętlę i ponownie, aby przenieść genom do pętli potomnej. Oczywiście zależy to od czterokrotnej symetrii obrotowej pętli; bez niego pętla nie byłaby w stanie pomieścić informacji wymaganych do jej opisania. To samo użycie symetrii do kompresji genomu jest stosowane w wielu wirusach biologicznych , takich jak adenowirus dwudziestościenny .

Porównanie powiązanych pętli CA

CA	liczba stanów	sąsiedztwo	liczba komórek (typowa)	okres replikacji (typowy)
Pętle Langtona (1984): Oryginalna samoodtwarzająca się pętla.	8	von Neumanna	86	151
Pętla Byla (1989): Usuwając wewnętrzną osłonę, Byl zmniejszył rozmiar pętli.	6	von Neumanna	12	25
Pętla Chou-Reggia (1993): Dalsza redukcja pętli poprzez usunięcie wszystkich osłonek.	8	von Neumanna	5	15
Pętla Tempesti (1995): Tempesti dodał możliwości konstrukcyjne do swojej pętli, umożliwiając zapisywanie wzorów wewnątrz pętli po odtworzeniu.	10	Moore'a	148	304
Pętla Perriera (1996): Perrier dodał stos programów i rozszerzalną taśmę danych do pętli Langtona, umożliwiając jej obliczenie wszystkiego, co można obliczyć .	64	von Neumanna	158	235
Pętla SDSR (1998): Po dodaniu dodatkowego stanu rozpuszczania struktury do pętli Langtona, pętla SDSR ma ograniczony czas życia i rozpuszcza się pod koniec swojego cyklu życia. Pozwala to na ciągły wzrost i wymianę pokoleń.	9	von Neumanna	86	151
Evoloop (1999): Rozszerzenie pętli SDSR, Evoloop może wchodzić w interakcje z sąsiednimi pętlami, a także ewoluować . Często największą presją selekcyjną w kolonii Evoloops jest rywalizacja o przestrzeń, a dobór naturalny faworyzuje najmniejszą obecną pętlę funkcjonalną. Dalsze badania wykazały większą złożoność systemu Evoloop niż pierwotnie sądzono.	9	von Neumanna	149	363
Sexyloop (2007): Sexyloop to modyfikacja Evoloop, w której samoreprodukujące się pętle mają zdolność seksu . Dzięki tej zdolności pętle są zdolne do przenoszenia materiału genetycznego do innych pętli. Zwiększa to różnorodność w ewolucji nowych gatunków pętli.	10	von Neumanna	149	363

Zobacz też

Sztuczne życie – Kierunek studiów
Automat komórkowy - model dyskretny badany w informatyce
Christopher Langton – amerykański informatyk
Automat komórkowy Codda - automat komórkowy 2D opracowany przez Edgara F. Codda w 1968 roku
Conway's Game of Life - Dwuwymiarowy automat komórkowy opracowany przez JH Conwaya w 1970 roku
Mrówka Langtona - Dwuwymiarowa maszyna Turinga z wyłaniającym się zachowaniem
Automat komórkowy von Neumanna - Automat komórkowy używany do modelowania uniwersalnej konstrukcji

^ von Neumann, Jan; Burks, Arthur W. (1966). „ Teoria samoodtwarzających się automatów ” . www.walenz.org. Zarchiwizowane od oryginału (zeskanowana książka online) w dniu 05.01.2008 . Źródło 2008-02-29 .
^ Codd, Edgar F. (1968). Automaty komórkowe . Prasa Akademicka, Nowy Jork.
Bibliografia _ „Samopowielanie w automatach komórkowych” (PDF) . Fizyka D. 10 (1–2): 135–144. doi : 10.1016/0167-2789(84)90256-2 . hdl : 2027.42/24968 .
^ J. Byl (1989). „Samopowielanie w małych automatach komórkowych”. Fizyka D. 34 (1–2): 295–299. doi : 10.1016/0167-2789(89)90242-X .
Bibliografia _ SL Armentrout; H.-H. Rozetka; Y.Peng (1993). „Proste systemy, które wykazują samokierującą się replikację”. nauka . 259 (5099): 1282–1287. doi : 10.1126/science.259.5099.1282 . PMID 17732248 .
^ G. Tempesti (1995). „Nowy samoreprodukujący się automat komórkowy zdolny do budowy i obliczeń”. Postępy w sztucznym życiu, Proc. 3. Europejska Konferencja Sztucznego Życia . Grenada, Hiszpania: Notatki z wykładów w sztucznej inteligencji, 929, Springer Verlag, Berlin. s. 555–563. CiteSeerX 10.1.1.48.7578 .
Bibliografia _ Perrier; M. Sipper; J. Zahnda (1996). „W kierunku realnego, samoreprodukującego się uniwersalnego komputera”. Fizyka D. 97 (4): 335–352. CiteSeerX 10.1.1.21.3200 . doi : 10.1016/0167-2789(96)00091-7 .
^ Sayama, Hiroki (1998). „Wprowadzenie rozpadu strukturalnego do samoodtwarzającej się pętli Langtona” . Sztuczne życie VI: Proceedings of the Sixth International Conference on Artificial Life . Los Angeles, Kalifornia: MIT Press. s. 114–122.
^ Sayama, Hiroki (1999). „W kierunku realizacji ewoluującego ekosystemu w automatach komórkowych”. Materiały z IV Międzynarodowego Sympozjum Sztucznego Życia i Robotyki (AROB 4th '99) . Beppu, Oita, Japonia. s. 254–257. CiteSeerX 10.1.1.40.391 .
Bibliografia _ Hiroki Sayama (2004). „Złożona ewolucja genetyczna sztucznych samoreplikatorów w automatach komórkowych” . Złożoność . 10 (2): 33–39. doi : 10.1002/cplx.20060 . Zarchiwizowane od oryginału w dniu 05.01.2013 r.
Bibliografia _ CL Nehaniv (2007). „Sexyloop: samoreprodukcja, ewolucja i płeć w automatach komórkowych”. Pierwsze sympozjum IEEE na temat sztucznego życia (1–5 kwietnia 2007 r., Hawaje, USA) . s. 130–138. hdl : 2299/6711 .

Linki zewnętrzne

Film przedstawiający Chrisa Langtona demonstrującego samoodtwarzające się pętle.
wizualna reprezentacja kilku samoreplikujących się pętli w aplecie Java
Repozytorium tabeli reguł zawiera tabele przejściowe dla wielu wymienionych powyżej urzędów certyfikacji.
Golly - obsługuje Langton's Loops wraz z Game of Life i innymi zestawami reguł.

[TSRA-1] von Neumann, Jan; Burks, Arthur W. (1966). „ Teoria samoodtwarzających się automatów ” . www.walenz.org. Zarchiwizowane od oryginału (zeskanowana książka online) w dniu 05.01.2008 . Źródło 2008-02-29 .

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

[Langton1984-3] Bibliografia _ „Samopowielanie w automatach komórkowych” (PDF) . Fizyka D. 10 (1–2): 135–144. doi : 10.1016/0167-2789(84)90256-2 . hdl : 2027.42/24968 .

[Byl1989-4] J. Byl (1989). „Samopowielanie w małych automatach komórkowych”. Fizyka D. 34 (1–2): 295–299. doi : 10.1016/0167-2789(89)90242-X .

[Reggia1993-5] Bibliografia _ SL Armentrout; H.-H. Rozetka; Y.Peng (1993). „Proste systemy, które wykazują samokierującą się replikację”. nauka . 259 (5099): 1282–1287. doi : 10.1126/science.259.5099.1282 . PMID 17732248 .

[Tempesti1995-6] G. Tempesti (1995). „Nowy samoreprodukujący się automat komórkowy zdolny do budowy i obliczeń”. Postępy w sztucznym życiu, Proc. 3. Europejska Konferencja Sztucznego Życia . Grenada, Hiszpania: Notatki z wykładów w sztucznej inteligencji, 929, Springer Verlag, Berlin. s. 555–563. CiteSeerX 10.1.1.48.7578 .

[Perrier1996-7] Bibliografia _ Perrier; M. Sipper; J. Zahnda (1996). „W kierunku realnego, samoreprodukującego się uniwersalnego komputera”. Fizyka D. 97 (4): 335–352. CiteSeerX 10.1.1.21.3200 . doi : 10.1016/0167-2789(96)00091-7 .

[Sayama1998-8] Sayama, Hiroki (1998). „Wprowadzenie rozpadu strukturalnego do samoodtwarzającej się pętli Langtona” . Sztuczne życie VI: Proceedings of the Sixth International Conference on Artificial Life . Los Angeles, Kalifornia: MIT Press. s. 114–122.

[Sayama1999-9] Sayama, Hiroki (1999). „W kierunku realizacji ewoluującego ekosystemu w automatach komórkowych”. Materiały z IV Międzynarodowego Sympozjum Sztucznego Życia i Robotyki (AROB 4th '99) . Beppu, Oita, Japonia. s. 254–257. CiteSeerX 10.1.1.40.391 .

[Salzberg2004-10] Bibliografia _ Hiroki Sayama (2004). „Złożona ewolucja genetyczna sztucznych samoreplikatorów w automatach komórkowych” . Złożoność . 10 (2): 33–39. doi : 10.1002/cplx.20060 . Zarchiwizowane od oryginału w dniu 05.01.2013 r.

[Oros2007-11] Bibliografia _ CL Nehaniv (2007). „Sexyloop: samoreprodukcja, ewolucja i płeć w automatach komórkowych”. Pierwsze sympozjum IEEE na temat sztucznego życia (1–5 kwietnia 2007 r., Hawaje, USA) . s. 130–138. hdl : 2299/6711 .