Algoritmo do castor: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 128:
A não-computabilidade de Σ(''n'') pode ser provado de forma semelhante. Na prova anterior, deve-se trocar a máquina ''AvaliaS'' com ''AvaliaΣ'' e ''Limpa'' com ''Incremento'' - uma MT simples, à procura de um primeiro 0 na fita e substituindo-o por 1.
A não-computabilidade de ''S''(''n'') também pode ser trivialmente estabelecido por referência ao [[problema da parada]]. Como ''S''(''n'') é o número máximo de passos que podem ser executados por uma máquina de Turing com parada, qualquer máquina que funciona por mais passos devem ser sem parada. Pode-se então determinar se uma máquina de Turing com ''n'' estados para executando-a para ''S''(''n'') passos; se ela ainda não parou, ela nunca irá parar. Como sendo capaz de calcular a ''S''(''n'') seria uma solução para o problema comprovadamente não-computável da parada, segue-se que''S''(''n'') também deve ser não-computável.
==Exemplos de máquinas de Turing para o algoritmo do castor ocupado==
| |||