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

10

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×NA , gdzie A jest alfabetem.

Definicja. Automat komórkowy zatrzymał się w konfiguracji f(w,i) , jeśli kN 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 , 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 , 10000010011 , 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.1001

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.2n

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 00001000200xyx00y00210010 ?

Oto, co wymyśliłem:

rozważmy wszystkie kombinacje takich zasad:

  1. i 002 000100020
  2. i 002 100100021
  3. i 002 200100022
  4. i 002 000110020
  5. i 002 100110021
  6. i 002 200110022
  7. i 002 000120020
  8. i 002 100120021
  9. i 002 200120022

Nie napisałem przypadków dla reguł formy , ponieważ są one symetryczne.x00y

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).00100022222

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 | /w101000110012020022|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 23n2 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 100100021 .

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 y122s101xy .

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 223n2 .

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?

Pavel
źródło
2
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu . Jeśli coś wyniknie z tej dyskusji, edytuj pytanie, aby uwzględnić nowe informacje lub wyjaśnienia. Nie dodawaj znaków „EDYTUJ:”, upewnij się, że nowicjusz zrozumie pytanie bez konieczności przeszukiwania historii.
Gilles „SO- przestań być zły”

Odpowiedzi:

1

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,xp,y,L

2) q,xp,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.xqxyp

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 qARQΣ=AQ{q|qrR,r=p,xq,y,L}q, takie, że istnieje reguła uwzględnimy q .p,xq,y,Lq

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...qQqz

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

2) q,zp,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αp,αΣ

αqzy,αΣ

Pierwszy przypadek jest nieco bardziej skomplikowany, mamy:

1) q,zp,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...abqpabq

pierwszy krok:

qzαy,αΣ

αqzp,αΣ

drugi krok:

αβpp,α,βΣ

αpββ,α,βΣ

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

αβγβ,α,β,γΣ

U6,4

wprowadź opis zdjęcia tutaj

qp,xq,y,Lu1,u3,u4,u5,u6

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

Pavel
źródło