Máquina que sempre para - Machine that always halts

Na teoria da computabilidade , uma máquina que sempre para , também chamada de decisor ou máquina de Turing total , é uma máquina de Turing que eventualmente para para cada entrada.

Como sempre para, essa máquina é capaz de decidir se uma determinada string é membro de uma linguagem formal . A classe de linguagens que pode ser decidida por tais máquinas é exatamente o conjunto das linguagens recursivas . No entanto, o problema da parada , determinando se uma máquina de Turing arbitrária para em uma determinada entrada, é em si 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 usa apenas memória finita em qualquer entrada específica pode ser forçada a parar para cada entrada, restringindo seus recursos de controle de fluxo de forma que nenhuma entrada fará com que a máquina entre em um loop infinito . Como um exemplo trivial, uma máquina implementando uma árvore de decisão finitária sempre irá parar.

Não é necessário que a máquina esteja totalmente livre de recursos de loop, no entanto, para garantir a parada. Se restringirmos os loops a um tamanho previsivelmente finito (como o loop FOR no BASIC ), podemos expressar todas as funções recursivas primitivas (Meyer e Ritchie, 1967). Um exemplo de tal máquina é fornecido pela linguagem de programação de brinquedo PL- {GOTO} de Brainerd e Landweber (1974).

Podemos definir ainda uma linguagem de programação na qual podemos garantir que funções ainda mais sofisticadas sempre sejam interrompidas. Por exemplo, a função de Ackermann , que não é recursiva primitiva, no entanto é uma função computável total por um sistema de reescrita de termos com uma ordem de redução em seus argumentos (Ohlebusch, 2002, pp. 67).

Apesar dos exemplos acima de linguagens de programação que garantem o término dos programas, não existe uma linguagem de programação que capture exatamente as funções recursivas totais , ou seja, as funções que podem ser calculadas por uma máquina de Turing que sempre para. Isso ocorre porque a existência de tal linguagem de programação seria uma contradição para a não-semidecidibilidade do problema se uma máquina de Turing para a cada entrada.

Relação com máquinas de Turing parciais

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

1. Cada função parcial computável por uma máquina de Turing parcial pode ser estendida (isto é, ter seu domínio ampliado) para se tornar uma função computável total?
2. É possível mudar a definição de uma máquina de Turing de forma que uma classe particular de máquinas de Turing totais, computando todas as funções computáveis ​​totais, possa ser encontrada?

A resposta a cada uma dessas perguntas é não.

O teorema a seguir mostra que as 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 questão acima tem uma resposta negativa. Este fato está intimamente relacionado à insolubilidade algorítmica do problema da parada .

De fato, se g fosse uma função computável total estendendo f, então g seria computável por alguma máquina de Turing; fixe e como o índice de tal máquina. Construir uma máquina de Turing M , usando o teorema de recursão de Kleene , que na entrada0 simula a máquina com índice e rodando em um índice n _M para M (assim, a máquina M pode produzir um índice de si mesma; este é o papel do teorema da recursão). Por suposição, esta simulação eventualmente retornará uma resposta. Defina M de forma que se g ( n _M ) = m então o valor de retorno de M é . Assim, f ( n _M ), o verdadeiro valor de retorno de M na entrada${\ displaystyle m + 1}$0 , não será igual a g ( n _M ). Logo, g não estende f .

A segunda questão pergunta, em essência, se existe outro modelo razoável de computação que calcula apenas funções totais e calcula todas as funções computáveis ​​totais. Informalmente, se tal modelo existisse, cada um de seus computadores poderia ser simulado por uma máquina de Turing. Assim, se este novo modelo de computação consistisse em uma sequência de máquinas, haveria uma sequência recursivamente enumerável de máquinas de Turing que computam funções totais e de modo que toda função computável total é computável por uma das máquinas T _i . Isso é impossível, porque uma máquina T poderia ser construída de forma que na entrada i a máquina T retorne . Esta máquina não pode ser equivalente a nenhuma máquina T na lista: suponha que ela estivesse na lista no índice j . Então , que não retorna um resultado inteiro. Portanto, não pode ser total, mas a função por construção deve ser total (se as funções totais forem recursivamente enumeráveis, então essa função pode ser construída), o que é uma contradição. Isso mostra que a segunda questão tem uma resposta negativa. ${\ displaystyle M_ {1}, M_ {2}, \ ldots}$${\ displaystyle T_ {1}, \ ldots T_ {2}, \ ldots}$${\ displaystyle T_ {i} (i) +1 \,}$${\ displaystyle T_ {j} (j) = T_ {j} (j) +1 \,}$

O conjunto de índices do total de máquinas de Turing

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

Veja também: Análise de rescisão .

Provabilidade

Pode-se estar interessado não apenas em se uma máquina de Turing é total, mas também em se isso pode ser provado em um determinado sistema lógico, como a aritmética de Peano de primeira ordem .

Em um sistema à prova de som , toda máquina de Turing comprovadamente total é de fato total, mas o inverso não é verdadeiro: informalmente, para cada sistema de prova de primeira ordem que é forte o suficiente (incluindo a aritmética de Peano), existem máquinas de Turing que são consideradas total, mas não pode ser provado como tal, a menos que o sistema seja inconsistente (neste caso, pode-se provar qualquer coisa). A prova de sua totalidade repousa em algumas suposições ou requer outro sistema de prova.

Assim, como se pode enumerar todas as provas no sistema de provas, pode-se construir uma máquina de Turing sobre a entrada n que passa pelas primeiras n provas e procurar uma contradição. Se encontrar um, entra em um loop infinito e nunca para; caso contrário, ele para. Se o sistema for consistente , a máquina de Turing irá parar em cada entrada, mas não se pode provar isso em um sistema de prova forte o suficiente devido aos teoremas da incompletude de Gödel .

Pode-se também criar uma máquina de Turing que irá parar se e somente se o sistema de prova for inconsistente e, portanto, não total para um sistema consistente, mas não pode ser provado tal: Esta é uma máquina de Turing que, independentemente da entrada, enumera todas as provas e pára em uma contradição.

Uma máquina de Turing que passa pelas sequências de Goodstein e para em zero é total, mas não pode ser provada como tal na aritmética de Peano.

Veja também

• BlooP e FlooP
• Programação funcional total
• Análise de rescisão

Referências

• Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley.
• Meyer, AR, Ritchie, DM (1967), The complex of loop programs , Proc. dos Encontros Nacionais da ACM, 465.
• Sipser, M. (2006), Introdução à Teoria da Computação , PWS Publishing Co.
• Kozen, DC (1997), Automata and Computability , Springer.
• Ohlebusch, E. (2002), Advanced Topics in Term Rewriting , Springer.