Czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych automatów komórkowych?

Próbowałem dowiedzieć się, czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych jednowymiarowych automatów komórkowych.

Definicja Niech $f(w,i)$ oznacza konfigurację systemu w kroku czasowym $i$ . Bardziej formalnie $f:A^*\times \mathbb{N} \to A^*$ , gdzie $A$ jest alfabetem.

Definicja. Automat komórkowy zatrzymał się w konfiguracji $f(w,i)$ , jeśli $\forall k\in \mathbb{N}$ mamy to $f(w,i)=f(w,i+k)$ .

Problem zatrzymania dla danego automatu komórkowego jest następujący:

Wejście: skończony wyraz $w$
pytaniu: Czy zatrzymanie automatem w niektórych państwowych $s$ ?

Definiowane są tutaj podstawowe automaty komórkowe (z 2 symbolami) . Skupiam się na tym samym rodzaju automatów celullarnych, tyle że interesuje mnie przypadek CA z 3 symbolami zamiast tylko 2 symbolami.

Odtąd będę oznaczać moje zasady w formie $***\to*$ , co oznacza, że ​​3 sąsiednie symbole tworzą kolejny pod nimi.

Problem zatrzymania jest rozstrzygalny dla elementarnych automatów komórkowych o dwóch symbolach

Użyję $0$ do oznaczenia białej komórki i $1$ do oznaczenia czarnej.

Jeśli mamy reguły , 001 → 1 , $000 \to 1$$001 \to 1$ , wiemy, że automat się nie zatrzyma. Ponieważ przy pierwszej regule, ponieważ nasza siatka jest nieskończona, zawsze będziemy mieć 3 białe komórki, które wygenerują czarną komórkę. Z drugą i trzecią zasadą słowo będzie się rozszerzać na boki, a automat nigdy się nie zatrzyma.$100 \to 1$

W pozostałych przypadkach możemy pozwolić, aby ewoluowała o kroków i sprawdził, czy się zatrzyma. Jeśli się zatrzyma, to ok, zatrzyma się, jeśli nie, to powtórzy pewne kombinacje i utknie w pętli, więc możemy również stwierdzić, że się nie zatrzyma.$2^n$

Co wymyśliłem dla przypadku 3 symboli

Oczywiste jest, że nie zatrzyma się, jeśli będziemy mieli reguły lub 000 → 2 . Ale reguły boczne postaci 00 x → y i x 00 → y są trudniejsze do przeanalizowania, ponieważ co jeśli mamy reguły 002 → 1 i 001 → $000 \to 1$$000 \to 2$$00x \to y$$x00 \to y$$002 \to 1$$001 \to 0$ ?

Oto, co wymyśliłem:

rozważmy wszystkie kombinacje takich zasad:

1. i 002 → $001 \to 0$$002 \to 0$
2. i 002 → $001 \to 0$$002 \to 1$
3. i 002 → $001 \to 0$$002 \to 2$
4. i 002 → $001 \to 1$$002 \to 0$
5. i 002 → $001 \to 1$$002 \to 1$
6. i 002 → $001 \to 1$$002 \to 2$
7. i 002 → $001 \to 2$$002 \to 0$
8. i 002 → $001 \to 2$$002 \to 1$
9. i 002 → $001 \to 2$$002 \to 2$

Nie napisałem przypadków dla reguł formy , ponieważ są one symetryczne.$x00 \to y$

Tak więc w pierwszym przypadku jest oczywiste, że słowo wejściowe nie będzie rozszerzane na boki, ponieważ te reguły symboli bocznych wytwarzają zera.

W przypadkach 5, 6, 8, 9 oczywiste jest, że automat nigdy się nie zatrzyma, ponieważ słowo wejściowe będzie się rozwijało.

Przypadki 2,3,4,7 są bardziej interesujące. Po pierwsze, zwróćmy uwagę, że przypadek 2 jest podobny do przypadku 7, a przypadek 3 jest podobny do przypadku 4. Rozważmy tylko przypadki 2 i 3 dla zwięzłości.

Rozważę najpierw przypadek 3, ponieważ jest łatwiej.

Mamy i 002 → 2 . Oczywiste jest, że jeśli pierwszym lub ostatnim symbolem naszego słowa wejściowego jest 2 , możemy stwierdzić, że automat się nie zatrzyma. Ale jeśli są one „1”, musimy przyjrzeć się większej liczbie elementów, w szczególności przyjrzyjmy się regułom, które mogą zamienić ostatni lub pierwszy symbol na 2 , ponieważ jeśli je mamy, to po ich wytworzeniu 2 , my można stwierdzić, że automat się nie zatrzyma. (słowo będzie rozwijało się na bokach).$001 \to 0$$002 \to 2$$2$$2$$2$

Oto wszystkie kombinacje, które musimy wziąć pod uwagę:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
........... etc

Wyjaśnienie, co się stanie, jeśli mamy pierwszą potrójną z powyższej tabeli

Mamy słowo zapisane na siatce. Pierwszy i ostatni symbol to 1 . Powiedzmy, że mamy reguły 010 → 0 , 011 → 0 , 012 → 0 (pierwszy potrójny) z góry. Wiemy wtedy, że z każdym kolejnym krokiem nasze słowo wejściowe będzie się zmniejszać o 2 symbole, ponieważ reguły te usuwają pierwszy i ostatni symbol, ale jeśli w pewnym momencie otrzymamy 2 , to reguła 002 → 2 spowoduje, że słowo będzie rosło na jedną lub drugą stronę (lub obie), a automat nigdy się nie zatrzyma. Podsumowując, w tym przypadku możemy pozwolić automatowi | w | $w$$1$$010 \to 0$$011 \to 0$$012 \to 0$$2$$002 \to 2$$|w|/2$ kroki, a jeśli słowo stanie się puste, wówczas automat zatrzyma się, jeśli nie, to nie.

Przypadek uogólniony 3

Uogólniłem to i zauważyłem, że możemy po prostu pozwolić automatowi wykonać kroków, a jeśli na którymkolwiek z tych kroków mamy $3^n$$2$ jako pierwszy lub ostatni symbol, to automat się nie zatrzyma. Jeśli tak się nie stanie, a automat nadal się nie zatrzyma, to powtarza pewną konfigurację, więc utknął w pętli i się nie zatrzyma. Jeśli się zatrzyma, to się zatrzyma.

Gdzie utknąłem

Rozważmy teraz przypadek 2.

Mamy zasady i 002 → $001 \to 0$$002 \to 1$ .

I tutaj utknąłem i nie wiem, co robić.

Napisałem również tabelę zasad, które zaczynają się od . Napisałem te out, bo wydawało się, że pierwszą rzeczą, jaką należy analizować, ponieważ nawet jeśli mamy słowo wejściowe z pierwszego lub ostatniego (lub obu) symbolu jako 2 , w następnym kroku te 2 ' s zamieni się w 1 . I będziemy musieli poradzić sobie z zasadami formularza 01 x → $1$$2$$2's$$1$$01x \to y$ .

Oto tabela:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
 0   1   2
 0   2   0
 0   2   1
 0   2   2
 1   0   0
 1   0   1
 1   0   2
 1   1   0
 1   1   1
 1   1   2
 1   2   0
 1   2   1
 1   2   2
 2   0   0
 2   0   1
 2   0   2
 2   1   0
 2   1   1
 2   1   2
 2   2   0
 2   2   1
 2   2   2

Oczywiste jest również, że jeśli spośród naszych 27 zasad mamy potrójną pozycję z tabeli, w której żadna reguła nie wyprowadza wartości , to nie mamy się czym martwić i możemy po prostu pozwolić, aby automat ewoluował przez 3 n kroków, ponieważ wygrał ' t naprawdę się rozwija, ponieważ reguły boczne nie dadzą wyniku $2$$3^n$$2$ .

Ale patrząc na trójki, które mają , tak naprawdę bardzo trudno jest je przeanalizować, a to, czy słowo się rozszerzy, czy też nie, zależy również od słowa wejściowego.$2$

Czy możecie mi powiedzieć, jak to rozwiązać? Nie wydaje mi się, żeby mnie to owijało.

Lub jeśli ten 3-symbolowy automat komórkowy wygląda jak coś, dla którego udowodniono, że problem zatrzymania jest nierozstrzygalny, to jak mogę zredukować to coś do 3-symbolowych automatów komórkowych?

Znalazłem ten artykuł: http://www.dna.caltech.edu/~woods/download/NearyWoodsMCU07.pdf i pokażę, jak udowodnić, że problem zatrzymania jest nierozstrzygalny w przypadku 15-symbolowych automatów komórkowych.

Spójrzmy na typowe instrukcje maszyny Turinga, mamy:

1) $q,x\to p,y,L$

2) $q,x\to p,y,R$

Pierwszy mówi, że jeśli automat zobaczy symbol w stanie q , wówczas zamieniamy x na y , przełączamy się do stanu p i poruszamy się w lewo, drugi mówi to samo, ale porusza się w prawo.$x$$q$$x$$y$$p$

Załóżmy, że alfabet TM jest , zbiór zasad jest R i zbiór stanów jest Q . Teraz stwórzmy nowy alfabet dla naszego automatu komórkowego, będzie on następujący: Σ = A ⋃ Q ⋃ { q ′ | ∀ q ∃ r ∈ R , r = p , x → q , y , L } . Innymi słowy, w nowym alfabecie uwzględnimy alfabet TM, alfabet stanu TM i dla każdego stanu q$A$$R$$Q$$\Sigma=A\bigcup Q\bigcup \{q'|\forall q \exists r\in R, r=p,x\to q,y,L\}$$q$, takie, że istnieje reguła uwzględnimy q ′ .$p,x\to q,y,L$$q'$

Automat zamodeluje TM w następujący sposób: na każdym etapie działania CA będziemy mieli jeden symbol z alfabetu stanu TM na taśmie CA, a ten symbol będzie wskazywał na symbol, na który wskazywałaby głowa TM, w w następujący sposób: symbol znajdujący się po prawej stronie symbolu stanu jest symbolem wskazywanym przez głowę TM. Jako przykład rozważ ciąg , powiedzmy, że q ∈ Q , wówczas TM jest w stanie q , a głowa wskazuje na symbol z .$s=...xabqzyk...$$q\in Q$$q$$z$

Zobaczmy, jak możemy symulować działanie bazy TM. Rozważmy najpierw drugi:

2) $q,z\to p,y,R$

Zasadniczo, jeśli mamy ciąg , należy go przekonwertować na . . . x a b y p y k . . . . Co można bardzo łatwo osiągnąć, dodając do automatu następujące reguły:$s=...xabqzyk...$$...xabypyk...$

$qz\alpha\to p, \forall \alpha \in \Sigma$

$\alpha qz\to y, \forall \alpha \in \Sigma$

Pierwszy przypadek jest nieco bardziej skomplikowany, mamy:

1) $q,z\to p,y,L$

Więc ciąg należy przekształcić w . . . x a p b y y k . . . , Ale nie jest to sposób, aby zrobić to b q → p bo przeprowadzić operację TM patrząc na stan i symbol, ale b q nie mówi nam o symbolu, jedynego państwa, więc będziemy wykonywać ten lewy ruch w 2 kroki:$s=...xabqzyk...$$...xapbyyk...$$abq\to p$$abq$

pierwszy krok:

$qz\alpha\to y, \forall \alpha \in \Sigma$

$\alpha qz\to p', \forall \alpha \in \Sigma$

drugi krok:

$\alpha \beta p'\to p, \forall \alpha, \beta \in \Sigma$

$\alpha p' \beta\to \beta, \forall \alpha, \beta \in \Sigma$

Jeśli chodzi o wszystkie pozostałe reguły CA, dla których nie ma reguły w TM, napiszemy:

$\alpha \beta \gamma \to \beta, \forall \alpha,\beta,\gamma \in \Sigma$

$U_{6,4}$

$q'$$p,x\to q,y,L$$u_1, u_3, u_4, u_5, u_6$

Tak więc teraz jest przerwa między 2 a 15 symbolami (wyłączne), o której nie wiemy.