Máquina de Turing somente de leitura

Uma máquina de Turing somente de leitura ou um autômato determinístico de estados finitos de dois caminhos (2AFD) é a classe de modelos de computabilidade que se comportam como uma máquina de Turing padrão que se move em ambas as direções pela cadeia de entrada, mas que não é possível escrever em sua fita. A máquina, na sua forma padrão, é equivalente em poder computacional a um autômato finito determinístico, e, portanto, só é possível analisar linguagens regulares.

Teoria

Nós definimos um padrão de 9-tuplas para a máquina de Turing somente de leitura.

$M=(Q,\Sigma ,\Gamma ,\vdash ,\_,\delta ,q,q_{a},q_{r})$ , onde

$Q$ é o conjunto finito de estados;
$\Sigma$ é o conjunto finito do alfabeto de entrada;
$\Gamma$ é o conjunto finito do alfabeto de fita;
$\vdash \in \Gamma -\Sigma$ é o marcador de final de fita à esquerda;
$\_\in \Gamma -\Sigma$ é o símbolo branco;
$\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ é a função de transição;
$q\in Q$ é o estado inicial;
$q_{a}\in Q$ é o estado de aceitação;
$q_{r}\in Q,~q_{r}\neq q_{a}$ é o estado de rejeição.

Portanto, para uma máquina de Turing padrão, dado um estado inicial $q$ lendo um símbolo de alfabeto de entrada $a$ , nós temos uma função de transição definida por $\delta (q,a)=(q_{2},a_{2},d)$ a qual substitui $a$ por $a_{2}$ , passaria do estado $q$ para o estado $q_{2}$ e moveria a cabeça de leitura para a direção indicada por $d$ (esquerda ou direita) para ler o próximo caractere da cadeia de entrada.^[1] Porém, para a máquina de Turing somente de leitura $a=a_{2}$ sempre, ou seja, ela apenas lê o caractere sem mudá-lo.

Esse modelo é equivalente a um AFD (autômato finito determinístico). A prova envolve a construção de uma tabela que lista o resultado do retrocesso com o controle em qualquer estado; no início da computação, este resultado é apenas a tentativa de ultrapassar o marcador de final de fita à esquerda. Em cada movimento para a direita, a tabela é atualizada usando os valores da tabela antiga e o caractere que estava na célula anterior. Uma vez que a cabeça de controle original teve algum número fixo de estados, e há um número fixo de estados no alfabeto de fita, a tabela também terá um tamanho fixo, e, portanto, pode ser computado por uma outra máquina de estado finito. Esta máquina, no entanto, nunca precisará voltar atrás, por isso é equivalente a um AFD.

Variantes

Diversas variantes deste modelo são também equivalentes a AFD's. Em particular, o caso da Não-Determinística (na qual a transição de um estado pode ser para vários estados dada a mesma entrada) é redutível a um AFD.

Outras variantes desse modelo permitem mais complexidade computacional. Com uma única pilha infinita o modelo pode analisar (pelo menos) qualquer linguagem que é computável por uma máquina de Turing em tempo linear.^[2] Em particular, a linguagem {aⁿbⁿcⁿ} pode ser analisada por um algoritmo o qual verifica primeiro se o número de a's é igual ao de b's, em seguida, retrocede e verifica se existe o mesmo número de b's e c's. Com o auxílio do Não-Determinismo a máquina pode analisar qualquer linguagem livre de contexto. Com duas pilhas infinitas a máquina é Turing equivalente e pode analisar qualquer linguagem formal recursiva.

Se é permitido ter várias cabeças de fita na máquina, ela pode analisar qualquer linguagem em L ou NL, de acordo se o não-determinismo é permitido.^[3]

Aplicações

Uma máquina de Turing somente de leitura é usada na definição da Máquina de Turing universal para aceitar a definição da máquina de Turing que será modelada, depois a computação continua com a máquina de Turing padrão.

Na pesquisa moderna, o modelo tornou-se importante na descrição de uma nova classe de complexidade de Autômato quântico finito ou autômato probabilístico determinístico.^[4]^[5]

Ver também

Referências

↑ Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider, ed. Automata and Computability (hardcover)<|formato= requer |url= (ajuda). Col: Undergraduate Texts in Computer Science 1 ed. New York: Springer-Verlag. pp. 158, 210, 224. ISBN 0-387-94907-0
↑ Computational Complexity by Wagner and Wechsung, section 13.3 (1986, ISBN 90-277-2146-7)
↑ Computational Complexity by Wagner and Wechsung, section 13.1 (1986, ISBN 90-277-2146-7)
↑ Kondacs, A.; J. Watrous (1997). «On the power of quantum finite state automata». 38th Annual Symposium on Foundations of Computer Science (FOCS '97): 66–75. doi:10.1109/SFCS.1997.646094. Consultado em 7 de novembro de 2007. Arquivado do original (– ^{Scholar search}) em 23 de agosto de 2007
↑ Dwork, Cynthia; Stockmeyer, Larry (1990). «A Time Complexity Gap For 2-Way Probabilistic Finite State Automata». SIAM Journal on Computing. 19 (6): 1011–1023. doi:10.1137/0219069. Consultado em 7 de novembro de 2007. Arquivado do original em 25 de outubro de 2009

Ligações externas

Lecture on finite-state automata by Adam Webber

[1] Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider, ed. Automata and Computability (hardcover)<|formato= requer |url= (ajuda). Col: Undergraduate Texts in Computer Science 1 ed. New York: Springer-Verlag. pp. 158, 210, 224. ISBN 0-387-94907-0

[2] Computational Complexity by Wagner and Wechsung, section 13.3 (1986, ISBN 90-277-2146-7)

[3] Computational Complexity by Wagner and Wechsung, section 13.1 (1986, ISBN 90-277-2146-7)

[4] Kondacs, A.; J. Watrous (1997). «On the power of quantum finite state automata». 38th Annual Symposium on Foundations of Computer Science (FOCS '97): 66–75. doi:10.1109/SFCS.1997.646094. Consultado em 7 de novembro de 2007. Arquivado do original (– ^{Scholar search}) em 23 de agosto de 2007

[5] Dwork, Cynthia; Stockmeyer, Larry (1990). «A Time Complexity Gap For 2-Way Probabilistic Finite State Automata». SIAM Journal on Computing. 19 (6): 1011–1023. doi:10.1137/0219069. Consultado em 7 de novembro de 2007. Arquivado do original em 25 de outubro de 2009

[1]

[2]

[3]

[4]

[5]