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.

${\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ⁿ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

• Computabilidade
• Computador quântico

Referências

Ligações externas

• Lecture on finite-state automata by Adam Webber