Máquina de Turing somente de leitura

Máquina de Turing
Máquina
Máquina de Turing universal Máquina de Turing alternada Máquina de Turing quântica Máquina de Turing não determinística Máquina de Turing somente de leitura Máquina de Turing movimentação à direita Máquina de Turing probabilística Máquina de Turing multifita Máquina de Turing de Várias Faixas Máquinas de Turing equivalentes Exemplos de Máquinas de Turing
Ciência
Alan Turing Categoria:Máquina de Turing
v d e

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.

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

• ${\displaystyle Q}$ é o conjunto finito de estados;
• ${\displaystyle \Sigma }$ é o conjunto finito do alfabeto de entrada;
• ${\displaystyle \Gamma }$ é o conjunto finito do alfabeto de fita;
• ${\displaystyle \vdash \in \Gamma -\Sigma }$ é o marcador de final de fita à esquerda;
• ${\displaystyle \_\in \Gamma -\Sigma }$ é o símbolo branco;
• ${\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}}$ é a função de transição;
• ${\displaystyle q\in Q}$ é o estado inicial;
• ${\displaystyle q_{a}\in Q}$ é o estado de aceitação;
• ${\displaystyle 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 ${\displaystyle q}$ lendo um símbolo de alfabeto de entrada ${\displaystyle a}$, nós temos uma função de transição definida por ${\displaystyle \delta (q,a)=(q_{2},a_{2},d)}$ a qual substitui ${\displaystyle a}$ por ${\displaystyle a_{2}}$, passaria do estado ${\displaystyle q}$ para o estado ${\displaystyle q_{2}}$ e moveria a cabeça de leitura para a direção indicada por ${\displaystyle 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 ${\displaystyle 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^nb^nc^n} 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

• Computabilidade
• Computador quântico

Referências

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  A referência emprega parâmetros obsoletos |coautor= (ajuda)
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

• Lecture on finite-state automata by Adam Webber