Máquina de Turing que sempre para

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.

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 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 pára 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 nM por M (assim a máquina M pode poreceder 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(nM) = m então o valor de retorno de M é m + 1. Então f(nM), o verdadeiro valor de retorno de M com entrada 0, nao será igual a g(nM). 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 M_1,M_2,\ldots, então existiria uma sequência da classe dos conjuntos recursivamente enumeráveis 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 Ti. Isso é impossível, porque uma máquina T poderia ser construída tal que com entrada i, a máquina T retorna 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 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[editar | editar código-fonte]

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 \Pi^0_2 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 pára 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.

Ver também[editar | editar código-fonte]

Referências

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

Bibliografia[editar | editar código-fonte]

  • 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.


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