Discussion :

[neuromencien]

Bonjour.

Je voudrais savoir s'il est possible de calculer de façon statique les chemins d'exécution d'un programme?

J'ai recherché sur Google et je tombe sur beaucoup de thèses et de documents de recherche qui parlent du calcul du chemin d'exécution le plus long, mais ce n'est pas ce que je recherche. Je voudrais être capable de calculer tous les chemins d'exécution possible.

J'ai déja essayé de créer un prototype mais il ne fonctionne pas correctement.

Par exemple si on a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
if (a == b) {
   //Une action A
}
else {
   //Une action B
}
 
//Une action C
 
if ((a == b) && (b < 2)) {
   //Une action D
}

Les chemins d'exécution possible sont :
A -> C -> D,
A -> C,
B -> C.

Mon prototype n'est déja pas capable de détecter que D ne peut suivre C que dans le cas ou l'on a pris la branche qui ne commence pas par A. Comment faire comprendre à mon programme que les deux conditions ont une partie commune? D'autant plus que le nom des variables peut changer voir leur valeur. Un

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

b++;

placé avant la dernière condition change complètement la liste des chemins d'exécution.

Est ce que tout celà est possible, ou est ce que ça relève de la SF? Et si c'est possible, ou peut-on trouver infos sur la façon de faire ça?

Merci d'avance pour vos réponses.

[10_GOTO_10]

Si un programme était capable de calculer la longueur du chemin le plus long dans un algorithme, il serait capable de déterminer si un programme boucle ou pas (longueur du chemin le plus long = infini). Or, un certain Mr Turing a démontré le contraire, donc il semblerait que ce soit impossible...

A condition que le théorème de Turing soit juste. Et personnellement, sans vouloir ouvrir une polémique, j'ai de sérieux doutes sur cette démonstration.

[Nemerle]

Allons-allons... sa démonstration est en béton armé!

[nletteron]

J'allais le dire.

On en revient à l'éternel problème de la décidabilité/indécidabilité d'un programme. Je te conseille tous les ouvrages qui trainent là dessus, tu risques d'être surpris sur le nombre de choses qu'on ne peut pas faire en informatique . Ensuite tout ce qui concerne les cours de calculabilité. Tu seras surpris aussi.

Théorème de Turing ? Ca me dit rien par contre.

Je pencherais plutôt pour le théorème de Gödel ou de Rice qui suffise à prouver qu'on est dans l'impossibilité à partir d'une propriété non triviale donnée de savoir si elle se termine ou non.

Tu pourras calculer le chemin d'un programme uniquement si ton algorithme est "décidable" (impropre au niveau du terme).

[10_GOTO_10]

Allons-allons... sa démonstration est en béton armé!

Aïe, ça y est. J'ai mis le doigt dans l'engrenage, j'aurais pas dû.

Il y a quelques années, j'ai eu un long échange de mails avec quelques spécialistes de la chose, qui n'avaient pas conclu sur le fond, mais plutôt avec des réponses du genre "mais qui es-tu, pauvre c.n, pour remettre en cause cette démonstration".

Sans entrer dans les détails, cette démonstration fait une joyeuse confusion entre un programme (suite d'instructions) et une instance de programme (instructions + données initiales). Elle conclut qu'un certain programme se termine et ne se termine pas à la fois. D'où contradiction, donc ce programme n'existe pas. Or, il ne s'agit pas de programmes mais de deux instances du même programme, et l'une peut très bien s'arrêter et pas l'autre. C'est comme si on disait que si W.....s plante sur un PC et pas sur un autre, il n'existe pas...

[nletteron]

L'engrenage m'intéresse perso .

J'aimerais bien que tu rentres dans le détail justement. J'aurais sans doute des questions là dessus. Ca m'intéresse fortement puis ça fait longtemps que j'ai pas eu le plaisir de palabrer de calculabilité.

[borisd]

Juste pour répondre à la question initiale, il semble que dans le cas général, la seule chose que tu puisses faire est de construire un émulateur (ou pourquoi pas te trouver un ordinateur ) et lancer ton programme dessus avec tous les jeux d'entrée possibles.
Après, tu peux certainement, heuristiquement, détecter un certain nombre de chemins et effectuer un certain nombre de déductions logiques qui invalideront des chemins impossibles. Et là, si tu considères que théoriquement ton programme ne sera pas parfait, tu peux en faire un qui s'approche de la perfection en, par exemple, tronquant simplement les arbres de recherche...

[10_GOTO_10]

L'engrenage m'intéresse perso .

Bon, ben si ça intéresse du monde...

De mémoire, j'avais, sur le même principe de démonstration, prouvé toutes sortes de choses toutes plus absurdes les unes que les autres (qu'un programme capable de dire si un nombre est pair ou pas n'existe pas), ce qui prouve que la démonstration est fausse. J'avais trouvé un contre-exemple: un langage de programmation (donc une machine de Turing, puisque tout automate à états finis est une machine de Turing) dans lequel il était très facile de dire si un programme s'arrêtait ou pas.

Je n'ai pas ces mails sous la main, mais ce soir je peux les retrouver. Je les mettrais ici.

[Nemerle]

un exemple de présentation de la preuve (http://www.cs.auckland.ac.nz/CDMTCS/chaitin/paris.html):

Turing : il n'existe pas d'algorithme général permettant de savoir si un programme s'exécutera en un temps fini ou non
Sans entrer dans les détails, on peut esquisser une façon de démontrer que le problème de l'arrêt d'un programme est insoluble, en faisant un raisonnement par l'absurde. Supposons qu'il existe une procédure mécanique permettant de savoir, pour tout programme, si celui-ci s'exécutera en un temps fini. Cela implique alors qu'il est possible de construire un programme (P) incorporant la donnée d'un nombre entier N, et effectuant les tâches suivantes : d'abord, examiner tous les programmes possibles de taille inférieure ou égale à N bits (tout programme informatique pouvant être traduit en une suite de chiffres binaires, 0 ou 1, appelés bits, et constituant chacun une unité d'« information ») et déterminer lesquels d'entre eux s'arrêtent en un temps fini. Ensuite, simuler l'exécution de tous ces derniers et considérer leurs résultats. Supposons que les résultats soient des nombres entiers positifs ou nuls, ce que l'on peut faire sans perte de généralité puisque tout programme produit comme résultat une suite de 0 ou 1, laquelle peut toujours être interprétée comme représentant un entier positif ou nul. La dernière tâche que l'on assigne alors au programme (P) est de prendre le résultat le plus élevé produit par tous les programmes qui s'arrêtent en un temps fini et dont la taille ne dépasse pas N bits, et de calculer le double (par exemple) de ce résultat maximal.
Examinons maintenant la situation à laquelle on aboutit. Le nombre N est l'essentiel de l'information incluse dans le programme (P) que l'on vient de décrire. Par conséquent, la taille de ce programme est de l'ordre de log2 N bits, puisque pour exprimer le nombre N, il n'est besoin que de log2 N bits dans le système binaire (par exemple, le nombre 109 s'écrit 1101101 dans le système binaire, ce qui nécessite donc 7 ≈ log2 109 bits). Bien sûr, le programme (P) doit aussi contenir d'autres instructions permettant d'énumérer et de simuler l'exécution de tous les programmes de taille inférieure à N bits, mais le résultat n'est pas fondamentalement modifié : le programme (P) a bien une taille d'ordre log2 N bits (donc inférieure à N bits). Ce point nécessite peut être un peu plus d'éclaircissements : naïvement, on aurait tendance à penser que (P) doit contenir en lui tous les programmes de moins de N bits. Mais ce n'est pas parce que (P) simule leur exécution qu'il doit les contenir ! Pour donner une image, un programme chargé d'effectuer la somme de tous les entiers de 1 à 1 000 n'a pas besoin de contenir en mémoire tous les entiers de 1 à 1 000 : il les produit successivement au fur et à mesure du calcul de la somme. Cela pour faire comprendre que N est bien l'ingrédient principal du programme (P). Mais revenons à notre propos ; par construction, ce programme produit un résultat qui est au moins deux fois plus grand que celui produit par tout programme dont la taille est inférieure à N bits : il y a contradiction, puisque (P) fait lui-même partie de ces programmes et qu'il donnerait donc un résultat au moins deux fois plus grand que celui qu'il fournit lui-même... L'hypothèse de départ (l'existence de (P)) est alors fausse. Le problème de l'arrêt d'un programme est donc insoluble, ce que nous venons de montrer en utilisant un point de vue de la théorie de l'information.

C'est clair, net et concis (du moins pour un informaticien , on attendrait plus de rigueur d'un logicien ou mathématicien). Dans le même style la preuve du théorème d'incomplétude de Gödel, écrit purement en formalisme mathématique, a été publié chez pour la science.

[millie]

Le premier théorème que tu peux montrer est qu'il existe des problèmes non décidables = non résolubles par une machine de turing = non résolubles par un algorithme.

On démontre que l'ensemble des algorithmes est dénombrable et que l'ensemble des problèmes ne l'est pas (l'ensemble des parties d'algorithme est en bijection avec l'ensemble des problèmes me semble t-il). Et donc on montre qu'il existe une infinité de problèmes qui sont indécidables.

Après, on peut en trouver, comme la détermination de la terminaison d'un algorithme sur une instance donnée (cité plus haut)

[Jean-Marc.Bourguet]

Je voudrais savoir s'il est possible de calculer de
façon statique les chemins d'exécution d'un programme?

Théoriquement impossible (on a déjà cité le problème de l'arrêt). Même si
c'était théoriquement possible, résoudre le problème exactement aurait un
intérêt pratique limité pour cause de complexité trop grande (pire que
NP-Complet).

Pratiquement on peut arriver à des sur-ensembles et des sous-ensembles de
la solution exacte avec une complexité raisonnable. C'est utilisé dans la
phase d'optimisation des compilateurs.

J'ai déja essayé de créer un prototype mais il ne fonctionne pas
correctement.

Par exemple si on a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
if (a == b) {
   //Une action A
}
else {
   //Une action B
}
 
//Une action C
 
if ((a == b) && (b < 2)) {
   //Une action D
}

Les chemins d'exécution possible sont :
A -> C -> D,
A -> C,
B -> C.

Mon prototype n'est déja pas capable de détecter que D ne peut suivre C que
dans le cas ou l'on a pris la branche qui ne commence pas par A. Comment
faire comprendre à mon programme que les deux conditions ont une partie
commune?

Regarde ce qui ce fait pour l'optimisation "common sub-expression". Une
autre chose que tu peux chercher est "symbolic evaluation".

[Jean-Marc.Bourguet]

Bon, ben si ça intéresse du monde...

Ça m'intéresse aussi.

J'avais trouvé un contre-exemple: un langage de programmation (donc une machine de Turing, puisque tout automate à états finis est une machine de Turing)

Non.

dans lequel il était très facile de dire si un programme s'arrêtait ou pas.

Quand on cherche à le faire, il est facile de définir des langages pour lesquels le problème de l'arrêt est résoluble. On se limite bien à des langages avec un typage statique sans trop perdre de puissance d'expression, en tout cas en considérant que ce qu'on perd en expressivité, on le gagne en sécurité.

[10_GOTO_10]

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 ?

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:

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:

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:

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.

* 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.

(...)

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 ?

*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.

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.

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:

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.

[borisd]

Ce que tu dis a l'air longuement réfléchi et je ne dispose pas (encore, mais qui sait peut-être qu'un jour?) de la culture scientifique nécessaire pour juger tes propos. Néanmoins, cet argument ne me semble pas valable :

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

En effet, un linker est capable d'éliminer du code non utilisé selon certaines conventions d'appel. Il est très facile d'écrire, dans un aussi beau langage que le C, un programme doté d'une portion de code P, procédure ou autre, non appelée explicitement, et pourquoi pas stockée dans une section de données du programme.
Il est alors facile d'écrire un autre bout de code, appelé explicitement, lui, qui calcule l'adresse de P (pourquoi pas une procédure qui résout un problème d'optimisation quelconque, ou qui calcule une suite convergeant vers l'adresse de P...). La portion de code P peut alors être appelée par le programme par un saut dynamique vers l'adresse calculée.
Le seul linker capable de prédire l'utilisation de la portion P devra émuler l'exécution du programme pour pouvoir prédire l'adresse du saut, ou exécuter lui-même une procédure équivalente de résolution du problème amenant à l'adresse de P.

Un autre contre-exemple est le cas d'un programme auto-générant son code (décryption du code...). Un linker est incapable de savoir si le programme va exécuter une portion de code qui n'existe même pas dans les fichiers compilés qu'on lui demande de lier; il n'est capable de traiter que les cas d'appels explicites. Lors de la création de programmes auto-modifiant (protection de code, virus polymorphes...), les fonctions de "nettoyage" du code non utilisé ne peuvent pas être utilisées car elles ne gèrent qu'un ensemble statique d'appels de procédures qui sont explicitement connus dès la compilation.

Cet argument n'est à mon avis valable que si on considère le sous-ensemble des programmes obéissant à ces règles d'appel, auquel on ne peut à mon avis rapporter l'ensemble des programmes. Je crois que cela illustre la remarque de Jean-Marc Bourguet, si on la transpose au problème du passage d'un programme par un état donné :

Quand on cherche à le faire, il est facile de définir des langages pour lesquels le problème de l'arrêt est résoluble. On se limite bien à des langages avec un typage statique sans trop perdre de puissance d'expression, en tout cas en considérant que ce qu'on perd en expressivité, on le gagne en sécurité.

[nletteron]

Argument de la diagonale de Cantor.

Preuve en termes imagés : Considérons l'ensemble des programmes informatiques qui lisent en entrée un programme informatique P et répondent par « oui », ou éventuellement bouclent indéfiniment. Voici un exemple de tel programme :

• Lire en entrée P
• Exécuter P
• Afficher « oui »

La troisième étape ne pourra être exécutée qu'à l'issue de la seconde étape, c’est-à-dire lorsque P se sera terminé. Si P boucle indéfiniment, il en est de même du programme principal et l'affichage « oui » n'aura jamais lieu.

Intéressons-nous maintenant à l'ensemble X des tels programmes P qui bouclent indéfiniment lorsqu'ils sont appliqués à eux-mêmes. Supposons maintenant que cet ensemble X est semi-décidable, c'est-à-dire qu'il existe un programme P0 tel que P0 réponde « oui » sur une entrée P si et seulement si P est dans cet ensemble. Nous pouvons maintenant nous demander si P0 est lui-même dans X. P0 répond « oui » sur l'entrée P0 si et seulement si P0 est dans X, c'est-à-dire si P0 appliqué à l'entrée P0 ne termine pas. La supposition d'existence de P0 est absurde. X n'est donc pas semi-décidable.

(Notons que le complémentaire de X est semi-décidable : le programme de semi-décision prend en entrée P, applique P à lui-même, puis répond « oui ».)

A fortiori, X n'est pas décidable.

Considérons maintenant le problème T de tester au vu d'un programme P si celui-ci termine sur l'entrée vide. On va réduire le problème de l'arrêt à celui-ci, c'est-à-dire montrer qu'on peut, au vu d'une question sur le problème de l'arrêt, construire algorithmiquement une question au problème T dont la réponse sera équivalente.

Soit P un programme dont on veut déterminer s'il appartient à X. On peut algorithmiquement construire un programme P2 qui ne prenne aucune entrée et lance P sur lui-même. Si on sait décider en général si P2 termine, on sait décider en général si P termine, donc X serait décidable. Cela est absurde.

Donc : il n'existe pas de moyen algorithmique de déterminer si un programme arbitraire termine.

Cette démonstration de l'arrêt me convainct beaucoup plus que cette histoire de bits et de N que je trouve aussi foireuse que toi. Qu'en penses tu ?

[neuromencien]

Merci pour vos réponses. J'ignorais que la question était sujette à une telle polémique

Donc si je résume ce n'est pas faisable, mais on peut tout de même approcher une solution en invalidant certains chemins. C'est ce que je vais faire. Je vais aussi faire quelques recherches sur "common sub-expression" et "symbolic evaluation" comme me l'à proposé Jean-Marc.Bourguet.

[10_GOTO_10]

[edit]réponse au post de nletteron[/edit]

Encore une nouvelle démonstration (mais pourquoi y en a-t-il tant ?).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Intéressons-nous maintenant à l'ensemble X des tels programmes P qui bouclent indéfiniment lorsqu'ils sont appliqués à eux-mêmes.

Comme je l'ai dit plus haut, il n'y a pas des programmes qui bouclent et d'autres qui s'arrêtent. Il n'y a que des instances de programmes (instructions + données initiales) qui le font.

Ici, le programme est P, quelles sont les données initiales ? P et les données initiales de P. C'est à dire P et les données initiales de P, et les données initiales de P. Et ainsi de suite. Nous avons donc théoriquement une infinité d'instances de P. Certaines bouclent, d'autres pas (il n'y a aucune contradiction là dedans, ce sont des instances différentes).
Sauf que pour exécuter un tel programme, il faudrait une mémoire infinie et un temps infini. Donc rien que le fait d'évoquer "P appliqué à P" est une vue de l'esprit.

[Jean-Marc.Bourguet]

Il existe au moins une catégorie de machines de Turing s'arrêtant en un
temps fini: ce sont les composants electroniques.

Non, les composants électroniques sont des composants analogiques. On peut
les simuler avec une bonne précision mais on ne peut pas les décrire
totalement avec des machines de Turing.

L'état des transistors (bloqués ou passants)

Que fais-tu de tous les états intermédiaires?

représentent l'état de la machine de Turing, et la présence ou non
de courant dans les fils représentent le ruban.

Il y a plus que simplement présence ou non, il y a la grandeur dont il faut tenir compte.

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.

Les systèmes électroniques ne convergent pas nécessairement vers un état
stable. Au fait, tu as l'air de confondre courant et tension.

Démontrons par la "méthode Turing" qu'il ne peut pas exister de
composant ayant une tension de sortie égale à l'entrée:

Cette "méthode de Turing" s'appelle diagonalisation. Je suppose que tu
n'es pas convaincu non plus par la démonstration du fait qu'il n'y a pas de
bijection entre l'ensemble des réels et celui des entiers.

Démonstration:

Supposons que nous ayons un composant A tel que la sortie soit égale à
l'entrée (Fonction NOP).

Ça s'appelle un buffer ou un court-circuit.

Construisons un composant B tel que la sortie soit inversée par
rapport à l'entrée (Fonction NOT).

Comment? Ça ne me semble pas être une opération évidente à faire à partir
d'un simple court-circuit.

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.

Effectivement, ils n'existent pas.

Sauf que ces composants A et B existent, et sont commercialisés
sous les références LS 07 et LS 04 (circuits TTL).

Ces composants ne sont pas ceux dont tu as supposé l'existence: ils
introduisent un délai entre les modifications de tension à l'entrée et à la
sortie. Ces délais sont souvent négligeables -- ou plutôt on a tendance à
se limiter aux conditions où ils le sont -- mais ils sont néanmoins
présents et jouent un rôle dans un circuit comme celui que tu imaginais.

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é.

Non, on prends simplement en compte ces délais. On s'en sert parfois,
parfois c'est des nuisances.

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.

Les oscillations sont un des comportements induits par les délais.

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.

Quand est-ce qu'on suppose que les machines de Turing effectuent un
traitement quelconque en un temps nul?

[Jean-Marc.Bourguet]

Encore une nouvelle démonstration (mais pourquoi y en a-t-il tant ?).

Je connais au moins trois démonstrations du théorème de Pythagore. Pourquoi y en a t'il tant? Ce théorème doit être faux.

[10_GOTO_10]

Je connais au moins trois démonstrations du théorème de Pythagore. Pourquoi y en a t'il tant? Ce théorème doit être faux.

Je n'ai jamais prétendu qu'il y avait corrélation. Je me pose la question, c'est tout.