Máquina de Turing somente de leitura – Wikipédia, a enciclopédia livre

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.

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

, onde

  • é o conjunto finito de estados;
  • é o conjunto finito do alfabeto de entrada;
  • é o conjunto finito do alfabeto de fita;
  • é o marcador de final de fita à esquerda;
  • é o símbolo branco;
  • é a função de transição;
  • é o estado inicial;
  • é o estado de aceitação;
  • é o estado de rejeição.

Portanto, para uma máquina de Turing padrão, dado um estado inicial lendo um símbolo de alfabeto de entrada , nós temos uma função de transição definida por a qual substitui por , passaria do estado para o estado e moveria a cabeça de leitura para a direção indicada por (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 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.

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 {anbncn} 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]

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]

Referências

  1. Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider, ed. Automata and Computability (hardcover). 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 

Ligações externas

[editar | editar código-fonte]