Jak spełniona jest reguła 110 Turing?

Przeczytałem stronę wikipedii dla reguły 110 w automatach komórkowych i mniej więcej wiem, jak działają (zestaw reguł decyduje, gdzie narysować następną 1 lub 0).

Właśnie przeczytałem, że Turing jest kompletny, ale nie mogę nawet pojąć, jak byś „zaprogramował” w „regule 110”?

computability automata turing-completeness cellular-automata Pureferret
źródło

W rzeczywistości jest to reguła 110, a nie reguła 101. Dowód jest nakreślony na stronie wikipedii, choć wyraźnie widać, w jaki sposób tekst łączy się z dowodem.

@WolfgangBangerth dzięki za to, naprawiłem to. Jeśli jest tam dowód / sposób programowania, przepraszam, że nie jest to wystarczająco oczywiste.

Pureferret

To samo pytanie przyszło mi też do głowy, jeśli istnieje skrypt do konwersji prostego programu na te automaty, a następnie jakiś „symulator” do jego wykonania.

doskonałe pytanie. szczegóły są złożone i zawarte w pracach naukowych. szkic tcs.SE, warunki początkowe dla reguły 110 dla szkicu i niektóre odnośniki. Zasadniczo istnieje sposób na konwersję lub kompilację bazy TM na „system tagów” (znany jako „zupełny TM”), a następnie skompilowanie „systemu tagów” do reguły 110. Byłoby „całkiem fajne”, gdyby zbudowano rzeczywiste implementacje dla ppl do eksperymentowania (i z pewnością prowadzą do nowych wglądów / odkryć), ale niestety, wydaje się, że nie istnieje, lub autorzy nie publikują swojego kodu.

vzn

ściśle powiązane są automaty komórkowe 2d i można je badać pod kątem intuicji w przypadku 1d. wiadomo było od lat 70. XX wieku dzięki dowodom Conwaya, że „gra życia” dobiega końca. patrz np. symulator Paula Rendella TM w Game of Life, aby uzyskać wersję nowoczesną / graficzną.

vzn

Odpowiedzi:

$f$ $P$ $P$ $x$ zawsze „zatrzymuje się” i „wysyła” poprawną odpowiedź. (Uwaga: maszyny Turinga nie pojawiają się tutaj: są tylko jednym przykładem uniwersalnego modelu obliczeniowego.)

Cytowane słowa to te, które należy zdefiniować. W przypadku maszyn Turinga:

programu jest określony jako lista państw, alfabetem taśmy, stanie początkowym, stanów końcowych, i przejść.
$T$ $x$ $x$ $T$ na tej taśmie zgodnie ze zwykłymi zasadami.
Maszyna Turinga zatrzymuje się, jeśli osiągnie stan końcowy. (Jest tu kilka wariantów).
To, co wyprowadza maszyna Turinga (jeśli się zatrzymuje), to zawartość taśmy.

$S$ $P$ $x$ $S(P,x)$ $P$ $x$ $S(p,x)$ $P$ $x$

Jeśli jesteś ciekawy co do konkretnej konfiguracji Reguły 110 jako systemu komputerowego, proponuję rzucić okiem na artykuł Matthew Cooka, który dowodzi uniwersalności Reguły 110 (a raczej systemu komputerowego zbudowanego wokół Reguły 110).

Co do innych zasad, takich jak Reguła 30 i Reguła 90, nie wiemy, że nie są one uniwersalne. Mogą być zbudowane przekonujące systemy komputerowe, które są uniwersalne, ale po prostu nie jesteśmy tego świadomi.

Yuval Filmus
źródło

Wszystko prawda, ale reguła 110 nie ma sposobu na zatrzymanie się. Może tylko obliczyć rzeczy, ale się nie zatrzymać.

Pavel

@Pavel Nie jest konieczne zatrzymywanie się na ukończenie Turinga

MilkyWay90

Z dowodu Matthew:

Podejście przyjęte tutaj nie polega na zaprojektowaniu nowego automatu komórkowego, ale na przyjęciu najprostszego, który naturalnie wykazuje złożone zachowanie, i sprawdzeniu, czy możemy znaleźć w obrębie tego złożonego zachowania sposób, aby zrobić to, co chcemy. Nie będziemy się bezpośrednio zajmować tabelą odnośników podaną powyżej, ale zamiast tego przyjrzymy się zachowaniu, które naturalnie przejawia się w czasie działania automatu.

Autor zaczyna od udowodnienia, że „system znaczników”, który usuwa 2 symbole na każdym etapie, jest uniwersalny, kompilując 2-stanowy program maszyny Turinga. Następnie udowadnia, że system szybowców może rzeczywiście zaimplementować system znaczników. Jest to proces krok po kroku. Następnie bada czasoprzestrzeń CA-110, aby znaleźć szybowce i prawidłowo powiązać je z systemem szybowców.

A teraz pytanie: jak „zaprogramowałbyś” regułę 110?

Poszukaj najprostszej 2-stanowej maszyny Turinga i znajdź taśmy podstawowych operacji LUB, AND, XOR, NOT .
Skompiluj je do systemu tagów.
Skompiluj implementację systemu znaczników w implementacji szybowca.
Dostosuj go poprawnie do szybowców CA-110, a będziesz mieć podstawowe operacje w automatach komórkowych.

$1+1=2$

Uwaga na bok. Szybowce są bardzo specjalnymi konstrukcjami. Operacje będą postrzegane jako poruszające się i zderzające się cząstki (szybowce), generujące różne dane wyjściowe w zależności od tego, jak te szybowce zaczynają się lub zderzają.

labotsirc
źródło

Więc dwa szybowce mogą „zakodować” znak +, a kiedy się zderzą, dostaję 2?

Pureferret

a dokładniej, wiele par szybowców koduje znak „+”, zakładając, że para szybowców może kodować OR, AND, XOR lub NOT. Weź również pod uwagę, że liczby będą prawdopodobnie reprezentowane jako sekwencja bitów, a suma zostanie wykonana przy użyciu bramek logicznych na każdej parze bitów.

labotsirc

Uwaga, w społeczności CS istnieją pewne kontrowersje dotyczące dowodu kompletności reguły 110 TM z różnych powodów. jeden najwyraźniej jest taki, że warunki wejściowe w urzędzie certyfikacji wymagają nieskończenie okresowych (ale powtarzalnych) wzorców.

vzn

Zgadzam się z tobą w sprawie kontrowersji. Osobiście nie wiem, co myśleć, jeśli chodzi o odrzucenie teoretycznego rozwiązania metodami formalnymi lub zaakceptowanie CA-110 jako nadzbiór, który działa jako maszyna Turinga (fakt, że CA to przestrzenie obliczeniowe, które działają jako systemy dynamiczne i na początek tej pracy równolegle sprawia, że zastanawiam się, czy reprezentują one syntetyczny wszechświat w toku).

labotsirc

Nie przepadam za ignorowaniem faktycznych ograniczeń przestrzeni i czasu. Wikipedia przytacza P-kompletność automatu komórkowego Reguła 110 i wyjaśnia, że Neary i Woods uniknęli gwałtownego narzutu czasu, unikając stosowania systemów 2-znacznikowych. Jednak Neary i Woods później w tym samym roku (2006) wykazali, że nawet systemy 2-znacznikowe nie mają eksponencjalnego czasu na symulację maszyn Turinga.

Thomas Klimpel,