4 Réponses :
Je crois ce que l'on entend "trouver tout le code qui est déjà exécuté", c'est-à-dire une couverture, éventuellement en combinaison avec le code généré dynamique. Qui peut en effet être réduit au problème d'arrêt.
Dites que vous avez un outil de couverture parfait qui trouvera chaque morceau de code dans un programme qui peut être exécuté (donc le reste est un code mort). Compte tenu d'un programme p , cet outil serait également en mesure de décider si le programme étendu (p; halt) exécute jamais l'instruction HALT ou Si la partie HALT est un code mort. Donc, cela résoudrait le problème d'arrêt que nous savons est indécitable.
Après avoir passé du temps à penser à votre argument. Je ne suis pas sûr que je suis convaincu. Comme suggéré dans la réponse ci-dessous, nous n'essayons pas de décider si le programme arrête (bien que je voie les parallèles à ce problème). Nous essayons de trouver toutes les dépendances pour un programme donné. Plus fondamentalement, toutes les dépendances ne sont-elles pas codées à l'intérieur de l'application avec des métadonnées? (Je suppose que non parce que vous pouvez les charger au moment de l'exécution - mais la dépendance serait alors stockée dans une constante ou une variable à un moment donné) HMMMMM. Je devrais probablement comprendre comment transformer cela en wiki.
Je suis en désaccord avec Larsman.
Le problème d'arrêt indique qu'aucun programme Alan Turing s'est avéré en 1936 qu'un algorithme général pour résoudre le problème d'arrêt pour toutes les paires d'intrants de programme possibles ne peut exister. Nous disons que le problème d'arrêt est indéciable sur les machines de Turing.
D'autre part, nous n'essayons pas de faire un tel programme / algorithme, mais nous essayons de trouver tout le code Si nous essayons de créer un émulateur pouvant exécuter n'importe quel programme, nous échouerions depuis lors, vous pouvez (facilement) réduire cela au problème d'arrêt. Mais généralement, vous construisez un émulateur pour quelque chose comme un garçon de jeu qui soutient une quantité finie de cartouches de jeu (programmes) et c'est donc possible. p ne peut prendre tout programme et décider si ce programme exécute l'instruction HALT . Permettez-moi de citer Wikipedia:
Quitter () (situation très optimiste) Nous avons prouvé qu'il sera appel >, alors que c'était impossible ?!
Est-ce que cela signifie "wooow" ou "ai-je perdu mon temps sur ce gars ?!"?
Non, je l'envisageait comme un compliment et une réalisation de la stupide que je suis stupide. :-( MDR
"Si nous ingénieur inverseur, le programme et voyons qu'il appelle immédiatement la sortie () (situation d'exemple très optimiste) Nous avons prouvé qu'il appellera HALT, alors qu'il était impossible ?!" Le problème d'arrêt n'implique pas que cela est impossible pour chaque cas, mais qu'il y a des cas certains pour lesquels il est impossible.
En ce qui concerne la "quantité finie de mémoire" argument: vous avez raison, car une gameboy (ou même un PC) est officiellement une machine à états finis. Le nombre d'états, cependant, est deux à la puissance [la quantité de RAM dans la machine]. Donc, il est toujours intraitable, comme c'est commun avec les cas finis de problèmes indéfinissables.
Le problème d'arrêt des machines d'état fini est résoluble (bien qu'il puisse prendre de nombreuses vie ..... de l'univers ), et toute machine que vous pourriez imiter est une machine à états finis. Il vient de gérer le programme et le nombre d'étapes est délimité par le nombre d'états possibles; Si ce nombre est dépassé sans arrêt, le programme ne s'arrêtera jamais, car il doit être dans une boucle.
Pratiquement parlant, la recherche de tout code est un problème beaucoup plus facile à moins que le code puisse utiliser des gotos calculés. Plutôt que d'exécuter le code, vous prenez simplement toutes les branches exactement une fois à chaque point de branche possible.
Même sans gotos calculé, ce n'est pas un problème facile. Par exemple, une branche conditionnelle peut toujours avoir sa condition ou éteinte. Dans cet exemple 8086: CLC; JC LBL Le programme ne saute jamais à lbl , de sorte que l'analyseur ne doit pas supposer lbl est le code. De même, dans CLC; Jnc lbl; Pop cs Le code passe toujours à lbl et donc pop cs est le code mort le plus probable (et c'est mieux, car cette instruction a été supprimée en 80186 en raison de être totalement inutile). Ces sauts étaient courants dans le code 6502, car 6502 manquaient d'une courte instruction relative inconditionnelle.
Je suis d'accord avec Larsman, et je pense que l'argument peut être fait précis. Premièrement, je dois d'accord pour dire que "trouver tout le code dans un binaire donné" signifie, dans ce contexte, disposer d'une seule fonction calculable qui détermine les octets dans une entrée binaire d'entrée correspond aux instructions exécutées.
Edit: Si quelqu'un n'est pas clair pourquoi il y a un problème ici, pensez au code de la machine obscurcie. Le démontage de ce code est un problème non trivial. Si vous commencez le démontage au milieu d'une instruction multi-octets, vous obtenez le mauvais démontage. Cela rompt non seulement l'instruction en question, mais généralement quelques instructions au-delà de cela. etc. Regardez-vous. (Par exemple, Google "Obfuscation et démontage").
Croquis de la stratégie pour rendre cela précis:
Premièrement, définissez un ordinateur théorique / machine de machine dans lequel un programme est codé dans Instructions binaires multi-bits, un peu comme le code de la machine sur des ordinateurs «réels», mais sont rendus précis (et tels qu'il contiennent complète). Supposons que le binaire code le programme et toutes les entrées. Cela doit tous être fait précis, mais suppose que la langue a une instruction (codée binaire codée) et qu'un programme s'arrête si et seulement s'il exécute une instruction «HALT».
Première, supposons-nous que la machine n'est pas capable de modifier le code de programme, mais a une mémoire dans laquelle travailler. (supposé infini dans des cas intéressants).
Ensuite, tout bit donné sera soit au début d'une instruction exécutée lors de l'exécution du programme, soit pas. (par exemple, il peut être au milieu d'une instruction, ou dans des données ou «code indésirable» - c'est-à-dire que le code qui ne sera jamais exécuté. Notez que je n'ai pas prétendu qu'elles sont mutuellement exclusives, comme par exemple une instruction de saut peut avoir une cible qui est au milieu d'une instruction particulière, créant ainsi une autre instruction qui, "sur la première passe", n'a pas ressemblé à une instruction exécutée.).
Définir ins (i, j) à Soyez la fonction qui retourne 1 si le binaire I a une instruction commençant à un bit-position J, qui s'exécute dans une exécution du programme codé par i. Définir ins (i, j) être 0 sinon. Supposons que INS (i, j) est calculable.
laisser halt_candidate (i) être le programme suivant: puisque nous interdisons le code auto-modificateur ci-dessus , ils seuls pour un programme de hall d'arrêt sont que pour y avoir une instruction «arrêtée» à une position J qui est exécutée. Par conception, halt_candidate (i) calcule la fonction d'arrêt. Ceci fournit un croquis très rugueux d'une direction de la preuve. C'est-à-dire que si nous supposons que nous pouvons vérifier si le programme I a une instruction à l'emplacement J pour tous J pour tous J, nous pouvons coder la fonction d'arrêt. Pour l'autre direction, il faut encoder un émulateur de la machine formelle, dans la machine formelle. Ensuite, créez un programme plus des entrées I et J qui émulent le programme I et lorsque une instruction à la position de bit J est exécutée, elle revient 1 et arrête. Lorsque toute autre instruction est exécutée, il continue à exécuter et si la simulation simule jamais une fonction «HALT» dans I, l'émulateur saute à une boucle infinie. Puis ins (i, j) équivaut à halt (émulateur (i, j)), et donc le problème d'arrêt implique le problème de recherche de code. Bien sûr, il faut assumer un ordinateur théorique pour que cela soit équivalent au problème de haltage célèbre insoluble. Sinon, pour un ordinateur "réel", le problème d'arrêt est solvable mais intraitable. pour un système qui permet un code auto-modificateur que l'argument est plus complexe, mais je m'attends à ce non différent. Edit: Je pense qu'une preuve dans le cas auto-modificateur consisterait à mettre en place un émulateur du système System-Plus-Auto-Modifiant-Code dans le code statique plus du système de données ci-dessus. Ensuite, arrêt avec le code auto-modificateur autorisé pour le programme I avec Data X, est identique à l'arrêt du système de données statique plus au système de données ci-dessus avec le binaire contenant l'émulateur, i et x comme code plus des données.
Que voulez-vous dire avec "Trouver le code"? Ingénierie inverse ou?
Ma compréhension par ce qu'il / elle signifie est que la recherche de la chaîne de code entière comprenant des dépendances. Recherchez la ligne avec ce texte dans la réponse sélectionnée pour voir le contexte.
Devriez-vous demander cela à théorique CS ?
Voir ma réponse. Trouver tout le code dans un programme est trivial tant que toutes les branches ont fixé des adresses cibles. Les pointeurs de fonction / code goto-calculé / auto-modification sont les complications possibles.