[Info] Probleme de terminaison

[invite4ef352d8]

Bonsoir !

j'ai une question tous a fait... pationante, soulvé par mon dernier DM d'info .

on considere la fonction recursive definit de la facon suivant :

Morris(m,n) = Morris(m-1,Morris(m,n))
Morris(0,n) = 1

l'enoncé demande si la fonction definit ainsi est justement bien definit.

sans rentrer dans les detail l'enoncé semble attendre assez clairement qu'on reponde "oui elle est bien definit, puisque si on itere la relation de recurence Morris(m,n)=Morris(0,....) = 1"


cependant je me pose la question :

est-ce que on peut dire que "Morris(0, quelque chose qui n'est pas definit)" est vraiment definit ?
si on dit que ce n'est pas definit, alors Morris(m,n) n'est pas definit non ?

au final est-ce qu'on ne peut pas dire que le fait que la fonction est corectement definit est indecidable puisque ni cette proposition ni sa negation n'apporte de contradiction ? (et si c'est vraiment le cas, comment peut-on le justifié ?)

merci!
-----

[invite6b1e2c2e]

Morris(m,n) = Morris(m-1,Morris(m,n))
Morris(0,n) = 1

Bonjour,

Si je comprends bien, Morris(1,n) = 1, et de proche en proche, Morris(m,n) =1. Déjà, je vois pas trop pourquoi on appelle la fonction constante 1 Morris, mais bon

Implicitement, je suppose que Morris est une fonction à valeur dans N.
En tout cas, voilà ce que je pense de ton problème. Si tu sais que la fonction Morris existe et vérifie en plus la propriété de récurrence "foo", alors ce n'est clairement pas indécidable, et Morris = 1.

Si on te demande de prouver l'existence d'une fonction qui vérifie ces propriétés, alors tu peux exhiber la solution Morris =1. Et comme l'unicité est démontrée par le point d'avant, tu obtient que Morris est bien définie, au sens où c'est une fonction, et qu'elle est notamment univaluée.

Cela dit, j'avoue ne pas trop comprendre ta dernière question. Qu'est ce qui est indécidable ? Pour moi, la fonction est bien définie au sens où il existe une unique solution à ce problème.

__
rvz

[invite6de5f0ac]

Cela dit, j'avoue ne pas trop comprendre ta dernière question. Qu'est ce qui est indécidable ? Pour moi, la fonction est bien définie au sens où il existe une unique solution à ce problème.
rvz

Bonsoir,

Je crois que c'est l'énoncé qui est trop elliptique. Ecrire Morris(0,n)=1 sans plus de précisions suggère (mais ne dit pas) que , ce qui est d'usage dans ce domaine.

Mais ladite fonction, même si elle n'est pas indécidable, me dit vaguement quelque chose. Je crains que son temps d'évaluation soit largement NP même pour des valeurs faibles de m et n.

(cette dernière phrase est idiote puisque NP est une propriété asymptotique; mais je me comprends, et je ne dois pas être le seul, si? ah bon. )

-- françois

[invite6b1e2c2e]

Mais ladite fonction, même si elle n'est pas indécidable, me dit vaguement quelque chose. Je crains que son temps d'évaluation soit largement NP même pour des valeurs faibles de m et n.

(cette dernière phrase est idiote puisque NP est une propriété asymptotique; mais je me comprends, et je ne dois pas être le seul, si? ah bon. )

Bonsoir,

Ca me fait plaisir de voir que je ne suis pas à soliloquer sur le forum, tout seul à cette heure tardive.

Effectivement, numériquement, ça doit prendre une place mémoire assez importante. En tout cas, ça doit ralentir pas mal les machines. Bon, pour moi NP, P, c'est pas très clair, mais en tout cas, c'est clair que ça doit être long, juste le temps de profiter de la vie quoi !

__
rvz

[A voir en vidéo sur Futura]

[invitef45cc474]

Salut
Je pense ne pas me tromper en disant que tu es un élève de mpsi au lycée condorcet
Je me rappelle de cette fonction et je crois bien me rappeler que notre cher prof d'info nous avait expliqué que cette fonction n'était pas définie, dans le sens où on ne pouvait pas évaluer tous les arguments de la fonction (sauf pour m=0 bien sûr). Ceci est plus ou moins une question de convention: on considère qu'une fonction est définie lorsque l'on peut évaluer tous les arguments. Cependant il y a des cas en info ou on peut court-circuiter certains de ces problèmes (par exemple pour l'évaluation paresseuse des booléens).

Nico

[invite6de5f0ac]

Je pense ne pas me tromper en disant que tu es un élève de mpsi au lycée condorcet

Au lycée Condorcet, je ne sais pas. Cet exemple est un grand classique...

Le problème est que pour évaluer M(m,n) on n'a pas forcément besoin de savoir évaluer tous les M(m',n') pour m'<m et n'<n -- c'est bien ce que tu appelles l'évaluation paresseuse, le "and then" de Ada ou le "&&" du C/C++.

Un problème est NP = Non Polynômial (dans ce cas précis) si son temps d'évaluation ne peut pas être borné par un polynôme de degré fini en (m,n). En clair, s'il fait péter les ressources disponibles. En général ça se produit assez vite, d'où mon expression "pour des petites valeurs de m et n".

-- françois

[invite636fa06b]

Bonsoir
J'ai quelques doutes sur le contenu de ce fil.
Je pense qu'il s'agit de jargon informatique. La fonction n'est certainement pas évaluable par une machine à cause du second argument qui l'appelle récursivement sans aucune sortie. Le premier argument ne pose pas de problème puisqu'on arrive vers M(0,..) qui renvoie 1.
Alors que nous comprenons que l'on peut négliger le second, et que la fonction est finalement constante, une mécanique va s'acharner à calculer les seconds arguments.
Il est exact que le nombre d'appel croit exponentiellement avec n mais je ne pense pas que ça soit un problème NP : Non polynomial mais vérifiable en un temps Polynomial. Ca ressemble davantage aux "référence circulaires" d'excel. En outre n=m=2 suffit pour planter la machine.
Enfin je n'arrive pas à faire le lien entre avec le concept d'indécidabilité

[invitef45cc474]

Je pense qu'il s'agit de jargon informatique.

Oui en effet, il s'agit là que de jargon informatique, et non de considérations mathématiques: il s'agit de comprendre comment l'ordinateur "gère" une fonction. Et dans le cas récursif, l'ordinateur évalue par défaut tous les arguments.
Mais il y a en effet l'exemple de l'évaluation paresseuse des booléens dans lequel il est possible que la fonction se "termine" sans que la fonction soit définie pour toutes valeurs au sens mathématique.
Par exemple:
Maurice(m,n) = (m<=n) or Maurice(m-1,Maurice(m,n))
Maurice(0,n) = true

Cette fonction se termine, car dès que m<n la fonction renvoie vrai. Mais en fait c'est parce que la fonction n'évalue pas le booléen qui suit (et qui n'est pas défini en fait).

Nico

[invite4ef352d8]

deja, merci pour vos reponses.

pour le probleme de P ou NP et bien il ne se pose pas puisque si on code cette fonction sa donne une boucle infinie... sauf dans un calculateur qui utilise l'evaluation par neccecité dans qu'elle cas il est en O(m) donc P.


sinon quand je parle d'indecidabilité je me demande si justement on ne peut montrer que le fait que la fonction est definit ou non est indecidable dans le sens ou ni "la fonction est definit" ni "la fonction n'est pas definit" n'apporte de contradiction, (si on suppose que c'est definit alors... c'est definit est Moris m n = 1, si on suppose que c'est non definit pour m different de 1 et bien on ne peut effectivement pas calculer les valeurs et dans aucun des deux cas on a de contradiction...) mais en y reflechissant mieux et en lisant vos reponse, il me semble que c'est effectivement juste un probleme de convention et donc qu'il n'y a pas lieux de parler d'indecidabilité... non ?


NB : et sinon, oui je suis en MPSI a condorcet ^^