Czy automaty wielopłytkowe mogą decydować o wszystkich deterministycznych językach kontekstowych?

MPA (automat multipebble) to 2DFA (dwukierunkowy deterministyczny automat skończony), który może wykorzystywać dowolną liczbę otoczek (w rzeczywistości najwyżej otoczki na danym wejściu - wejście jest zapisywane na taśmie między dwoma końcami -markery jak ). Podczas obliczeń MPA może wykryć, czy symbol pod głową ma kamyk, a następnie może umieścić kamyk (usunąć kamyk), jeśli nie ma kamyka (kamyk).$|w|+2$$w$$\# w \#$

$h_k(\sigma) = \underbrace{\sigma \cdots \sigma}_{k \mbox{ times}} = \sigma^k$ jest homomorfizmem, gdzie jest symbolem, a .$\sigma$$k>0$

Dla każdego deterministycznego języka kontekstowego nietrudno wykazać, że istnieje tak, że może zostać rozpoznany przez MPA. Mówiąc luźno, możemy to powiedzieć$\mathtt{L} ~~ \left( \mathtt{L} \in \mathsf{DSPACE(n)} \right),$$k>0~$$h_k( \mathtt{L} )$

każdy „problem” rozstrzygalny przez DTM w przestrzeni liniowej (deterministyczna maszyna Turinga) może być rozstrzygany przez MPA.

Czy dotyczy to również dowolnego języka w ? Czy MPA mogą decydować o wszystkich deterministycznych językach kontekstowych?$\mathsf{DSPACE(n)}$

$|w|$to długość .$w$

$w_i$ jest symbolem , gdzie.$i^{th}$$w$$1 \leq i \leq |w|$

$h_k(\mathtt{L}) = \left\lbrace h_k(w_1) h_k(w_2) \cdots h_k(w_{|w|}) \mid w \in \mathtt{L} \right\rbrace$ .

Być może możesz zbudować język w DPSACE (n), który nie może być rozpoznany przez MPA z używając argumentu diagonalizacji (prawdopodobnie pomysł jest podobny do tego w odpowiedzi Bena, ale nie zagłębiłem się w to):$k=1$

Załóżmy, że nad alfabetem kodujesz MPA przy użyciu listy przejść:$\Sigma = \{0,1\}$

$s,a,p \rightarrow s',p',L|R;...\#$

gdzie to aktualny stan, to aktualny symbol, to status kamyka, to nowy stan, to nowy stan kamyka, to kierunek ruchu, to znacznik końcowy).$s$$a$$p$$s'$$p'$$L|R$$\#$

Maszyna Turinga na wejściu może sprawdzić, czy jest poprawnym opisem i symulować go na wejściu dla kroków, używając komórki, rozciągając dane wejściowe w ten sposób:$M$$x$$MPA_x$$x$$4^{|x|}$$6|x|+\log|x|$

 MPA description # MPA tape # curr_state # counter #

Gdzie:

• Opis MPA to oryginalny ciąg wejściowy (ma długość );$x$$|x|$
• Taśma MPA jest reprezentacją taśmy MPA: dla każdej komórki możemy użyć 3 bitów do przechowywania flagi głowy, flagi kamyka i (stałej) zawartości taśmy (ma długość );$3|x|$
• curr_state przechowuje bieżący stan MPA (ma długość );$\log |x|$
• counter jest licznikiem kroków symulacji, który jest aktualizowany po każdym kroku symulacji (ma długość ).$2|x|$

Jeśli zatrzymuje się w wówczas TM wypisuje coś przeciwnego (jeśli nie zatrzymuje wyjść 0).$MPA_x$$4^{|x|}$$M$$M$

Dla wystarczająco dużą , gdy etapy symulacji są większe niżktóra jest większa niż długość pełnego opisu konfiguracji ; w ten sposób, jeśli nie zatrzyma się w krokach, jesteśmy pewni, że zapętli się na zawsze.$x > x_0$$4^{|x|}$$2^{|x|+2} |x| \log |x|$$MPA_x$$MPA_x$$4^{|x|}$

Załóżmy, że istnieje który decyduje o tym samym języku z , a następnie zawsze zatrzymuje się i możesz zbudować „większy” który decyduje o tym samym języku, używając (wystarczy dodać stany dum).$MPA_y$$L$$M$$MPA_{y'}$$y'>x_0$

Z konstrukcji mamy, co jest sprzecznością.$MPA_{y'}(y') = 1 - M(y') = 1 - MPA_{y'}(y')$

Nie. Przeciwprzykład: problem zatrzymania MPA jest rozstrzygalny w przestrzeni liniowej: jeśli MPA ma stany N, potrzebujemy | k | +2 bitów miejsca do przechowywania lokalizacji kamyków, log N bitów do przechowywania bieżącego stanu i bity do przechowywania licznika; jeśli licznik cyklów, symulowana maszyna nigdy się nie zatrzyma. Jest to liniowe w | k | (ignorując przestrzeń O (N \ log N) wymaganą do opisu komputera), zgodnie z wymaganiami.$\log(N(|k|+2))+|k|+2$

Ponieważ język ten jest rozstrzygalny w przestrzeni liniowej, można go również wyrazić jako DCSL.