Calcul des chemins d'exécution d'un programme

Version imprimable

Voir 40 message(s) de cette discussion en une page

31/10/2006, 12h45
10_GOTO_10

Citation:

Envoyé par Jean-Marc.Bourguet

Non, les composants électroniques sont des composants analogiques.

Je parlais ici de composants numériques (portes logiques)

Citation:

Envoyé par Jean-Marc.Bourguet

Au fait, tu as l'air de confondre courant et tension.

Quand je disais que la moindre imprécision me serait reprochée...

Citation:

Envoyé par Jean-Marc.Bourguet

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.

Si, pourquoi ?

Citation:

Envoyé par Jean-Marc.Bourguet

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

Avec deux transistors.

Citation:

Envoyé par Jean-Marc.Bourguet

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.

Les programmes fonctionneraient de façon instantannée ?

Citation:

Envoyé par Jean-Marc.Bourguet

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

Ah ben, tu vois, on est d'accord. Les programmes comme les composants n'effectuent pas de traitement en un temps nul.
31/10/2006, 14h43
nletteron
Bon on va la jouer mathématique. Je ne peux pas être d'accord sur la définition de programme que tu utilises. J'utiliserais donc le terme procédure qui s'applique à des données initiales et pas un double ensemble d'instructions et de données initiales.

Soit p une procédure qui calcule la fonction f. Soit n un entier. p(n) représente la procédure p appliqué à n. Une fonction f est dite calculable si il existe au moins une procédure qui la calcule. Jusque là rien de bien compliquer. Tout le monde sait qu'on ne peut pas numéroter les procédures (c'est Cantor qui l'a dit) donc on en déduit toujours aisément qu'il existe une foultitude de fonction f:N->N qui ne sont pas calculables.

Jusqu'ici tout va bien... :mouarf:

Aller je prend une fonction h avec comme argument une procédure et un entier naturel.

h(p,x) = 1 si p(x) est défini
h(p,x) = 0 sinon

h(p,x) n'est pas calculable.
- la procédure p calcule-t-elle une fonction totale, c'est-à-dire a-t-on :pour tout x, h ( p, x ) = 1 ?
- Existe-t-il x tel que h ( p, x ) = 1 ?
Réponses de ta part ?

Il n'y a ici aucune ambiguïté possible sur des procédures qui appellent des procédures.
31/10/2006, 14h44
nletteron

EDIT Erreur de post.
31/10/2006, 14h56
Jean-Marc.Bourguet

Citation:

Envoyé par 10_GOTO_10

Je parlais ici de composants numériques (portes logiques)

Il n'y a pas de composants numériques, rien que des composants qu'on fait fonctionner dans un mode numérique. Quand tu sorts de leur zone de fonctionnement numérique, ce sont des composants analogiques.

Citation:

Quand je disais que la moindre imprécision me serait reprochée...

Ça te rend difficile à comprendre

Citation:

Si, pourquoi ?

Parce que jusqu'à présent il y avait toujours une corrélation.

Citation:

Avec deux transistors.

Tu n'as pas compris le fond de ma question. De toute façon il est accessoire, passons.

Citation:

Les programmes fonctionneraient de façon instantannée?

Ah ben, tu vois, on est d'accord. Les programmes comme les composants n'effectuent pas de traitement en un temps nul.

L'introduction d'un délai supprime le fond de ta preuve de non existence de la porte non. En effet, il n'y a aucune incohérence quand à la valeur de la tension du noeud d'entrée de sa porte quand on le court-circuite avec sa sortie: il y a deux délais (celui de la porte et celui du fil) qui permettent des tensions cohérentes.

À quel endroit l'introduction de délais rend-t'elle la preuve de Turing invalide?
31/10/2006, 14h58
borisd

Citation:

Envoyé par nletteron

Tout le monde sait qu'on ne peut pas numéroter les procédures (c'est Cantor qui l'a dit) donc on en déduit toujours aisément qu'il existe une foultitude de fonction f:N->N qui ne sont pas calculables.

Tu ne voudrais pas plutôt dire veux dire "on ne peut pas numéroter les fonctions" (et on peut numéroter les procédures) ? :P
31/10/2006, 15h17
10_GOTO_10

Citation:

Envoyé par nletteron

Bon on va la jouer mathématique..

Très bien. Enfin un peu de rigueur.

Citation:

Envoyé par nletteron

h(p,x) = 1 si p(x) est défini

Là, je te suis pas bien. Q'appelles-tu "défini" ? Au sens mathématique du terme ?

Citation:

Envoyé par nletteron

h(p,x) n'est pas calculable.

C'est une hypothèse ou ta conclusion ?
31/10/2006, 15h36
Jean-Marc.Bourguet

Citation:

Envoyé par 10_GOTO_10

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

Tu mets le doigt ici sur une des difficultés techniques de la preuve que les présentation simplifiées esquivent généralement.

On peut tout d'abord remarquer que cette objection ne gène pas la preuve si plutôt de prouver l'inexistance d'une machine de Turing déterminant l'arrêt des couples machine de Turing/entrée on cherche à prouver l'inexistance d'une machine de Turing déterminant l'arrêt des machines de Turing quelle que soit leur entrée ou l'inexistance d'une machine de Turing déterminant l'arrêt des machines de Turing sans entrée ou à entrée fixe.

Revenons au problème initial qui était de faire la preuve pour H(m, x).
Construisons d'abord I(m) = H(m, H). C'est une machine qui résouds le problème de l'arrêt pour une entrée constante, donc elle n'existe pas. Soit que H n'existe pas, soit qu'il est impossible de construire H(m, H). Si je prends une machine de Turing universelle prenant pour la description de la machine à simuler le même codage que H, je peux facilement construire H(m, H). Donc H n'existe pas.
31/10/2006, 15h40
nletteron

Citation:

C'est une hypothèse ou ta conclusion ?

Ne serait ce pas la conclusion évidente de nombreux paradoxe que tu peux trouver par diagonalisation de Cantor ?

Citation:

Là, je te suis pas bien. Q'appelles-tu "défini" ? Au sens mathématique du terme ?

C'est la question à laquelle je m'attendais.

p(x) défini <=> Il existe y tel que p(x) = y
p(x) défini <=> p = { xEX / p(x) } (amusant d'ailleurs)

p(x) défini je dirais pour le moment, que la procédure p donne un résultat quel que soit x. Le temps n'intervient pas pour le moment.

Citation:

Tu ne voudrais pas plutôt dire veux dire "on ne peut pas numéroter les fonctions" (et on peut numéroter les procédures) ?

Petite erreur de ma part (le travail m'endors :D). On peut numéroter les procédures ce qui d'ailleurs permet de montrer l'existence dans tout modèle de calcul de fonctions partielles calculable.

Citation:

Revenons au problème initial qui était de faire la preuve pour H(m, x).
Construisons d'abord I(m) = H(m, H). C'est une machine qui résouds le problème de l'arrêt pour une entrée constante, donc elle n'existe pas. Soit que H n'existe pas, soit qu'il est impossible de construire H(m, H). Si je prends une machine de Turing universelle prenant pour la description de la machine à simuler le même codage que H, je peux facilement construire H(m, H). Donc H n'existe pas.

Ce qui ce conçoit bien s'énonce clairement dit on. J'ai toujours eu du mal à l'énoncer mais pas à le concevoir :mouarf:
31/10/2006, 15h43
nletteron

Une petite nouvelle qui risque de ravir certains.

Citation:

On énonce une nouvelle frontière entre la décidabilité du problème de l'arrêt et l'universalité pour les machines de Turing déterministes et non effaçantes sur {0,1}. De façon précise: toute machine de ce type qui a au plus deux instructions gauches a un problème de l'arrêt décidable et il existe une machine de ce type avec exactement trois instructions gauches qui simule une machine de Turing universelle. De plus, on ne peut construire une telle machine de Turing universelle avec 223 états. Dans ce rapport, on donne une preuve complète du résultat qui concerne les machines qui ont au plus deux instructions gauches.
31/10/2006, 16h01
Nemerle

10 goto 10: pas d'accord avec toi, je reviendrai des que j'aurais du temps pour te préciser ce passage de N à log2(N) qui te dérange tant. Je pensais que cette démo vulgarisée était compréhensible, mais bon...

Si tu veux de la rigueur: va dans une librairie scientifique prendre un livre niveau troisième cycle sur la thérie des langages. Tu y verras la preuve mathématique du théorème de Turing/Rice, qui de mon coté matheux est une conséquence indirect du théorème d'inversion global sur les espaces de Banach (http://www.les-mathematiques.net/a/a/f/node11.php3 voir la 1iere remarque parlant du th. de Rice)

Sinon: un cours d'info avec la démo (page 46): http://www.cs.tau.ac.il/~kgad/cm/cou...lec8-print.pdf

voir aussi une vulgarisation plus simple: http://www.techno-science.net/?ongle...efinition=6238

Voir 40 message(s) de cette discussion en une page