O puede existir un algoritmo general para un problema de apagado.
Pero, como siempre, hay matices.
Si está interesado, le pido gato.
Introduccion
En 1936, Alan Turing demostró que no existe un algoritmo general que analice otros algoritmos e indique si el programa se bloqueará o no.
Me gustaría puntuar inmediatamente toda la ey describir los términos que utilizo para que no se entienda.
El programa se congela : el algoritmo funcionará una cantidad INFINITA de tiempo, independientemente de la velocidad de ejecución de los comandos y la computación paralela. No importa cuán grande sea una supercomputadora, el algoritmo siempre funcionará una cantidad infinita de tiempo.
Ejecutar un programa en un tiempo finito : el algoritmo en cualquier máquina finalizará sus cálculos sin importar cuán voluminosos sean. Por ejemplo, si un algoritmo ejecuta 300 millones de años, esto no significa que se cuelgue, solo necesita ejecutar 300 millones de años con los recursos actuales y SIEMPRE termina.
Ahora puedes continuar.
La prueba de Turing se puede describir de la siguiente manera: hay un cierto oráculo S (algoritmo) en la entrada del cual se proporciona una descripción del algoritmo N y los datos de entrada X. El programa se detiene y devuelve 1 si el algoritmo N no se detiene, recibiendo X en la entrada.
El programa no se detiene de otra manera, si el algoritmo N se detiene después de recibir una entrada X. Si alimentamos nuestra descripción de nosotros mismos a nuestro oráculo, habrá una contradicción y el algoritmo se contradirá a sí mismo. Los detalles se pueden encontrar en la
wiki .
Oracle existe pero necesita un hermano
No está confundido por el hecho de que el oráculo debe congelarse si el algoritmo que analiza se detiene, estoy directamente confundido por este hecho, por lo que, como prueba, corregiremos ligeramente la conclusión del oráculo. Deje que el oráculo devuelva 1 o 0. Bien, entonces, pregunta, nada ha cambiado si escribimos en el pseudocó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){
}
}
.
.
, . , . - , .
, , . , .