Por que as máquinas de Turing com limite linear são mais poderosas que os autômatos de estados finitos?

Fiquei com a impressão de que nossos computadores, por serem finitos, não são mais poderosos que as máquinas de estado finito (extraordinariamente grandes). Entretanto, as Máquinas de Turing com Limite Linear também são finitas, mas parece que as Linguagens Regulares são estritamente um subconjunto impróprio de Linguagens Sensíveis ao Contexto.

Obviamente, estou perdendo alguma coisa aqui. O que está acontecendo?

finite-automata computation-models linear-bounded-automata Ben I.
fonte

Respostas:

A máquina de Turing delimitada linear é restrita a uma fita cujo comprimento é uma função linear do comprimento da entrada.

Se o limite de comprimento fosse constante, a máquina não seria mais poderosa que um DFA. No entanto, um DFA não pode aumentar mais estados para lidar com uma entrada mais longa, o que de fato o LBTM pode fazer (considerando o estado como sendo a configuração completa da máquina). Portanto, o LBTM é estritamente mais poderoso.

rici
fonte

Há um resultado interessante relacionado a isso. Qualquer máquina de Turing que é executada no espaço aceita um idioma regular.

o (\log \log n)

$o(\log \log n)$

precisa saber é o seguinte

@ skankhunt42, por que isso?

Ben I.

@ skankhunt42: Corrija-me se estiver errado, mas… qualquer TM que seja executada no espaço deve ser executada em tempo. Mas não é difícil mostrar que qualquer TM executada em tempo decide uma linguagem que também pode ser decidida em . Depois, há uma constante modo que os primeiros caracteres da entrada determinam se a entrada está no idioma. Mas a linguagem é obviamente regular: inclua um estado para cada prefixo em . Estou esquecendo de algo? Onde está meu erro?

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

@Choirbean Requer uma prova usando sequências cruzadas. Você pode procurar aqui em cs.stackexchange.com/questions/7372/… .

precisa saber é o seguinte

@wchargin Acho que o erro pode estar alegando que a TM é executada em porque você precisa considerar também a posição da cabeça da fita de entrada enquanto conta o número de configurações. Então, acho que a MT roda no tempo .

2^{k \log \log n}

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

n 2^{k \log \log n}

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

precisa saber é o seguinte

Acho que devemos primeiro entender a descrição de uma máquina e o tamanho da entrada, para que a comparação seja apenas de objetos válidos. Digamos que N é um tamanho de entrada. Isso significa que as máquinas terão esses limites de recursos.

\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}$

Agora, aqui é mais expressivo que . Isso ocorre simplesmente porque o movimento e as restrições da fita são limitados para . $\mathcal{M}$ $\mathcal{A}$ $\mathcal{A}$

Agora vamos fazer uma comparação inválida .

\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}$

Aqui e têm o mesmo poder expressivo. Mas observe que o tamanho de depende da entrada maneira exponencial. Tamanho antes de não dependem . Isso significa que para cada entrada em , você precisará gerar uma nova FA, mesmo que permaneça inalterado. $\mathcal{A}'$ $\mathcal{M}$ $\mathcal{A}'$ $N$ $\mathcal{A}$ $N$ $\mathcal{M}$ $\mathcal{M}$

Devendra Bhave
fonte