Próbowałem dowiedzieć się, czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych jednowymiarowych automatów komórkowych.
Definicja Niech oznacza konfigurację systemu w kroku czasowym . Bardziej formalnie , gdzie jest alfabetem.
Definicja. Automat komórkowy zatrzymał się w konfiguracji , jeśli mamy to .
Problem zatrzymania dla danego automatu komórkowego jest następujący:
Wejście: skończony wyraz
pytaniu: Czy zatrzymanie automatem w niektórych państwowych ?
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 , 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ę do oznaczenia białej komórki i do oznaczenia czarnej.
Jeśli mamy reguły , 001 → 1 , 100 , 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.
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.
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 → 0 ?
Oto, co wymyśliłem:
rozważmy wszystkie kombinacje takich zasad:
- i 002 → 0
- i 002 → 1
- i 002 → 2
- i 002 → 0
- i 002 → 1
- i 002 → 2
- i 002 → 0
- i 002 → 1
- i 002 → 2
Nie napisałem przypadków dla reguł formy , ponieważ są one symetryczne.
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).
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 | / 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 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 → 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 → 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 .
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.
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?
Odpowiedzi:
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→p,y,L
2)q,x→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 qA R Q Σ=A⋃Q⋃{q′|∀q∃r∈R,r=p,x→q,y,L} q , takie, że istnieje reguła uwzględnimy q ′ .p,x→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∈Q q z
Zobaczmy, jak możemy symulować działanie bazy TM. Rozważmy najpierw drugi:
2)q,z→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...
Pierwszy przypadek jest nieco bardziej skomplikowany, mamy:
1)q,z→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→p abq
pierwszy krok:
drugi krok:
Jeśli chodzi o wszystkie pozostałe reguły CA, dla których nie ma reguły w TM, napiszemy:
Tak więc teraz jest przerwa między 2 a 15 symbolami (wyłączne), o której nie wiemy.
źródło