Je le savais, c'était un piège. Me voici maintenant sous le feu des projecteurs, la main tremblante sur mon clavier. Je vais essayer à mon tour d'être clair et précis, je sais que vous ne me pardonnerez aucune imprécision (et vous avez raison).
Il y a plusieurs démonstration de ce que j'appelle le «théorème de Turing» et qu'on appelle aussi «l'indécidabilité de l'arrêt des programmes». Et toutes sont entachées d'erreurs.
La première est celle que cite Nemerle plus haut. Dans cette démonstration, que représente le nombre N ?
Citation:
d'abord, examiner tous les programmes possibles de taille inférieure ou égale à N bits
Donc, en début de démonstration, N est le nombre de bits du programme. Mais, dans la suite de la démonstration:
Citation:
puisque pour exprimer le nombre N, il n'est besoin que de log2 N bits dans le système binaire
Par un glissement sémantique subtil, N devient le nombre représenté par le nombre de bits du programme. C'est à dire pour 16 bits, N = 65536 (et effectivement, log2(65536) = 16). Tout le reste de la démonstration est la conséquence de cette incohérence, et on aboutit bien évidement à une absurdité. Mais bien évidemment, un programme qui examine tous les programmes de taille inférieure à N bits doit faire au minimum N bits (en non pas log2(N)), de la même façon qu'un programme qui fait un traitement quelconque sur tous les entiers de moins de 16 bits (de 0 à 65535) doit faire au minimum 16 bits (la taille du compteur).
Pour pas qu'il y ait ambiguïté sur le vocabulaire:
Un nombre de N bits a besoin de N bits pour être représenté, pas un de moins.
Un nombre N a besoin de log2(N) bits pour être représenté. 255 peut être représenté sur 8 bits, 65535 sur 16.
La deuxième démonstration que je connaisse est celle qui avait été publiée dans la revue «*Pour la science*» d'octobre 2003, page 92 (pourquoi deux démonstrations ? La première n'était donc pas totalement digne de confiance ?). C'est en général celle qu'on trouve sur le net, sous des formes plus ou moins formelles:
Citation:
Envoyé par Pour la science
Le problème de l'arrêt. Turing démontre qu'il n'existe pas de machines prédisant, sans jamais se tromper et en un nombre fini d'étapes, si un calcul s'arrête. Voici son raisonnement qui utilise un argument analogue au paradoxe du menteur. On suppose qu'on détient une machine A qui, à chaque fois qu'on écrit sur son ruban des données n et s, indique au bout d'un nombre fini d'étapes si la machine de Turing numéro n s'arrête lorsqu'elle calcule en partant d'un ruban sur lequel la suite de symboles s a été inscrite. L'existence de cette machine A conduit à une contradiction. Connaissant la machine A, nous en construisons une autre, la machine B. Lorsqu'on inscrit n sur son ruban, elle s'arrête au bout d'un nombre fini d'étapes si la machine n avec la donnée s = n ne s'arrête pas et elle ne s'arrête pas si la machine numéro n soumise à la donnée s = n s'arrête (la machine B fait le même calcul que A soumise aux données n et s, mais au lieu d'indiquer «arrêt» ou «non-arrêt» part dans une boucle si A s'apprêtait à écrire «arrêt» et s'arrête si A s'apprêtait à écrite «non-arrêt»). Comme toute machine, B possède un numéro que nous nommons m. Soumise à la donnée m, la machine B se comporte de manière invraisemblable. Si elle s'arrête, c'est par définition de B que la machine m soumise à la donnée m ne s'arrête pas, ce qui est absurde, car B est elle-même la machine m et elle s'arrête. Si elle ne s'arrête pas, c'est par définition que la machine m, soumise à la donnée m s'arrête, ce qui est absurde pour la même raison: la machine m, c'est la machine B. Aucune machine prédisant l'arrêt ne peut donc exister
Et voici l'échange de mails que je vous avais promis:
Citation:
j'ai lu avec interêt et attention l'article de votre numéro d'Octobre intitulé "La barrière de Turing". D'autant plus d'interêt que je pense que le théorème de Turing (cause de cette "barrière de Turing") est faux. (...)
Raisonnons par l'absurde. Supposons que le théorème de turing soit vrai. Alors, le théorème suivant, basé sur le même principe, est également vrai. Il démontre qu'il n'existe pas de machine prédisant, sans jamais se tromper et en un nombre fini d'étapes, si un programme passe par un état donné ou pas:
On suppose qu'on détient une machine A qui, à chaque fois qu'on écrit sur son ruban des données n et s, indique au bout d'un nombre fini d'étapes si la machine de Turing numéro n passe par l'état s. La machine A écrit "OUI" on "NON" (ou exclusif) selon que n passe par l'état s ou pas. L'existence de cette machine A conduit à une contradiction. Connaissant la machine A, nous en construisons une autre, la machine B. La machine B fonctionne exactement comme la machine A, sauf qu'elle écrit "NON" lorsque A écrivait "OUI", et vice versa. Comme toute machine, B possède un numéro que nous nommons m. Essayons de savoir si la machine B passe par l'état "écrire OUI". Pour cela, soumettons à B la donnée m. La machine B se comporte alors de manière invraisemblable: si B affiche "OUI", alors cela signifie que m ne passe pas par l'état "écrire OUI" (puisque la machine B est inversée par rapport à la machine A), ce qui est absurde car B est elle-même la machine m, et qu'elle vient juste d'écrire "OUI", donc de passer par l'état "écrire OUI". Si B affiche "NON", cela signifie que m passe par l'état "écrire OUI", ce qui est également absurde pour la même raison: la machine m, c'est la machine B, et elle a écrit "NON", donc elle n'est pas passée par l'état "écrire OUI" (le OU étant exclusif, B ne peut pas ecrire "OUI" et "NON" en même temps). Aucune machine prédisant le passage d'une autre machine par un état donné ne peut donc exister.
Or, le résultat précédent est bien évidemment faux. Non seulement il remettrait en cause l'existence des "machines universelles", mais de plus, on sait que n'importe quel compilateur contient un programme LINK dont la fonction est, entre autre, de détecter les parties de programme inutilisées (indiquer si le programme n passe par l'instruction s) pour éliminer le code inutile. Donc ce théorème est faux et le théorème de Turing est faux également.
Alors, où est l'erreur ? Nous avons fait deux hypothèses. La première, c'est que la machine A existe (hypothèse de départ). La seconde, moins évidente, est que nous pouvons appliquer m à la machine B. Or, qu'est-ce que m ? c'est un ensemble de données {n, s} où n = B et s = m. Donc, en appliquant m à B, nous y appliquons en fait les données {B, m}. Donc les données {B, {B, m}}, donc les données {B, {B, {B, m}}}, et ainsi de suite. En d'autre termes, nous appliquons à la machine B la machine B appliquée à la machine B appliquée à la machine B etc... Par un artifice de raisonnement, nous avons introduit une dimension infinie dans une démonstration sur des machines traitant des données finies. Inutile de dire qu'il ne faut pas s'étonner si les conséquences que nous en déduisons sont absurdes et invraisemblables.
Citation:
* Cher Monsieur,
Le théorème suivant :
*>* il n'existe pas de machine prédisant, sans jamais se
*> tromper et en un nombre fini d'étapes, si un programme passe par un état
*>* donné ou pas:
est vrai et ce n'est pas une nouveauté.
Cela ne remet pas en cause l'existence de machines de Tunrig universelle.
qui simulent tout programme (car quand elles simulent un programme qui ne termine
pas, les machines universelles ne terminent pas non plus.)
Quand au programme LINK j'imagine qu'il teste simplement si une
partie du programme est utilisée lors d'une ou plusieurs utilisations
particulière et ayant terminée ce qui est tout autre chose que de tester
a priori avant de savoir si le programme va terminer si une partie X du code
sera utilisée. La difficulté provient des programme qui ne terminent pas.
(...)
Citation:
Messieurs,
*
*** Je vous remercie de l'importance que vous avez bien voulu apporter à mon mail, ainsi que de la rapidité de votre réponse.
*
*** (...)
*
*** Cependant, si vous avez encore quelques minutes à m'accorder, je voudrais avoir votre opinion sur la démonstration suivante. Est-elle juste ? Est-ce également un résultat connu ?
*
*
*** Considérons le sous-ensemble des machines de Turing s'arrêtant dans un temps fini. D'accord, on ne sait pas construire ce sous ensemble, néanmoins il doit exister. Dans ce sous-ensemble, interessons nous à celles dont le résultat final est un nombre (peu être toutes ? peu importe). Appelons ce dernier sous-ensemble T (comme Turing).
Existe-il une machine de Turing qui indique si ce résultat final est pair ou impair ?
*
*** Supposons que nous possédions une machine A qui, appliquée à n'importe quelle*autre machine X appartenant à T, renvoie 1 si le résultat final de X est impair, 2 si ce résultat est pair. A s'arrête en un temps fini et son résultat final est un nombre. A appartient donc à T.
*** Connaissant A, construisons la machine B, qui renvoie 1 si le résultat final est pair, et 2 sinon. B appartient également à T.
*** Comme toute machine, B possède un numéro que nous nommons m. Appliquons m à B. que se passe-t-il ?
*** - Soit B renvoie 1, ce qui veut dire que le résultat de m est pair. C'est absurde puisque m c'est B, et que B renvoie 1 qui est impair.
*** - Soit B renvoie 2, ce qui veut dire que le résultat de m est impair. C'est absurde puisque m c'est B, et que B renvoie*2 qui est pair.
*** Donc A n'existe pas.
*
*** Indépendamment du traitement et des problèmes d'arrêt, il n'existerait aucune machine de Turing capable de dire si un résultat est pair ou impair ? Hum, hum ! Plutôt étrange, non ? Qu'en pensez-vous ?
Citation:
*Cher* Monsieur
*Votre démonstration est juste et bien connue (dans un de mes livres (Logique informatique et paradoxes page 14) je
mentionne ce problème a propos du théorème de Rice.
>*** Considérons le sous-ensemble des machines de Turing s'arrêtant dans un temps fini. D'accord, on ne sait pas construire ce sous >ensemble, néanmoins il doit exister. Dans ce sous-ensemble, interessons nous à celles dont le résultat final est un nombre (peu être >toutes ? peu importe). Appelons ce dernier sous-ensemble T (comme Turing).
>existe-il une machine de Turing qui indique si ce résultat final est pair ou impair ?
* Oui bien sur : on fait trouner la machine jusqu'à ce qu'elle s'arrete et on regarde ce qu'elle a produit.
Apliquée a elle-même cette machine ne s'arretera pas car si elle s'arretait votre raisonnement marcherait
et conduirait donc a une contradiction.
Citation:
Monsieur,
*
(...)
Je reste toutefois convaicu que le théorème de Turing est faux. Ne voulant pas abuser de votre temps, je vais tenter une toute dernière fois de vous convaincre:
*
Il existe au moins une catégorie de machines de Turing s'arrêtant en un temps fini: ce sont les composants electroniques. L'état des transistors (bloqués ou passants) représentent l'état de la machine de Turing, et la présence ou non de courant dans les fils représentent le ruban. Ils s'arrêtent forcément dans un temps fini car la tension de sortie est toujours mesurable. Soit il y a du courant, soit il n'y en a pas.
*
Démontrons par la "méthode Turing" qu'il ne peut pas exister de composant ayant une tension de sortie égale à l'entrée:
*
Démonstration:
*
Supposons que nous ayons un composant A tel que la sortie*soit égale à l'entrée (Fonction NOP). Construisons un composant B tel que la sortie soit inversée par rapport à l'entrée (Fonction NOT). Appliquons le composant B à lui-même (c'est à dire, soudons la broche de sortie avec l'entrée). Mesurons la tension de sortie. Que voyons-nous ?
Soit il y a du courant, ce qui est absurde car la sortie est reliée à l'entrée, et que s'il y a du courant en entrée, il ne doit pas y en avoir en sortie.
Soit il n'y a pas de courant, ce qui est également absurde pour la même raison: s'il n'y a pas de courant en sortie, il n'y en a pas en entrée et donc il devrait y en avoir en sortie.
Donc les composants A et B ne peuvent pas exister. CQFD.
*
Sauf que ces composants A et B existent, et sont commercialisés sous les références LS 07 et LS 04 (circuits TTL).
*
Donc, soit cette démonstration est juste, et il va falloir que tous les électroniciens arrêtent d'utiliser ces composants, il va aussi falloir convaincre tous les utilisateurs de radios, télévisions, machines à laver et ordinateurs contenant ce type de composant de jeter aux ordures tous ces appareils, car ils ne peuvent pas fonctionner, c'est scientifiquement prouvé.
*
Soit cette démonstration est fausse, et, quelle qu'en soit la raison, le théorème de Turing le sera aussi pour la même raison.
*
Objections possibles:
*
1) Les composants electroniques ne sont pas des machines de Turing. Le fait que les composants soient ou non des machines de Turing, susceptibles de s'arrêter ou non dans un temps fini ou pas, n'entre pas en ligne de compte dans la démonstration.
*
2) Un composant*LS 04*relié à lui-même entre dans une configuration instable, oscillant indéfiniment entre un niveau haut et un niveau bas avec une période correspondant au temps de basculement des transistors. Exact. Mais cela ne signifie pas que ce composant n'existe pas.
*
3) Le point*précédent révèle que nous avons oublié de prendre en compte le facteur Temps. Et ça s'applique également aux machines de Turing. Je ne pense pas qu'on puisse fabriquer des machine de Turing effectuant un quelconque traitement dans un espace de temps nul.
Citation:
Cher monsieur,
toute revue de vulgarisation scientifique que nous soyons, nous ne sommes
pas fonde a juger de la validite d un enonce scientifique. puis je me
permettre de vous conseiller, si vous le croyez necessaire, de vous
retourner vers une ''autorite" competante en la matiere, comme l Academie
des Sciences par exemple. Vous trouvez la, toutes les personnes qu il faut
pour valider une demonstration, si celle ci s avere exacte.
L'académie des sciences, pourquoi pas ? Voici leur réponse:
Citation:
Monsieur
Merci de votre mail. Mais l'Academie ne
peut pas faire des recherches bibliographiques, que les auteurs de
ces demandes soient des scientifiques, des chercheurs,
des enseignants, des journalistes, ou toute autre personne.
