Ou pode existir um algoritmo geral para um problema de desligamento.
Mas, como sempre, existem nuances.
Se estiver interessado, peço gato.
1. Introdução
Em 1936, Alan Turing provou que não há algoritmo geral que analise outros algoritmos e indique se o programa travará ou não.
Gostaria de colocar imediatamente todos os pontos e descrever os termos usados por mim para que não haja entendimento.
Programa congela - o algoritmo funcionará uma quantidade infinita de tempo, independentemente da velocidade de execução dos comandos e da computação paralela. Não importa quão grande seja um supercomputador, o algoritmo sempre executará uma quantidade infinita de tempo.
Executando um programa em um tempo finito - o algoritmo em qualquer máquina concluirá seus cálculos, não importa quão volumosos eles sejam. Por exemplo, se um algoritmo executa 300 milhões de anos, isso não significa que ele congela, ele precisa executar 300 milhões de anos nos recursos atuais e SEMPRE termina.
Agora você pode continuar.
A prova de Turing pode ser descrita da seguinte forma: existe um certo oráculo S (algoritmo) na entrada cuja descrição do algoritmo N e dados de entrada X é fornecida.O programa para e retorna 1 se o algoritmo N não parar, recebendo X na entrada.
O programa não para de outro modo, se o algoritmo N parar após receber uma entrada X. Se alimentarmos nossa descrição de nós mesmos ao nosso oráculo, haverá uma contradição e o algoritmo se contradiz. Detalhes podem ser encontrados no
wiki .
Oracle existe, mas ele precisa de um irmão
Você não está confuso pelo fato de que o oráculo deve congelar se o algoritmo que ele analisa parar, estou diretamente confuso com esse fato, portanto, como prova, corrigiremos levemente a conclusão do oráculo. Deixe o oráculo retornar 1 ou 0. Bem, você pergunta, nada mudou se escrevermos no pseudo-código:
If ((N)==0){
While (true){
}
}
, , :
, , :
S1 0 1 0 1 , .
S2 0 1 , . 1 1 , 0 . 0 , 1 .
, . .
, , . , , .
, . , .
:
If ((N)==0){
While(true){
}
}
If ((N)==0){
While(true){
}
}
.
.
, . , . - , .
, , . , .