Ordinateurs de choses ne peuvent jamais faire

Original: http://www.efgh.com/math/impossible.htm

LOGO
Philip J. Erdelsky
Tout d’abord publié dans le Journal du Dr. Dobb’s mai 1987


S’il vous plaît e-mail des commentaires, des corrections et des ajouts au webmaster à  [email protected].

 

Quiconque a vu les énormes améliorations dans les ordinateurs dans les 40 dernières années peut avoir l’impression que les ordinateurs sera finalement en mesure de résoudre tous les problèmes bien définis. Progrès dans la compréhension du langage et d’autres formes de l’intelligence artificielle a été décevante, mais le langage humain est plein d’ambiguïtés, donc ce n’est pas un problème bien défini. Jeu d’échecs, quant à elle, est très bien définie. Bien qu’il était autrefois considéré comme le summum de l’activité intelligente, ordinateurs peuvent maintenant jouer aux échecs mieux que tous, mais quelques joueurs humains.
Certains problèmes, même si bien défini, sont trop volumineux pour être résolu dans un délai raisonnable même sur nos ordinateurs plus grands. Mais sûrement, si un ordinateur pourrait être libéré de toutes les limitations sur le temps et la mémoire, ne pouvait pas il résoudre tous les problèmes bien définis ?
La surprenante réponse à cette question, qui était connue pour mathématiciens avant même que les premiers vrais ordinateurs ont été construits, est pas. Il y a des choses, qu’aucun ordinateur ne peut jamais faire parce qu’il peut être prouvé qu’il n’y a aucun algorithmes pour les fairecomme il n’y a aucun moyen à la place un cercle avec une règle et le compas.
Ces choses ne sont pas simples curiosités mathématiques. Ils sont des choses que les programmeurs voudrais ont leurs ordinateurs à faire pour eux et que les fournisseurs d’outils de développement logiciel souhaite incorporer dans leurs débogueurs. Programmes scientifiques ordinateur comprennent généralement le sujet des fonctions uncomputable, mais les programmeurs qui ne sont pas majors de science informatique parfois demandent l’impossible sans s’en rendre compte.
Alan Turing en 1935 a demandé s’il y a une méthode par laquelle un programme d’ordinateur peut déterminer si n’importe quel autre programme d’ordinateur s’arrête. Il s’agit de la célèbre « problème de l’arrêt. » Turing a montré qu’il n’a pas de solution.
Un débogueur avec cette capacité serait certainement utile. Omission d’arrêter normalement est une forme courante de l’échec du programme. En outre, le débogueur peut être appliqué successivement aux parties du programme a échoué à isoler la partie qui accroche.
Il n’est pas évident que cet un débogueur est impossible. Bien sûr, le débogueur ne peut pas juste le programme pour voir si elle s’arrête. Si le programme n’est pas arrêtée, le débogueur peut exécuter pour toujours sans déterminer que c’est le cas. Ou il pourrait abandonner tout comme le programme est sur le point de prendre fin, comme les programmeurs humains font parfois. À un moment donné, le débogueur devra être en mesure de dire, « Aha ! Cette boucle est infinie!” Il semble comme si un débogueur habilement écrit, avoir tous les outils des langages de haut niveau modernes à sa disposition, pourrait être en mesure de le faire.
La preuve de l’impossibilité repose sur l’argument suivant. Si vous avez un débogueur qui peut résoudre le problème de l’arrêt, donné sans limites de temps et de la mémoire, puis vous pouvez utiliser le même code pour faire le débogueur à faire d’autres choses, dont certaines sont contradictoires et donc impossible.
Le langage informatique particulière n’est pas important. Si vous pouvez résoudre le problème de l’arrêt pour une seule langue, vous pouvez le résoudre pour un autre. Il suffit d’utiliser un compilateur ou à un autre programme de traduction avant de résoudre le problème de l’arrêt. Notez que le fait de traduire un programme en langage assembleur pour un langage de niveau supérieur est assez facile, même si le programme de l’objet peut être inefficace. L’objectif, cependant, est de montrer qu’une solution pour le problème de l’arrêt est impossible, pas uniquement inefficace.
Turing lui-même a proposé une machine minime qui a fini par être appelé la Machine de Turing. Sa mémoire était censé pour être infiniment longs, mais seulement un peu large, et la machine avait seulement un accès séquentiel, comme avec un ruban. Le langage de programmation a été essentiellement un organigramme avec seulement quelques commandes de base. Néanmoins, Turing a montré que sa machine était capable d’émuler n’importe quelle autre machine, donné assez de temps et d’un logiciel adapté. Une telle interprétation n’est pas nécessaire pour nos besoins-vous pouvez imaginer que l’ordinateur est programmé dans un langage de haut niveau familier.
Considérons maintenant le problème de déterminer si un programme peut imprimer une chaîne spécifiée S (avec ou sans autre production). Si vous pouvez résoudre le problème de l’arrêt, vous pouvez résoudre ce problème. Il suffit de remplacer chaque instruction print dans le programme avec une routine qui n’envoie pas la sortie à l’imprimante, mais conserve la trace des sortie et s’arrête lorsque la chaîne S apparaît. Ensuite, pour empêcher le programme de mettre un terme pour toute autre raison, remplacez toutes les déclarations d’arrêt au programme avec des boucles infinies. Alors résoudre le problème de l’arrêt pour le résultat.
Un tel programme serait utile en soi, parce que de nombreuses erreurs d’exécution produisent messages distinctifs, et il serait utile de prévoir à l’avance que ces erreurs seront produisent.
Parce que cela s’applique à n’importe quelle chaîne S, vous pouvez également déterminer si un programme imprime une copie de lui-même. Ce n’est pas aussi curieux qu’il semble à première vue. Il est facile d’écrire un programme de 1 000 caractères qui imprime toutes les combinaisons de 1 000 caractères, y compris lui-même. En fait, 1 000 caractères est probablement une surestimation du nombre de caractères requis dans les langages de plus haut niveau.
Maintenant, vous pouvez écrire un programme pour faire les choses suivantes. Tout d’abord, générer, un par un, tous les programmes possibles. La meilleure façon de procéder est de générer toutes les chaînes et vérifier chacun d’entre eux pour voir il s’existe un programme. Compilateurs pour cela lors de l’enregistrement syntaxe. Ensuite, vérifiez chaque programme pour voir si elle imprime une copie de lui-même. Enfin, imprimer une copie de tous les programmes qui ne s’imprime pas sur une copie de lui-même.
Ce programme, en train de générer tous les programmes, générera éventuellement lui-même. Il s’imprime une copie de lui-même ? Dans l’affirmative, il se brise la règle en imprimant une copie d’un programme qui imprime une copie de lui-même. Si il n’est pas le cas, il se brise la règle par défaut imprimer une copie d’un programme qui ne s’imprime pas sur une copie de lui-même. Cette contradiction mortelle prouve que le problème de l’arrêt n’a pas de solution.
Vous pouvez le reconnaître comme le paradoxe de Russell (le jeu de tous les ensembles qui ne contiennent pas eux-mêmes) ou le paradoxe du Barbier (le Barbier qui se rase tout homme qui ne pas se raser).
N’importe quel problème qui peut convertir le problème de l’arrêt, tels que le problème de la sortie de la chaîne, un débogueur est également insoluble. Quelques autres exemples évidents sont :
déterminer si un programme atteindra un point spécifié (programmeurs Ada : c’est pourquoi PROGRAM_ERROR doit être une erreur d’exécution, pas une erreur de compilation)
déterminer si une variable est initialisée avant d’être utilisé
déterminer si un segment donné du code est inaccessible et qu’il ne sera jamais exécuté
déterminer si les deux programmes font la même chose
Bien sûr, un débogueur ou le compilateur permet parfois de prédire ces erreurspar exemple, code inaccessible peut parfois être identifié au moment de la compilation. Mais il n’existent pas de solutions universelles pour ce genre de problèmes.
L’impossibilité de déterminer si les deux programmes font la même chose signifie qu’il est toujours possible de vaincre un certain type de cheval de Troie. Lors d’une conférence, réimprimée dans les avis de l’ACM (août 1984), Ken Thompson a fait valoir qu’il pourrait mettre un cheval de Troie dans un compilateur C qui serait miscompile l’instruction login afin de lui permettre l’accès à n’importe quel système Unix compilé avec elle, et elle serait miscompile le compilateur C pour insérer une copie de lui-même. Le cheval de Troie elle-même n’apparaîtra pas dans le code source du compilateur C. Dans une lettre à l’éditeur, Steve Draper a fait remarquer que tel un cheval de Troie peut être défait en paraphrasant le compilateur C (écriture code différent qui fait la même chose) et en recompilant ensuite. Aucun cheval de Troie ne peut reconnaître infailliblement paraphrasés programmesd’où il y a toujours une paraphrase qui va battre le cheval de Troie.
Ma propre opinion dans cette affaire, c’est que, à moins que le cheval de Troie ont été habilement écrites, la plupart des paraphrases il irait et en fait il serait probablement être défait finalement de maintenance logicielle normale. Toute puce de cheval de Troie assez pour reconnaître la plupart des paraphrases serait probablement beaucoup plus grande que le reste du compilateur C. Vous n’obtiendriez jamais il à travers les portes.
Le problème de l’arrêt est intimement lié à deux autres problèmes qui ont été posés par le mathématicien David Hilbert en 1900. Y a-t-il une preuve formelle ou une réfutation pour chaque énoncé mathématique ? Y a-t-il un algorithme pour trouver des preuves ?
La première question a été répondue par la négative par Kurt Gödel en 1931. La preuve de Gödel est complexe, mais si vous acceptez l’impossibilité de résolution du problème de l’arrêt, il peut être prouvé tout simplement. Si un programme particulier s’arrête est un énoncé mathématique. En fait, de nombreux théorèmes mathématiques sont déjà des cas particuliers du problème de l’arrêt parce que vous pouvez écrire un programme pour rechercher des contre-exemples et arrêter quand il en trouve un. Ce théorème est équivalent à l’affirmation selon laquelle le programme ne s’arrête jamais.
S’il y avait toujours une preuve formelle ou réfuter l’affirmation selon laquelle un programme s’arrête, puis vous pourriez simplement générer toutes les épreuves (plus ou moins comme le programme décrit précédemment généré tous les programmes) jusqu’à ce que vous avez trouvé une preuve ou une réfutation. Cela réglerait le problème de l’arrêt. Parce que le problème de l’arrêt est en général insoluble, il doit y avoir au moins un énoncé mathématique de ce genre qui est indécidablec’est-à-dire il ne peut pas être formellement prouvé ou réfuté.
Cela montre qu’il est en général impossible de prouver qu’un programme fonctionne. Programmes spécifiques ou des catégories limitées des programmes peuvent être prouvés de faire certaines choses, mais il n’y a aucun moyen de le faire pour chaque programme.
Étant donné que certains énoncés mathématiques sont indécidables, est-il un programme, le « programme de décidabilité, » qui peut dire si tout énoncé mathématique est decidable, même sans décider si c’est vrai ou faux ? Comme vous l’avez peut-être deviné le ton de cet article, la réponse est encore une fois aucun. Si vous avez un programme de décidabilité, vous pouvez prendre n’importe quel programme et demander si elle s’arrête. Puis appliquer le programme de la décidabilité à cette question. Si la question est decidable, une recherche de toutes les épreuves est le prouver ou réfuter il. Si la question est indécidable, puis le programme jamais s’arrête ; dans le cas contraire, vous pourriez s’avérer qu’il s’arrête en le faisant simplement marcher jusqu’à ce qu’il s’arrête.
Par conséquent, prouver le théorème programmes, toutefois réussis, qu’ils soient dans des zones limitées, ne peuvent jamais prouver tout. Certaines choses doivent toujours rester au-delà de leur portée.
Ces arguments ne sont pas rigoureux dans le sens mathématique car trop bien a été omis. Une grande partie de Turing et de Gödel travail impliquée formalisation des concepts de « calcul » et la « preuve » au point leurs arguments seraient acceptées par les mathématiciens.
Vous mai ont déjà repéré une hypothèse tacite qui ne correspond pas à la réalité. Les programmes ne sont pas contraints par les limites de la mémoire. Si un programme a une limitation de la mémoire, alors le problème de l’arrêt peut en théorie être résolumais seulement par un programme avec une mémoire beaucoup plus grande.
C’est comment il peut être fait. Un programme avec une limitation de la mémoire a seulement un nombre fini d’États. Un débogueur peut seule étape il, suivi des États qu’il occupe. Si elle occupe le même état deux fois avant de mettre un terme, il répétera indéfiniment la même séquence des États et ne s’arrêtera jamais.
Pour cela, le débogueur a besoin de suffisamment de mémoire pour suivre les États dans lesquels que le programme est occupé. Un bit est requis pour chaque état possible, mais le nombre d’États possibles pour même un programme simple est vraiment ahurissant. Toutes les combinaisons de bits dans la mémoire sont un état différent. Un programme avec seulement 1 024 octets de mémoire a donc au moins 2 États (1024 x 8) en raison de la configuration de la mémoire seule, sans parler des drapeaux et registres. Ce nombre de tongs ne rentrait pas dans tout l’univers connu. On peut donc dire que le problème de l’arrêt n’a pas de solution même dans ce cas.
Il devrait être clair, ensuite, qu’il n’y a certainement des limites à ce que l’intelligence artificielle peut accomplir et que mathématiciens et emplois de programmeurs ne peuvent jamais être complètement automatisées. (C’est un grand réconfort pour moi parce que je suis un programmeur et un mathématicien.
Seules les solutions parfaites sont impossibles, cependant. On peut encore faire valoir, et il est soutenu par certains, que les programmes d’intelligence artificielle sera finalement en mesure de résoudre tous les problèmes que l’esprit humain peut résoudre, au moins le même taux de réussite. Et si la seule exigence est des solutions pratiques, pas parfait de solutions, puis beaucoup d’intéressant mais théoriquement insolubles problèmes peuvent être résolus.