human
Le problème de l'arrêt Quelqu'un peut-il s'il vous plaît m'expliquer ce que c'est... comme si j'avais cinq ans. (Ceci est une question d'informatique) Expliquez comme si j'avais cinq ans.
gpt
Un programme informatique reçoit des données ( entrée ) et sort des données ( sortie ) . Et un programme lui-même est une donnée. Ainsi, un programme peut être entré dans un autre programme. ( De plus , un programme peut * produire * un programme ; c'est ce que fait un compilateur . ) Certains programmes s'exécutent indéfiniment ( sur une entrée particulière ) , et certains programmes s'arrêtent . Par exemple , voici un programme en BASIC qui s'exécute indéfiniment : 10 PRINT " Hello " 20 GOTO 10 Voici un programme qui s'arrête : 10 PRINT " Hello " 20 PRINT " Ok , j'ai terminé . " Et voici un programme qui s'exécutera indéfiniment ou s'arrêtera en fonction de l'entrée : 10 INPUT A$ 20 IF A$ = " STOP " THEN GOTO 50 30 PRINT " Running forever ! " 40 GOTO 30 50 PRINT " Stoppingly stoping ! " un programme qui examinera un autre programme et une entrée , et dira si ce programme s'arrêtera , compte tenu de cette entrée ? Utilisons quelques maths. Nous dirons que X(Y ) signifie "exécuter le programme X sur l'entrée Y". Et si un programme prend deux entrées Y et Z , nous l'écrirons sous la forme X(Y , Z ) . Ainsi , le problème d'arrêt est : Pouvons-nous écrire un programme H(P , I ) qui prendra un programme P et une entrée I , et dire si P(I ) s'exécute indéfiniment ou s'arrête ? Eh bien , supposons que nous le puissions . Supposons que nous ayons écrit un programme H qui fasse exactement cela ! Il afficherait " STOP " ou " FOREVER " selon que P(I ) s'arrêterait ou fonctionnerait pour toujours . Maintenant , nous pourrions écrire un nouveau programme G(X ) . G prend le programme X en entrée , et ce que fait G est d'exécuter H(X , X ) pour savoir si X(X ) s'arrête ou s'exécute indéfiniment . Ensuite, G(X ) décide ce qu'il doit faire, en fonction de ce que H(X , X ) a dit. Si H(X , X ) dit " STOP " , alors G(X ) s'exécute indéfiniment , tout comme le programme BASIC ci-dessus . Et si H(X , X ) dit " POUR TOUJOURS " , alors G(X ) s'arrête . Maintenant, nous exécutons G(G ) . G(G ) exécute H(G , G ) qui demande si G(G ) s'arrête . Si H(G , G ) dit qu'il s'arrête , alors G(G ) décide de s'exécuter indéfiniment — ce qui signifie que H(G , G ) est buggé ! Et si H(G , G ) dit que G(G ) court pour toujours , alors G(G ) décidera de s'arrêter . Encore une fois , H a un bogue ; il donne la mauvaise réponse. Oops ! Peu importe ce que fait H, il ne peut pas avoir la bonne réponse ! H est un programme impossible. Il n'est pas possible d'écrire un programme qui indique parfaitement si d'autres programmes s'arrêtent ou s'exécutent indéfiniment. Maintenant, il y a beaucoup de programmes dont nous * pouvons * dire s'ils s'arrêtent ou s'exécutent indéfiniment. Par exemple, un programme avec une boucle de retour au début - comme le premier ci-dessus - s'exécute évidemment indéfiniment. Et un programme sans boucles ni GOTO — comme le second ci-dessus — ne s'exécute certainement pas indéfiniment. Nous pouvons également prouver que beaucoup d'autres programmes avec des boucles finiront par s'arrêter. Et nous pouvons écrire des programmes qui le prouveront pour nous. Mais il n'y a aucun moyen d'écrire un programme qui réponde correctement à cette question pour * chaque programme possible *, parce que nous pouvons toujours trouver un programme délicat comme G qui le réfute.