Zasada 110 - Rule 110

Reguła 110 automat komórkowy (często nazywany po prostu Artykuł 110 ) stanowi podstawowy automat komórkowy z ciekawym zachowania na granicy między stabilnością i chaosu. Pod tym względem przypomina Conway's Game of Life . Podobnie jak Życie, Reguła 110 jest znana jako zupełna pod względem Turinga . Oznacza to, że w zasadzie każdy program obliczeniowy lub program komputerowy może być symulowany za pomocą tego automatu.

Przykładowe uruchomienie automatu komórkowego reguły 110

Definicja

W elementarnym automacie komórkowym jednowymiarowy wzór zer i jedynek ewoluuje zgodnie z prostym zestawem reguł. To, czy punkt we wzorcu będzie miał wartość 0 czy 1 w nowej generacji, zależy od jego bieżącej wartości, a także od wartości jego dwóch sąsiadów.

Animacja przedstawiająca sposób, w jaki reguły automatu komórkowego 1D określają następną generację przy użyciu reguły 110.

Automat Reguła 110 ma następujący zestaw reguł:

Bieżący wzór 111 110 101 100 011 010 001 000
Nowy stan dla komórki centralnej 0 1 1 0 1 1 1 0

Nazwa „Reguła 110” wywodzi się z faktu, że regułę tę można streścić w sekwencji binarnej 01101110; interpretowana jako liczba binarna , odpowiada wartości dziesiętnej 110.

Historia

W 2004 r. Matthew Cook opublikował dowód na to, że reguła 110 jest zupełna w sensie Turinga , tj. zdolna do uniwersalnych obliczeń , co domyślił się Stephen Wolfram w 1985 r. Cook przedstawił swój dowód na konferencji CA98 Instytutu w Santa Fe przed publikacją książki Wolframa A New Kind of Nauka . Doprowadziło to do afery prawnej opartej na umowie o zachowaniu poufności z Wolfram Research . Wolfram Research przez kilka lat blokował publikację dowodu Cooka.

Ciekawe nieruchomości

Spośród 88 możliwych unikalnych elementarnych automatów komórkowych , Reguła 110 jest jedyną, dla której udowodniono kompletność Turinga, chociaż dowody na kilka podobnych reguł powinny wynikać z prostych wniosków (np. Reguła 124, która jest poziomym odzwierciedleniem Reguły 110). Reguła 110 jest prawdopodobnie najprostszym znanym kompletnym systemem Turinga.

Zasada 110, podobnie jak Gra w życie , pokazuje to, co Wolfram nazywa „ zachowaniem klasy 4 ”, które nie jest ani całkowicie stabilne, ani całkowicie chaotyczne. Zlokalizowane struktury pojawiają się i oddziałują w złożony sposób.

Matthew Cook dowiódł, że Reguła 110 jest w stanie wspierać uniwersalne obliczenia, kolejno emulując systemy znaczników cyklicznych , następnie system dwuznacznikowy , a następnie maszyny Turinga . Ostatni etap ma wykładniczy czas narzutu, ponieważ taśma maszyny Turinga jest zakodowana za pomocą jednoargumentowego systemu liczbowego . Neary i Woods (2006) przedstawili inną konstrukcję, która zastępuje systemy 2-tagowe maszynami Turinga prawoskrętnymi i ma wielomianowy narzut.

Dowód uniwersalności

Matthew Cook przedstawił swój dowód na uniwersalność zasady 110 na konferencji Instytutu w Santa Fe, która odbyła się przed publikacją A New Kind of Science . Wolfram Research twierdził, że ta prezentacja naruszyła umowę Cooka o zachowaniu poufności z jego pracodawcą i uzyskała orzeczenie sądowe wykluczające artykuł Cooka z opublikowanych materiałów konferencyjnych. Istnienie dowodu Cooka stało się jednak znane. Zainteresowanie jego dowodem wynikało nie tyle z jego wyniku, ile z jego metod, a konkretnie z technicznych szczegółów jego budowy. Charakter dowodu Cooka różni się znacznie od omówienia zasady 110 w A New Kind of Science . Od tego czasu Cook napisał artykuł, w którym przedstawił swój kompletny dowód.

Cook udowodnił, że reguła 110 jest uniwersalna (lub kompletna według Turinga), pokazując, że można jej użyć do emulacji innego modelu obliczeniowego, systemu znaczników cyklicznych , o którym wiadomo, że jest uniwersalny. Najpierw wyizolował pewną liczbę statków kosmicznych , samonapędzających się zlokalizowanych wzorców, które można było skonstruować na nieskończenie powtarzającym się wzorcu we wszechświecie Reguły 110. Następnie opracował sposób interakcji kombinacji tych struktur w sposób, który można wykorzystać do obliczeń.

Statki kosmiczne w zasadzie 110

Funkcja maszyny uniwersalnej w Regule 110 wymaga skończonej liczby zlokalizowanych wzorów osadzonych w nieskończenie powtarzającym się wzorze tła. Wzór tła ma szerokość czternastu komórek i powtarza się dokładnie co siedem iteracji. Wzorzec to 00010011011111 .

Trzy zlokalizowane wzory mają szczególne znaczenie w uniwersalnej maszynie Rule 110. Są one pokazane na poniższym obrazku, otoczone powtarzającym się wzorem tła. Skrajna lewa struktura przesuwa się w prawo o dwie komórki i powtarza się co trzy pokolenia. Zawiera sekwencję 0001110111 otoczoną wzorem tła podanym powyżej, jak również dwie różne ewolucje tej sekwencji.

Na rysunkach czas upływa od góry do dołu: górna linia przedstawia stan początkowy, a każda następna linia stan w następnym czasie.

Ca110-struktury2.png

Struktura środkowa przesuwa się w lewo o osiem komórek i powtarza się co trzydzieści pokoleń. Zawiera sekwencję 1001111 otoczoną wzorem tła podanym powyżej, jak również dwadzieścia dziewięć różnych ewolucji tej sekwencji.

Skrajna prawa struktura pozostaje nieruchoma i powtarza się co siedem pokoleń. Zawiera sekwencję 111 otoczoną wzorem tła podanym powyżej, jak również pięć różnych ewolucji tej sekwencji.

Poniżej znajduje się obraz przedstawiający pierwsze dwie struktury przechodzące przez siebie bez interakcji innej niż przez translację (po lewej) i oddziałujące tworząc trzecią strukturę (po prawej).

Ca110-interaction2.png

Istnieje wiele innych statków kosmicznych w zasadzie 110, ale nie są one tak widoczne w dowodzie powszechności.

Budowanie cyklicznego systemu tagów

Maszyna systemu cyklicznych znaczników składa się z trzech głównych elementów:

  • Ciąg danych, który jest nieruchomy;
  • Nieskończenie powtarzająca się seria skończonych reguł produkcji, które zaczynają się od prawej i przesuwają się w lewo;
  • Nieskończenie powtarzająca się seria impulsów zegarowych, które zaczynają się od lewej i przesuwają się w prawo.

Początkowe odstępy między tymi elementami mają ogromne znaczenie. Aby automat komórkowy mógł zaimplementować system znaczników cyklicznych, warunki początkowe automatu muszą być starannie dobrane tak, aby zawarte w nim różne zlokalizowane struktury oddziaływały w wysoce uporządkowany sposób.

Ciąg danych do cyklicznego układu znacznika jest reprezentowana przez szereg powtarzających się struktur stacjonarnych typu przedstawionego powyżej. Różne wielkości odstępów poziomych między tymi strukturami służą do odróżnienia 1 symbolu od 0 symboli. Symbole te reprezentują słowo, na którym działa system znaczników cyklicznych, a pierwszy taki symbol jest niszczony po rozważeniu każdej zasady produkcji. Gdy ten wiodący symbol to 1, nowe symbole są dodawane na końcu ciągu; gdy wynosi 0, nie są dodawane żadne nowe symbole. Mechanizm osiągnięcia tego został opisany poniżej.

Wchodzące z prawej strony to seria poruszających się w lewo struktur typu pokazanego powyżej, oddzielonych różnymi ilościami poziomej przestrzeni. Duża liczba tych struktur jest połączona z różnymi odstępami, aby reprezentować zera i jedynki w regułach produkcji cyklicznego systemu znaczników. Ponieważ zasady produkcji systemu znaczników są znane w momencie tworzenia programu i powtarzają się w nieskończoność, wzorce zer i jedynek w stanie początkowym mogą być reprezentowane przez ciąg nieskończenie powtarzający się. Każda reguła produkcyjna jest oddzielona od następnej inną strukturą zwaną separatorem reguł (lub separatorem bloków ), która przesuwa się w lewo z taką samą szybkością, jak kodowanie reguł produkcyjnych.

Kiedy separator reguł poruszający się w lewo napotka symbol nieruchomy w ciągu danych systemu znaczników cyklicznych, powoduje zniszczenie pierwszego napotkanego symbolu. Jednak jego późniejsze zachowanie różni się w zależności od tego, czy symbol zakodowany przez ciąg był 0 czy 1. Jeśli jest 0, separator reguł zmienia się w nową strukturę, która blokuje przychodzącą regułę produkcji. Ta nowa struktura zostaje zniszczona, gdy napotka kolejny separator reguł.

Z drugiej strony, jeśli symbolem w ciągu jest 1, separator reguł zmienia się w nową strukturę, która dopuszcza przychodzącą regułę produkcji. Chociaż nowa struktura jest ponownie niszczona, gdy napotka kolejny separator reguł, najpierw pozwala na przejście serii struktur w lewo. Struktury te są następnie dołączane do końca ciągu danych systemu znaczników cyklicznych. Ta końcowa transformacja jest dokonywana za pomocą serii nieskończenie powtarzających się, poruszających się w prawo impulsów zegarowych, zgodnie z przedstawionym powyżej wzorcem ruchu w prawo. Impulsy zegarowe przekształcają przychodzące symbole 1 poruszające się w lewo z reguły produkcji na stacjonarne symbole 1 ciągu danych, a przychodzące symbole 0 z reguły produkcji na stacjonarne symbole 0 ciągu danych.

Działa cykliczny system tagów

Cts-diagram.jpg

Powyższy rysunek jest schematycznym diagramem rekonstrukcji systemu znaczników cyklicznych w regule 110.

Zobacz też

Bibliografia

  1. ^ B c Cook (2004) .
  2. ^ Idzie (2002) .
  3. ^ Wolfram 2002 , s. 169, 675-691
  4. ^ Wolfram 2002 , s. 229
  5. ^ Neary i Woods (2006) .
  6. ^ Martinez, Genaro J.; Seck Tuoh Mora, Juan; Chapa, Sergio; Lemaitre, chrześcijanin (kwiecień 2019). „Krótkie notatki i obliczenia historyczne w Meksyku w ciągu 50 lat” . International Journal of Parallel, Emergent and Distributed Systems . 35 : 1–8. arXiv : 1905.07527 . doi : 10.1080/17445760.2019.1608990 . Źródło 2020-04-15 .

Prace cytowane

Dalsza lektura

Linki zewnętrzne