Chaque fois que les gens se posent sur le problème de l'arrêt que ce qui a trait à la programmation, les gens réagissent avec des "Si vous venez d'ajouter une boucle, vous avez l'arrêt du programme et, par conséquent, vous ne pouvez pas automatiser des tâches"
Du sens. Si votre programme est une boucle infinie, puis lorsque votre programme est en cours d'exécution, vous n'avez aucun moyen de savoir si le programme est toujours à croquer d'entrée, ou si c'est juste en boucle à l'infini.
Mais certains cela semble contre-intuitif. Que faire si j'écrivais un problème de l'arrêt solveur, qui prend le code source en entrée. rascher@localhost$ ./haltingSolver source.c
Si mon code (la source.c) ressemble à ceci:
for (;;) { /* infinite loop */ }
Il semble que ce serait assez facile pour mon programme pour voir ce. "Regardez la boucle, et de regarder l'état. Si la condition est juste, fondée sur les littéraux, et aucune des variables, alors vous savez toujours le résultat de la boucle. Si il y a des variables (par exemple while (x < 10)), voir si ces variables sont jamais modifiés. Si non, alors vous savez toujours le résultat de la boucle."
Accordé, ces contrôles ne serait pas trivial (le calcul de l'arithmétique de pointeur, etc), mais il ne semble pas impossible. par exemple:
int x = 0
while (x < 10) {}
a pu être détecté. avec - mais ce n'est pas trivialement:
int x = 0
while (x < 10)
{
x++;
if (x == 10)
{
x = 0
}
}
Maintenant, quelle est la saisie de l'utilisateur? C'est le kicker, c'est ce qui rend un programme imprévisible.
int x = 0;
while (x < 10)
{
scanf("%d", &x); /* ignoring infinite scanf loop oddities */
}
Maintenant mon programme peut dire: "Si l'utilisateur entre un 10 ou plus, le programme s'arrête. Sur tous les autres commentaires, il passe en boucle à nouveau."
Ce qui signifie que, même avec des centaines d'entrées, on devrait être en mesure d'énumérer les conditions dans lesquelles le programme s'arrête. En effet, quand j'écris un programme, je fais toujours en sorte que quelqu'un a la possibilité d'y mettre fin! Je ne dis pas que la liste de conditions est trivial à créer, mais il ne semble pas impossible pour moi. Vous pourriez prendre l'entrée de l'utilisateur, les utiliser pour calculer pointeur d'index, etc - mais qui ajoute juste le nombre de conditions pour s'assurer que le programme se termine, n'est pas impossible de les énumérer.
Alors, quel est exactement le problème de l'arrêt? Ce que je ne suis pas à la compréhension de l'idée que l'on ne peut pas écrire un problème pour détecter les boucles infinies? Ou, pourquoi sont des "boucles" un tel, souvent citée en exemple?
Mise à JOUR
Alors, permettez-moi de changer la question un peu: qu'est-ce que le problème de l'arrêt en tant qu'il s'applique aux ordinateurs? Et puis je vais répondre à certains commentaires:
Beaucoup de gens ont dit que le programme doit être en mesure de faire face à "toute entrée quelconque." Mais dans les ordinateurs, il n'y a pas toujours de tout arbitraire d'entrée. Si je ne saisissez qu'un seul octet de données, que je n'ai que 2^8 entrées possibles. Ainsi, à titre d'exemple:
int c = getchar()
switch (c) {
case 'q':
/* quit the program */
}
Tout d'un coup, j'ai juste comptabilisés pour toutes les possibilités. Si c a la séquence de bits 0x71, il ne fait qu'une chose. Pour tous les autres modèles, il fait quelque chose d'autre. Même un programme qui accepte une chaîne de caractères arbitraire d'entrée n'est jamais vraiment "arbitraire", puisque les ressources sont limitées, ce qui signifie que, bien que la théorie de "l'arbitraire" s'applique... ce n'est pas exactement un-à-un avec la pratique.
L'autre exemple les personnes citées est ceci:
while (n != 1)
if (n & 1 == 1)
n = 3 * n + 1;
else
n /= 2;
Si n est un entier de 32 bits... alors je peux visuellement vous dire si oui ou non cela va s'arrêter.
Je suppose que cette édition n'est pas en train de demander quoi que ce soit, mais le plus convaincant exemple que j'ai vu est ce un:
Supposons que vous avez votre magique de programme/méthode pour déterminer qu'un programme s'arrête.
public bool DeterminesHalt(string filename, string[] args){
//runs whatever program you tell it do, passing any args
//returns true if the program halts, false if it doesn't
}
Maintenant, disons que nous écrire un petit morceau de code, tels que...
public static void Main(string[] args){
string filename = Console.ReadLine(); //read in file to run from user
if(DeterminesHalt(filename, args))
for(;;);
else
return;
}
Ainsi, pour cet exemple, nous pouvons écrire un programme pour faire l'exact opposé de notre magique arrêt de méthode. Si nous réussissons à nous de déterminer qu'un programme stopper les, nous venons de sauter dans une boucle infinie; autrement, si nous déterminons que le programme est dans une boucle infinie, nous la fin du programme.
Et puis, si vous avez intentionnellement écrire un programme qui contient une boucle infinie... "résoudre le problème de l'arrêt" est assez discutable, n'est-ce pas?
