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,\mathrm{\Sigma },\mathrm{\Gamma },⊢,\mathrm{\_},\delta ,q,q_a,q_r)$ , onde

• $Q$ é o conjunto finito de estados;
• $\mathrm{\Sigma }$ é o conjunto finito do alfabeto de entrada;
• $\mathrm{\Gamma }$ é o conjunto finito do alfabeto de fita;
• $⊢\in \mathrm{\Gamma }-\mathrm{\Sigma }$ é o marcador de final de fita à esquerda;
• $\mathrm{\_}\in \mathrm{\Gamma }-\mathrm{\Sigma }$ é o símbolo branco;
• $\delta :Q\times \mathrm{\Gamma }\to Q\times \mathrm{\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\ne 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. 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. 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.

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.

Ver também

• Computabilidade
• Computador quântico

Ligações externas

• Lecture on finite-state automata by Adam Webber