Le problème d'arrêt est-il décidable pour les programmes purs sur un ordinateur idéal?

25

Il est assez simple de comprendre pourquoi le problème d'arrêt est indécidable pour les programmes impurs (c'est-à-dire ceux dont les E / S et / ou les états dépendent de l'état global de la machine); mais intuitivement, il semble que l'arrêt d'un programme pur sur un ordinateur idéal serait décidable par exemple par l'analyse statique.

Est-ce bien le cas? Sinon, quels sont les contre-exemples ou les documents qui réfutent cette affirmation?

halting-problem static-analysis Jules
la source
35
Notez que les preuves standard que le problème d'arrêt est indécidable (comme celui décrit sur wikipedia: en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof ) fonctionnent toutes avec des modèles de calcul qui n'essaient même pas de représenter les E / S. Et bien que, par exemple, les machines de Turing soient dynamiques, leur comportement est formellement défini en termes de fonctions pures. Donc, dans un certain sens, «des programmes purs sur un ordinateur idéal» est en fait le cadre dans lequel le problème d'arrêt est généralement indécidable.
Ben
1
Quelles recherches avez-vous faites? Googler "Halting problem" aurait déjà dû répondre à cette question pour vous.
Jonathan Cast

Réponses:

38

Voici une preuve d'indécidabilité par réduction du problème d'arrêt.

Réduction: étant donné une machine M et une entrée X , construisez une nouvelle machine de Turing H qui ne lit aucune entrée, mais écrit M et X sur la bande et simule M sur X jusqu'à ce que M s'arrête.

Le comportement de cette nouvelle machine est indépendant de la bande d'entrée, il s'agit donc d'une machine de Turing pure sur laquelle seule l'analyse statique est applicable. Si l'analyse statique était suffisante, cela pourrait montrer si s'arrête, ce qui montrerait si s'arrête sur , ce qui résoudrait le problème d'arrêt pour les machines impures, que nous savons indécidable, et donc votre problème est indécidable aussi.H M xHHMX

Lieuwe Vinkhuijzen
la source
2
Le problème d'arrêt de la bande vierge
Hendrik Jan
@HendrikJan Précisément!
Lieuwe Vinkhuijzen
16

Non, ce n'est pas le cas et, de plus, cela ne dépend pas des E / S.

Contre-exemple simple: écrire un programme pour trouver un nombre impair parfait (c'est un problème ouvert: nous ne savons pas encore s'il en existe un) - il ne prend aucune entrée et n'effectue aucune tâche impure ; il peut s'arrêter lorsqu'il en trouve un ou fonctionner à l'infini (dans le cas où un tel nombre n'existe pas). Maintenant, si l'analyse statique était suffisamment puissante pour déterminer le cas d'arrêt, elle serait utilisée pour répondre à cette question (et à bien d'autres) où l'arrêt signifierait l'existence positive d'un tel nombre et ne pas s'arrêter signifierait qu'il n'y en a pas, mais malheureusement l'analyse statique n'est pas si puissant.

Mal
la source
18
Je ne vois pas vraiment l'intérêt de cette réponse. Ce n'est pas parce que nous ne savons pas actuellement si un tel nombre existe qu'il ne le fait pas, ni que nous ne pourrions pas à l'avenir écrire un analyseur statique capable de le décider. Une meilleure alternative consiste à utiliser un problème indécidable connu. Par exemple, il est connu qu'aucun programme ne peut résoudre toutes les équations diophantiennes, et résoudre une telle équation est une tâche similaire à celle indiquée dans la réponse.
Bakuriu
2
Eh bien, si le problème d'arrêt était décidable, alors chaque problème serait décidable si nous pouvons le mettre sous une forme où nous demandons si un programme s'arrête ou non. Ou toute question de forme: il y a un ensemble dénombrable, et je peux décider si un élément potentiel individuel est dans l'ensemble ou non. L'ensemble est-il vide? Les équations diophantiennes ont un ensemble dénombrable de solutions potentielles, et je peux vérifier si chaque solution potentielle individuelle est une solution ou non. Si le problème de l'arrêt était décidable, les équations diophantiennes seraient décidables.
gnasher729
10
@ gnasher729 Oui, et comme ils ne le sont pas, le problème de l'arrêt est indécidable. C'est mon point. Alors que l'énoncé de cette réponse n'a aucune implication réelle: "Considérez cette définition mathématique. Actuellement, nous n'avons aucune idée si un programme qui décidera de cela s'arrêtera ou non, mais demain un gars pourrait découvrir que c'est le cas ou non et cette réponse devient 100 % sans signification".
Bakuriu
6
N'est-ce pas un cas similaire à Comment peut-on déterminer si π a une séquence de chiffres? , le problème d'arrêt est indécidable sur des classes de problèmes, pas sur des problèmes isolés .
npostavs
2

La preuve classique par diagonalisation est une machine pure , non seulement c'est une machine de Turing pure, mais elle ne repose pas sur des "problèmes ouverts".

Par exemple, une machine de Turing qui exécute la conjecture de Collatz a un statut d'arrêt inconnu, mais qui repose sur notre ignorance de la conjecture de Collatz, un jour nous pourrions prouver que Collatz avait raison et nous pourrions alors décider du statut d'arrêt de la conjecture (Soit pour certaines entrées ne s'arrête pas, soit s'arrête toujours).

Ainsi, la conjecture de Collatz pourrait déjà répondre à votre question (temporairement au moins), mais elle repose sur quelque chose que nous ne savons pas . Au lieu de cela, la preuve classique est un problème résolu: nous savons déjà que c'est indécidable .

Développeur de jeu
la source
0

Pour mémoire, la preuve standard de l'indécidabilité du problème d'arrêt repose sur la même idée que les quines: qu'il est possible d'écrire un programme dont un sous-terme est évalué dans le code source de l'ensemble du programme. Ensuite, s'il y avait une fonction haltsqui, étant donné le code source d'un programme, renvoyait True si ce programme s'arrêtait sur toutes les entrées et False sinon, ce serait un programme légal:

prog() = if halts "prog" then prog() else ()

où "prog"serait une expression évaluée par le code source de prog; cependant, vous pouvez rapidement voir que progs'arrête (pour toutes les entrées) ssi il ne s'arrête pas, ce qui est une contradiction. Rien dans cette preuve ne repose en aucune façon sur les E / S (avez-vous besoin d'E / S pour écrire une quine?).

Soit dit en passant, vous souhaiterez peut-être consulter les "E / S basées sur les dialogues" pour plus de preuves que les E / S ne sont pas du tout pertinentes pour votre problème (en gros, les programmes qui font des E / S peuvent être réduits à des programmes qui acceptent (explicites) des arguments fonctionnels et renvoyer la sortie sous forme de résultats supplémentaires (explicites) dans un langage paresseux). Malheureusement, je ne trouve pas de page raisonnable, non biaisée (ou pro-dialogue) sur le Web pour le moment.

Jonathan Cast
la source