compilation

[jennifer]

coucou tout le monde j'ai une question a poser a tout le monde voila la question qui m'a été poser pour un devoir , pouvez vous y repondre parce que la je galere beaucoup :


On dit qu'un fragment de programme n'est pas utile (code mort) si
la logique du programme est telle qu'il est impossible d'exécuter
ce code quelles que soient les données fournies au programme.
Quelqu'un vous affirme qu'il a un compilateur optimal X qui élimine
tout le code mort. Prouvez que c'est impossible (c'est-à-dire que
si X existait on pourrait résoudre le problème d'arrêt).

ou alors pouvez vous m'indiquez un endroit ou je pourrez trouver de l'aide!!!!!!
merci Jennifer

[tomtom]

Hummm, un peu d'algo et de mathématiques...

Avant toute chose : Je suppose si tu poses cette question, tu as suivi au moins un cours d'algorithmique avec un certain niveau, voire un cours de mathématiques d'un niveau encore meilleur.
Hypothéses : tu sais ce qu'est une machine de turing, tu connais le problème d'arret et un minimum de théorie sur la calcabilité.

Code: Tout sélectionner

Machine de turing :
C'est un automate à etat fini. On la modélise en générale comme suit :

On a un ruban infini (ou au moins "suffisamment grand" ) comportant des cases dans lesquelles il y a des données (ces cases sont les "entrées" ou édonnées" du programme...).
La machine est une tête de lecture. Elle sait lire la valeur de la donnée sur le ruban. et ecrire sur le ruban.
On a un registre détat. En gros, un variable qui peut prendre un nombre FINI de valeurs. : E1, E2, E3, .., En
On a un automate (le "programme") qui est une "table d'actions", comportant elle aussi un nombre FINI d'entrées. Cette table d'action définit ce que fait le programme en fonction à la fois de son état  et de la valeur lue sur le ruban. ces actions sont limitées :
- deplacer le ruban, vers la droite ou la gauche
- remplacer la valeur de la donee
- changer d'etat
(l'automate peut effectuer plusieurs actions ex : remplacer la valeur et deplacer le ruban, remplacer la valeur et changer d'etat...)

L'automate demarre dans un etat initial (E0) et lit la donnée dans la case en face de lui. Puis, il effectue les actions prévues dans la table, fonction de la donnee et de l'etat.
L'automate s'arrete quand il n'y a aucune entrée dans sa table correspondant au couple (etat, donnée).


Passons à la théorie des maths...

- Il est admis que tout problème calculable (decidable) peut etre résolu par une machien de turing judicieusement choisie. En gros, si il n'existe pas de machine de turing pour resoudre ce problème, alors il n'est pas soluble...

- Il est demontré (et je ne ferais pas la demonstration car elle fait appel à des notions mathématiques violentes pour mon cerveau embué) qu'il n'est pas possible a priori de determiner si une mahine de turing va s'arreter ou non. Soit, a peu près, on peu trouver un ruban qui fera que la machine ne s'arretera pas, et un autre qui fera qu'elle s'arrete.
C'est je suppose ce que tu nomme "problème de l'arrêt".


Maintenant, la question.

Un programme informatique peut etre considéré comme une machine de turing (c'en est une d'ailleurs).
le ruban, c'est les données, les entrées, etc. Les etats, ce sont des variables internes. La table d'actions est le code compilé (executé).
Du code mort, c'est un endroit ou l'on ira jamais, c'est à dire une entrée de la table des actions qui ne sera jamais utilisées, ce qui revient à dire que qulles que soit la donne sur le ruban, on ne se retrouvera jamais dans la situation (etat, donnée) qui entraine cette action. Pour etre certain de ceci, il faut être capable de decrire tous les couples (etat, données) qui peuvent être vus. Or realiser cette enumération permet egalement de determiner si un de ces couples ne possède pas d'actions associée, condition de l'arret de la machine. Nous savons que ceci est impossible.


Voila, je ne sais pas si tu cherchais une demonstration aussi "blabla". Je ne maitrise pas assez les mathématiques sous-jacentes à ceci pour te l'expliquer, mais je pense que si tu cherches une demonstration "mathématique", la lecture de ce document pourrait t'aider :
http://www.mathematik.uni-karlsruhe.de/ ... ad/ter.pdf

Il existe quantité d'information sur internet sur ces théories, mais la plupart sont en anglais...

voila, bon courage !

t.