Dlaczego maszyny Turinga liniowo ograniczone są bardziej wydajne niż automaty o stanie skończonym?

Miałem wrażenie, że nasze komputery, będąc skończone, ostatecznie nie są potężniejsze niż (wyjątkowo duże) skończone maszyny stanowe. Jednak maszyny Turinga liniowo ograniczone są również skończone, ale wydaje się, że zwykłe języki są ściśle niewłaściwym podzbiorem języków wrażliwych na kontekst.

Oczywiście czegoś tu brakuje. Co się dzieje?

finite-automata computation-models linear-bounded-automata

— Ben I.
źródło

Odpowiedzi:

Maszyna Turinga ograniczona liniowo jest ograniczona do taśmy, której długość jest funkcją liniową długości wejścia.

Gdyby limit długości był stały, maszyna nie byłaby mocniejsza niż DFA. Jednak DFA nie może rozwinąć większej liczby stanów, aby poradzić sobie z dłuższym wejściem, co w rzeczywistości może zrobić LBTM (przyjmując stan za całą konfigurację maszyny). Zatem LBTM jest ściśle potężniejszy.

— rici
źródło

Jest z tym ciekawy wynik. Każda maszyna Turinga działająca w przestrzeni akceptuje zwykły język.

o (\log \log n)

$o(\log \log n)$

— skankhunt42

@ skankhunt42, dlaczego tak jest?

— Ben I.

@ skankhunt42: Popraw mnie, jeśli się mylę, ale… każda TM działająca w przestrzeń musi działać w czas. Ale nietrudno jest pokazać, że dowolna baza TM działająca w czasie decyduje o języku, który można określić również w czasie . Następnie istnieje pewna stała taka, że pierwsze znaków wejścia określają, czy wejście jest w języku. Ale wtedy język jest oczywiście regularny: wystarczy dołączyć stan dla każdego prefiksu w . Czy coś brakuje? Gdzie jest mój błąd?

k \log \log n

$k \log \log n$

2^{k \log \log n} = 2^{\log (\log^{k} n)} = \log^{k} n

$2^{k \log \log n} = 2^{\log (\log^k n)} = \log^k n$

o (n)

$o(n)$

O (1)

$\mathcal O(1)$

c \in N

$c \in \mathbb N$

c

$c$

⋃_{0 \leq i \leq c} {0, 1}^{i}

$\bigcup_{0 \leq i \leq c} \{ 0, 1 \}^i$

— wchargin 18.04.17

@Choirbean Wymaga dowodu przy użyciu sekwencji krzyżujących. Możesz to sprawdzić tutaj cs.stackexchange.com/questions/7372/… .

— skankhunt42 18.04.17

@wchargin Myślę, że błędem może być twierdzenie, że TM działa w czasie ponieważ musisz uwzględnić pozycję głowy taśmy wejściowej również podczas liczenia liczby konfiguracji. Myślę więc, że TM działa w czasie .

2^{k \log \log n}

$2^{k \log \log n}$

n 2^{k \log \log n}

$n 2^{k \log \log n}$

— skankhunt42

Myślę, że najpierw musimy zrozumieć opis maszyny i rozmiar wejściowy, aby porównanie dotyczyło tylko poprawnych obiektów. Powiedzmy, że N jest rozmiarem wejściowym. Oznacza to, że maszyny będą miały te ograniczenia zasobów.

\begin{array}{lll} Resource & Finite Automata: A & LBTM: M \\ Input Tape Size & O (N) & O (N) \\ Tape Operations & Read Only & Read, Write \\ Tape Movement & Left to right, One pass only & Both directions, No pass limit \\ # of Locations (States) & M & M \\ Input Alphabet & Σ & Σ \\ Acceptance Condition & Reach finite location: ℓ_{f} & Reach finite location: ℓ_{f} \end{array}

$\begin{array}{|l|l|l|} \hline \mbox{Resource} & \mbox{Finite Automata:}\quad \mathcal{A} & \mbox{LBTM:} \quad \mathcal{M}\\ \hline \mbox{Input Tape Size} & O(N) & O(N)\\ \mbox{Tape Operations} & \mbox{Read Only}& \mbox{Read, Write}\\ \mbox{Tape Movement} & \mbox{Left to right, One pass only}& \mbox{Both directions, No pass limit}\\ \mbox{# of Locations (States)} & M & M\\ \mbox{Input Alphabet} & \Sigma & \Sigma\\ \mbox{Acceptance Condition} & \mbox{Reach finite location: }\ell_f & \mbox{Reach finite location: }\ell_f\\ \hline \end{array}$

Teraz tutaj jest bardziej wyrazisty niż . Jest tak po prostu dlatego, że ruch taśmy i ograniczenia są ograniczone dla . $\mathcal{M}$ $\mathcal{A}$ $\mathcal{A}$

Teraz dokonajmy niepoprawnego porównania.

\begin{array}{lll} Resource & Finite Automata: A^{'} & LBTM: M \\ Input Tape Size & O (N) & O (N) \\ Tape Operations & Read Only & Read, Write \\ Tape Movement & Left to right, One pass only & Both directions, No pass limit \\ # of Locations (States) & M \times 2^{N} & M \\ Input Alphabet & Σ & Σ \\ Acceptance Condition & Reach finite location: ℓ_{f}^{'} & Reach finite location: ℓ_{f} \end{array}

$\begin{array}{|l|l|l|} \hline \mbox{Resource} & \mbox{Finite Automata:}\quad \mathcal{A'} & \mbox{LBTM:} \quad \mathcal{M}\\ \hline \mbox{Input Tape Size} & O(N) & O(N)\\ \mbox{Tape Operations} & \mbox{Read Only}& \mbox{Read, Write}\\ \mbox{Tape Movement} & \mbox{Left to right, One pass only}& \mbox{Both directions, No pass limit}\\ \mbox{# of Locations (States)} & M \times 2^N & M\\ \mbox{Input Alphabet} & \Sigma & \Sigma\\ \mbox{Acceptance Condition} & \mbox{Reach finite location: }\ell'_f & \mbox{Reach finite location: }\ell_f\\ \hline \end{array}$

Tutaj i mają tę samą moc ekspresji. Zauważ jednak, że rozmiar zależy od danych wejściowych w sposób wykładniczy. Wcześniej wielkość nie zależą . Oznacza to, że dla każdego wejścia do konieczne będzie wygenerowanie nowego FA, mimo że pozostaje niezmieniony. $\mathcal{A}'$ $\mathcal{M}$ $\mathcal{A}'$ $N$ $\mathcal{A}$ $N$ $\mathcal{M}$ $\mathcal{M}$

— Devendra Bhave
źródło