Máquina de Turing que sempre para

Na teoria da computação, uma máquina de Turing que sempre para, também chamada de máquina de Turing total,[1] é uma máquina de Turing que para qualquer entrada.

Como ela sempre para, a máquina é sempre capaz de decidir se uma determinada cadeia pertence a uma determinada linguagem formal. A classe de linguagens que podem ser decidida por estas máquinas é exatamente o conjunto das linguagens recursivas. No entanto, devido ao problema da parada, determinar quando uma Máquina de Turing para para uma entrada arbitrária é um problema indecidível.

Funções computáveis por máquinas de Turing totais

Na prática, muitas funções de interesse são computáveis por máquinas que sempre param. Uma máquina que utiliza apenas memória finita em sua entrada particular pode ser forçada a parar restringindo a capacidade de sua estrutura de controle para nenhuma entrada provoque um laço infinito. Como exemplo, uma máquina implementando uma árvore de decisão sempre irá parar.

Não é necessário que a máquina seja inteiramente livre de entrar em um laço, e sim que ela garanta que sempre pare. Se restringirmos os laços para serem de um tamanho finito previsível (assim como o laço FOR em BASIC), podemos descrever todas as funções primitivas recursivas (Meyer e Ritchie, 1967).

Nós podemos definir uma linguagem de programação na qual nós podemos assegurar que funções ainda mais sofisticadas irão sempre parar. Por exemplo, a função de Ackermann não é uma primitiva recursiva, mas é uma função totalmente computável por um sistema de cadeia reescrito com uma relação bem-ordenada nos seus argumentos (Ohlebusch, 2002, pp.67).

Relações com máquinas de Turing parciais

Uma máquina de Turing geral irá computar uma função parcial. Duas perguntas podem ser feitas sobre a relação entre máquinas de Turing parciais e totais:

1. Será que toda função parcial computável por uma máquina de Turing parcial pode ser estendida (isto é, tem seu domínio aumentado) para virar uma função totalmente computável?
2. Será que é possível mudar a definição de uma máquina de Turing para que, uma classe particular de máquinas totais que computam todas as funções totalmente computáveis, ser descoberta?

As respostas para essas perguntas são negativas.

O seguinte teorema mostra que funções computáveis por máquinas que sempre param não incluem extensões de todas as funções computáveis parciais, o que implica que a primeira pergunta tem resposta negativa. Esse fato está relacionado à impossibilidade de se resolver o Problema da parada.

Teorema. Estas são funções Turing parcialmente computáveis que não têm extensão para funções totalmente computáveis. Em particular, a função parcial f definida por f(n) = m se e somente se a máquina de Turing com índice n para na entrada 0 com saída m não tem extensão para máquinas totalmente computáveis.

A prova é por contradição. Se g fosse uma função computável total estendendo-se f, então g seria computável por alguma máquina de Turing; fixe e como o índice dessa máquina. Construa uma máquina de Turing M usando Kleene's recursion theorem, que, com entrada O, simula a máquina com índice e rodando num índice n_M por M (assim a máquina M pode preceder como um índice de si mesma; esse é o papel de um teorema recursivo). Pode-se assumir que essa simulação eventualmente retornará uma resposta. Definimos M para que se g(n_M) = m então o valor de retorno de M é m + 1. Então f(n_M), o verdadeiro valor de retorno de M com entrada 0, nao será igual a g(n_M). Isso contradiz o que assumimos (que g estende-se a f).

A segunda pergunta diz, em essência, se existe um outro modelo razoável de computação que computa somente funções totais e todas elas. Informalmente, se um modelo existisse, então cada uma de suas computações poderiam ser simuladas por uma máquina de Turing. Assim, se esse novo modelo de computação consistisse da sequência de máquinas ${\displaystyle M_{1},M_{2},\ldots }$, então existiria uma sequência da classe dos conjuntos recursivamente enumeráveis ${\displaystyle T_{1},\ldots T_{2},\ldots }$ de máquinas de Turing que computam funções totais e então toda função total é computável por uma das máquinas T_i. Isso é impossível, porque uma máquina ${\displaystyle T}$ poderia ser construída tal que com entrada i, a máquina T retorna ${\displaystyle T_{i}(i)+1\,}$. Essa máquina não pode ser equivalente a nenhuma máquina T da lista: considere que foi em uma lista de índice j. Então ${\displaystyle T_{j}(j)=T_{j}(j)+1\,}$, o que não retorna um número inteiro como resultado. Portanto, isso não pode ser total, porém a função por construção deve ser total (se funções totais são recursivamente enumeráveis, então essa função pode ser construída), e então temos uma contradição. Isso mostra que a segunda pergunta também tem resposta negativa.

O conjunto de índices de máquinas de Turing totais

O problema de decisão de uma máquina de Turing com índice e irá parar com toda parada não é decidível. Na verdade, esse problema está no nível ${\displaystyle \Pi _{2}^{0}}$ da hierarquia aritmética. Assim, esse problema é pelo menos mais difícil do que o problema da parada, que pergunta se uma máquina com índice e para com entrada 0. Intuitivamente, essa diferença na indecibilidade é porque cada instância do problema da "máquina total" representa infinitamente mais instâncias do problema da parada.

Teoria da computação

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia Chomsky	Gramática	Linguagem	Reconhecedor
Tipo-0	Irrestrita	Recursivamente enumerável	Máquina de Turing
--	--	Recursiva	Máquina de Turing que sempre para
Tipo-1	Sensível ao contexto	Sensível ao contexto	Autômato linearmente limitado
Tipo-2	Livre de contexto	Livre de contexto	Autômato com pilha
Tipo-3	Regular	Regular	Autômato finito

Ver também

• Programação funcional

Referências

1. Dexter Kozen (1997). Automata And Computability (em inglês). [S.l.]: Birkhäuse. ISBN 9780387949079 

Bibliografia

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
• Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.
• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Kozen, D.C. (1997), Automata and Computability, Springer.
• Ohlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer.