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.
M = ( Q , Σ , Γ , ⊢ , _ , δ , q , q a , q r ) {\displaystyle M=(Q,\Sigma ,\Gamma ,\vdash ,\_,\delta ,q,q_{a},q_{r})} , onde
Portanto, para uma máquina de Turing padrão, dado um estado inicial q {\displaystyle q} lendo um símbolo de alfabeto de entrada a {\displaystyle a} , nós temos uma função de transição definida por δ ( q , a ) = ( q 2 , a 2 , d ) {\displaystyle \delta (q,a)=(q_{2},a_{2},d)} a qual substitui a {\displaystyle a} por a 2 {\displaystyle a_{2}} , passaria do estado q {\displaystyle q} para o estado q 2 {\displaystyle q_{2}} e moveria a cabeça de leitura para a direção indicada por d {\displaystyle 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 {\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.
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 {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.
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.