Oracle existe

Ou un algorithme général pour un problème d'arrêt peut exister.
Mais, comme toujours, il y a des nuances.
Si vous êtes intéressé, je demande un chat.

Présentation

En 1936, Alan Turing a prouvé qu'il n'y a pas d'algorithme général qui analyse d'autres algorithmes et indique si le programme va se bloquer ou non.

Je voudrais immédiatement mettre un point sur tous les e et décrire les termes que j'utilise pour qu'il n'y ait pas de compréhension.

Le programme se bloque - l'algorithme fonctionnera une durée INFINIE, quelle que soit la vitesse d'exécution des commandes et le calcul parallèle. Quelle que soit la taille d'un supercalculateur, l'algorithme fonctionnera toujours pendant une durée infinie.

Exécution d'un programme dans un temps fini - l'algorithme sur n'importe quelle machine terminera ses calculs, peu importe leur volume. Par exemple, si un algorithme fonctionne sur 300 millions d'années, cela ne signifie pas qu'il se fige, il a juste besoin de fonctionner 300 millions d'années sur les ressources actuelles et il sera TOUJOURS terminé.

Vous pouvez maintenant continuer.

La preuve de Turing peut être décrite comme suit: il y a un certain oracle S (algorithme) à l'entrée dont une description de l'algorithme N et des données d'entrée X est fournie. Le programme s'arrête et renvoie 1 si l'algorithme N ne s'arrête pas, recevant X à l'entrée.

Le programme ne s'arrête pas autrement, si l'algorithme N s'arrête après avoir reçu une entrée X. Si nous alimentons notre description de nous-mêmes vers notre oracle, il y aura une contradiction et l'algorithme se contredira lui-même. Les détails peuvent être trouvés sur le wiki .

Oracle existe mais il a besoin d'un frère

Vous n'êtes pas confus par le fait que l'oracle devrait geler si l'algorithme qu'il analyse s'arrête, je suis directement confus par ce fait, donc pour preuve nous corrigerons légèrement la conclusion de l'oracle. Laissez l'oracle retourner 1 ou 0. Eh bien, demandez-vous, rien n'a changé si nous écrivons sur le pseudo-code:

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){
}
}

.

.
, . , . - , .

, , . , .