Le Problème de l'Arrêt dans le Domaine

Question

Quand avez-vous personnellement de venir sur le problème de l'arrêt dans le domaine? Cela peut être un collègue / patron suggéré une solution qui violerait les limites fondamentales de calcul, ou lorsque vous avez réalisé vous-même un problème que vous essayez de résoudre, en fait, était impossible à résoudre.

La dernière fois que je suis venu avec elle était lors de l'étude type de pions. Notre classe a réalisé qu'il serait impossible d'écrire un type parfait checker (celle qui accepterait tous les programmes qui irait sans erreurs de type, et de rejeter tous les programmes qui irait avec des erreurs de type) parce que ce serait, en effet, de résoudre le problème de l'arrêt. Un autre a été quand nous avons réalisé, dans la même classe, qu'il serait impossible de déterminer si une division serait jamais se produire par zéro, dans le type de vérification de la scène, car de vérifier si un nombre, au moment de l'exécution, est de zéro, est aussi une version du problème de l'arrêt.

Answer 1

J'ai littéralement eu attribué le problème de l'arrêt, comme dans "écrire un moniteur plugin pour déterminer si un hôte est en permanence en bas". Sérieusement? OK, donc je vais juste lui donner un seuil. "Non, car il pourrait revenir par la suite."

Beaucoup théorique exposition s'ensuivit.

Answer 2

Il y a des années, je me souviens de la lecture d'un examen (en Byte magazine, je crois) d'un produit "de Base" Boucle Infinie Finder ou BILF. BILF était censé analyser votre Microsoft Base de code source et de trouver toutes les boucles qui n'a pas de fin. Il prétendait être capable de tout trouver de boucle infinie dans le code.

La critique a été suffisamment malin pour remarquer que, pour que le programme fonctionne dans tous les cas, il aurait à résoudre le problème de l'arrêt, et est allé jusqu'à fournir une preuve mathématique de pourquoi ça ne pourrait pas fonctionner dans tous les cas.

Dans le prochain numéro, ils ont publié une lettre d'un représentant de l'entreprise en expliquant que le problème sera résolu dans la prochaine version.

Answer 3

Le projet sur lequel je travaille en ce moment a indécidable tous les problèmes sur elle. C'est une unité de générateur de test, donc, en général, ce qu'il tente d'accomplir, c'est de répondre à la question "ce que ce programme". Qui est une instance d'un problème de l'arrêt. Un autre problème qui est apparu au cours du développement est "deux-test () fonctionne de la même manière"? Ou encore : "l'ordre de ces deux appels (assertions) de la matière"?

Ce qui est intéressant à propos de ce projet est que, même si vous ne pouvez pas répondre à ces questions dans toutes les situations, vous pouvez trouver des solutions intelligentes qui permettent de résoudre le problème de 90% du temps, ce qui pour ce domaine est vraiment très bon.

D'autres outils que d'essayer de raisonner sur d'autres codes, comme l'optimisation des compilateurs/interpréteurs, statique outils d'analyse de code, même le refactoring, sont susceptibles de frapper (donc contraints de trouver des solutions de contournement pour) le problème de l'arrêt.

Answer 4

Exemple 1. Combien de pages de mon rapport?

Quand j'étais apprentissage de la programmation, j'ai joué avec un outil pour imprimer assez de rapports à partir de données. Évidemment, je voulais que ce soit vraiment puissant et flexible de sorte qu'il serait le générateur de rapports pour mettre fin à tous les générateurs de rapports.

La définition de rapport a fini par être tellement souple qu'elle était Turing. Il pourrait ressembler à des variables, à choisir entre deux options, utiliser les boucles pour répéter les choses.

J'ai défini une variable intégrée N, le nombre de pages du rapport de l'instance, de sorte que vous pourriez mettre une chaîne de caractères qui dit "page n N" sur chaque page. J'ai fait deux passes, la première à compter les pages (au cours de laquelle N a été fixée à zéro), et le deuxième réellement générer, à l'aide de la N de la première passe.

Parfois, la première étape serait de calculer N, puis la seconde étape serait de générer un nombre différent de pages (parce que maintenant la non nul N allait changer à ce que le rapport ne). J'ai essayé de faire des passes de manière itérative jusqu'à la N s'installe. Puis j'ai réalisé que c'était sans espoir parce que si il n'a pas s'installer?

Cela conduit ensuite à la question "puis-je au moins de détecter et de prévenir l'utilisateur si l'itération ne va jamais à régler sur une valeur stable pour le nombre de pages de leur rapport produit?" Heureusement, à cette époque, j'étais devenu intéressé à la lecture de Turing, Godel, compilation, etc. et fait le lien.

Des années plus tard, j'ai remarqué que MS Access parfois des tirages "à la Page 6 de 5", qui est vraiment une chose merveilleuse.

Exemple 2: compilateurs C++

Le processus de compilation s'agit d'une expansion de modèles. Modèle de définitions peuvent être sélectionnées à partir de plusieurs spécialisations (assez bonne pour servir de "cond") et ils peuvent également être récursive. C'est donc une Turing (fonctionnels purs) méta-système, dans lequel le modèle de définitions de la langue, les types sont les valeurs, et le compilateur est vraiment un interprète. C'était un accident.

Par conséquent, il n'est pas possible d'examiner tout programme C++ et dire si le compilateur pourrait en principe se terminer par un succès de la compilation du programme.

Compilateur vendeurs de contourner ce problème en limitant la pile de la profondeur de modèle récursif. Vous pouvez ajuster la profondeur de g++.

Answer 5

Beaucoup de il ya de nombreuses lunes j'ai été l'assistante d'un consultant pour notre société qui a été mise en œuvre très complexe système de rail pour déplacer des paniers de pièces de métal et d'un 1500 degrés de haut fourneau. La piste elle-même est assez complexe de "mini-voies de garage" sur le plancher de l'atelier qui a croisé lui-même dans quelques endroits. Plusieurs motorisé palettes faisait la navette de paniers de pièces de autour de, selon un horaire. Il était très important que le four portes étaient ouvertes pour une durée aussi brève que possible.

Étant donné que l'usine était en pleine production, le consultant était pas en mesure d'exécuter son logiciel en "temps réel" pour tester ses algorithmes d'ordonnancement. Au lieu de cela, il a écrit un joli graphique-y simulateur. Comme nous l'avons vu virtuelle palettes de se déplacer sur son tracé, j'ai demandé "comment allez-vous savoir si vous avez des conflits de calendrier?"

Sa réponse rapide, Facile - la simulation ne sera jamais s'arrêter."