Répondre à la discussion
Affichage des résultats 1 à 23 sur 23

Fonction récursive étonnante



  1. #1
    Deedee81
    Modérateur

    Fonction récursive étonnante


    ------

    Salut

    Un petit truc que j'ai lu dans un article hier. Je le met ici car je vais le poser comme une question. Que ceux qui connaissent ou ont lu le même article ne se précipitent pas pour donner les réponses (en tout cas pas sans spoiler). Mais je donnerai sans doute assez vite les réponses.

    Soit la fonction récursive M sur les réels définie comme suit :
    Si x < 0 alors M(x) = -x
    Si x >= 0 alors M(x) = M(x - M(x-1)) / 2

    Questions :
    1) Pouvez-vous écrire un petit programme récursif qui implémente cette fonction ? Là c'est facile évidemment.
    2) Pouvez-vous calculer à la main ou avec votre programme :
    M(0), M(1), M(2) ? (facile) Et M(3) ? (difficile) Sinon M(4) ?
    3) On peut démontrer que la fonction récursive se calcule en un nombre fini d'étapes quelle que soit la valeur de x. Pouvez-vous le démontrer ? (c'est c'est hard mais... essayez )
    4) Si vous y arrivez, cette démonstration a quelque chose d'assez étonnant (pour un truc aussi "simple" en tout cas). Le voyez-vous, le devinez-vous ?

    -----
    Keep it simple stupid

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    Liet Kynes

    Re : Fonction récursive étonnante

    Bonjour,

    je ne comprends comment il faut aborder cela Si x >= 0 alors M(x) = M(x - M(x-1)) / 2
    M étant une fonction je ne trouve pas à quoi correspond le M dans la parenthèse..
    En langage très barbare et comme on est pas sur le forum maths :

    je fais quelque chose à x équivaut à : je fait quelque chose à x - 1 j'enlève x au résultat et avec ce que j'obtiens je fait la même chose qu'à x-1 puis je divise le tout cela par 2 je ne vois pas ce que l'on applique à x-1?
    Sans questions il n'y a que des problèmes sans réponses.

  5. #3
    vgondr98

    Re : Fonction récursive étonnante

    A mon avis, il faut l'aborder comme cela
     Cliquez pour afficher

  6. #4
    jacknicklaus

    Re : Fonction récursive étonnante

    Citation Envoyé par Liet Kynes Voir le message
    Bonjour,
    je ne comprends comment il faut aborder cela Si x >= 0 alors M(x) = M(x - M(x-1)) / 2
    C'est une fonction récursive, très commun en programmation. On utilise la fonction dans sa propre définition, en traitant un cas particulier explicitement. La plus classique:

    Code:
    factorielle(x)
    si x = 1 alors résultat = 1
    sinon résultat = x * factorielle(x-1)
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  7. A voir en vidéo sur Futura
  8. #5
    pm42

    Re : Fonction récursive étonnante

    Citation Envoyé par jacknicklaus Voir le message
    C'est une fonction récursive, très commun en programmation.
    Et en maths puisqu'on définit notamment la célèbre suite de Fibonacci comme ça. Et c'est juste un exemple parmi tellement d'autres.

  9. #6
    jacknicklaus

    Re : Fonction récursive étonnante

    Soit la fonction récursive M sur les réels définie comme suit :
    Si x < 0 alors M(x) = -x
    Si x >= 0 alors M(x) = M(x - M(x-1)) / 2
    Ca me rappelle la fonction d'Ackermann définie sur ℕ×ℕ , et dont le calcul est infaisable sauf pour une dizaine de valeurs.
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  10. Publicité
  11. #7
    vgondr98

    Re : Fonction récursive étonnante

    Citation Envoyé par jacknicklaus Voir le message
    Ca me rappelle la fonction d'Ackermann définie sur ℕ×ℕ , et dont le calcul est infaisable sauf pour une dizaine de valeurs.
    Pour M(3), la fonction que j'ai codée à déjà calculé 400 000 valeurs et ne semble pas vouloir s'arrêter mais bon je me suis peut-être trompé dans mon code qui sait.

  12. #8
    Liet Kynes

    Re : Fonction récursive étonnante

    Ca y est j'ai pigé, merci pour les explications.
    Sans questions il n'y a que des problèmes sans réponses.

  13. #9
    Deedee81
    Modérateur

    Re : Fonction récursive étonnante

    Salut,

    Que de bonnes remarques et réflexions

    Citation Envoyé par vgondr98 Voir le message
    Pour M(3), la fonction que j'ai codée à déjà calculé 400 000 valeurs et ne semble pas vouloir s'arrêter mais bon je me suis peut-être trompé dans mon code qui sait.
    Non c'est juste. Le calcul devient vite inabordable (la valeur de M(4) est même inconnue).

    Reste à démontrer qu'elle s'arrête (pas évident).
    Keep it simple stupid

  14. #10
    Svenn

    Re : Fonction récursive étonnante

     Cliquez pour afficher

  15. #11
    Deedee81
    Modérateur

    Re : Fonction récursive étonnante

    C'est aussi une très bonne remarque, félicitation pour les résultats (tant pour avoir réussi à les obtenir que l'analyse de ces résultats). Ils sont justes

    Delahaye a dit qu'il avait programmé ça très soigneusement mais n'avait quand même pas pu calculer M(3). Mais il se calcule (faut un supercalculateur !)

    Je lève le voile :
    https://www.pourlascience.fr/sr/logi...ches-22274.php

    Tout l'article n'est pas lisible sans payer mais ce qu'on lit suffit déjà à deviner la réponse à ma question (4)
    (la démonstration n'est pas dans l'article, elle est disponible via les références, toutefois les explications données avec le cardinaux de Cantor suffit à comprendre la source de la difficulté)
    Dernière modification par Deedee81 ; 08/09/2021 à 12h09. Motif: orthographe
    Keep it simple stupid

  16. #12
    pm42

    Re : Fonction récursive étonnante

    Et c'est en effet un article très, très intéressant ou comment partir d'un simple "casse-tête" concret pour arriver à un indécidable facile à exprimer.

  17. Publicité
  18. #13
    Deedee81
    Modérateur

    Re : Fonction récursive étonnante

    Citation Envoyé par pm42 Voir le message
    Et c'est en effet un article très, très intéressant ou comment partir d'un simple "casse-tête" concret pour arriver à un indécidable facile à exprimer.
    Ce qui est sans doute remarquable c'est que le problème est particulièrement simple. C'est la première fois qu'on a un indécidable de Peano aussi simple, sans logique auto-référentielle et pouvant clairement surgir dans des mathématiques "naturelles" (v.s. des trucs alambiqués construit justes pour ça).
    Keep it simple stupid

  19. #14
    jacknicklaus

    Re : Fonction récursive étonnante

    Citation Envoyé par Deedee81 Voir le message
    Ce qui est sans doute remarquable c'est que le problème est particulièrement simple. C'est la première fois qu'on a un indécidable de Peano aussi simple, sans logique auto-référentielle et pouvant clairement surgir dans des mathématiques "naturelles" (v.s. des trucs alambiqués construit justes pour ça).
    On a aussi la fonction d'Ackermann à laquelle je faisais référence. Elle a de remarquable que la seule opération arithmétique utilisée est .. "+ 1" . Et pourtant ...
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  20. #15
    Médiat

    Re : Fonction récursive étonnante

    Citation Envoyé par Deedee81 Voir le message
    C'est la première fois qu'on a un indécidable de Peano aussi simple
    Les suites de Goodstein sont très simples aussi à définir
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  21. #16
    pm42

    Re : Fonction récursive étonnante

    Citation Envoyé par jacknicklaus Voir le message
    On a aussi la fonction d'Ackermann à laquelle je faisais référence. Elle a de remarquable que la seule opération arithmétique utilisée est .. "+ 1" . Et pourtant ...
    Oui, elle est impressionnante mais son arrêt n'est pas indécidable dans l'arithmétique de Peano : elle n'est pas primitive récursive mais reste complètement calculable (de mémoire + lectures en anglais)

  22. #17
    Deedee81
    Modérateur

    Re : Fonction récursive étonnante

    Citation Envoyé par Médiat Voir le message
    Les suites de Goodstein sont très simples aussi à définir
    Oui, c'est vrai. Je citais juste Delahaye
    (mais c'est vrai que le fameux problème de l'hydre de Lerne m'est venu à l'esprit)

    Ah, pris de vitesse avec Ackermann. Oui en effet, le coté remarquable de "M" n'est pas tant sa (dé)croissance si rapide mais plutôt le fait qu'elle conduit à un tel indécidable. J'ai souvent vu des fonctions récursives (forcément, avec l'informatique, hein) et démontrer l'arrêt ou pas est généralement fort simple (sauf fonctions hautement complexes) mais ici c'est la simplicité de "M" qui rend ce résultat déroutant !

    Bon, en soi c'est surtout intéressant et sympatique (c'est aussi pour ça que je l'ai mit ici et pas en maths du supérieur ou en logique).
    Dernière modification par Deedee81 ; 08/09/2021 à 13h15. Motif: avec un e le lerne
    Keep it simple stupid

  23. #18
    Stan_94

    Re : Fonction récursive étonnante

    Intéressant ça, mais migraine assurée pour moi d'essayer d'en comprendre l'aspect mathématique
    Ceci dit, Excel arrive vite à un dépassement de ses capacités !
    x = 0 1 2 2,9 2,91 2,9195 2,919509 2,92 2,95
    M(x) = 0,5 0,125 0,000976563 1,0206E-202 6,3515E-263 1,1392E-305 5,6962E-306 0 #VALEUR!

    Je me demande si il serait pertinent de tracer la courbe correpsondantes à cette fonction ?

  24. Publicité
  25. #19
    Deedee81
    Modérateur

    Re : Fonction récursive étonnante

    Citation Envoyé par Stan_94 Voir le message
    Je me demande si il serait pertinent de tracer la courbe correpsondantes à cette fonction ?
    Je ne crois pas que ce soit très parlant. Par contre l'ensemble F des nombres fusibles (voir l'article) dont est tiré cette fonction a une structure extraordinairement riche et assez visuelle (pour ses grandes lignes, comme le dit Delahaye, dès qu'on creuse ses propriétés c'est plus difficile à "voir")

    EDIT l'article étant payant, voir https://fr.wikipedia.org/wiki/%C3%89...mbres_fusibles pour la définition
    redit ah tiens, ils citent aussi Goldstein
    Dernière modification par Deedee81 ; 08/09/2021 à 13h23.
    Keep it simple stupid

  26. #20
    Médiat

    Re : Fonction récursive étonnante

    Citation Envoyé par Deedee81 Voir le message
    ils citent aussi Goldstein
    ni lui ni Goldfinger mais Goodstein
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #21
    Deedee81
    Modérateur

    Re : Fonction récursive étonnante

    Roooooooh !!!!!!

    Merci Médiat
    Keep it simple stupid

  28. #22
    Svenn

    Re : Fonction récursive étonnante

    Voilà les conclusions auxquelles j'étais arrivé sans lire wikipedia, globalement j'avais pas trop mal visé

    Voilà comment évolue -Log2(M(x)) de 1 à presque 3. Les points que j'ai utilisé sont ceux d'abscisse x=n/128, avec n entier (le plus grand étant vers 2.9). A l'exception d'une poignée de valeurs à la gauche du graphique, toutes les valeurs de -Log2(M(x)) sont entières.

    Le fait de prendre des points d'abscisse n/128 n'est pas du tout anodin puisque la courbe qui est déjà en dents de scie pour ces valeurs est encore bien plus complexe que ça si on prend des points "moins réguliers".

    Regardons ce qui se passe pour x=1-ɛ avec ɛ très petit. On va donc avoir M(1-ɛ)=(1-ɛ-M(-ɛ))/2=M(1-2ɛ)/2 et donc M(1-ɛ*2^(-n))=M(1-ɛ)*2^(-n). La limite de M(x) quand x tend vers 1 par valeurs inférieures, c'est donc 0
    Ce qui se passe à l'approche de 1 se passe en fait pour plein de valeurs, on voit d'ailleurs sur le graphique que la courbe diverge à l'approche par la gauche de 1,125, de 1,25, de 1,5, de 2, de 2,5 et plus probablement de n'importe quel nombre A/2^n avec A entier. Avec une divergence d'autant plus rapide que n est petit. Si c'est le cas, la courbe M(x) serait donc définie partout et continue nulle part au-delà d'une certaine valeur.
    log2m.png

  29. #23
    Deedee81
    Modérateur

    Re : Fonction récursive étonnante

    Salut,

    Joli..... Bravo. Ca ressemble furieusement à la structure de l'ensemble F. Ce n'est sûrement pas un hasard.
    Keep it simple stupid

Discussions similaires

  1. Fonction récursive (C)
    Par theodutt dans le forum Programmation et langages, Algorithmique
    Réponses: 4
    Dernier message: 06/11/2018, 20h07
  2. Fonction récursive VB.net
    Par KKG689 dans le forum Programmation et langages, Algorithmique
    Réponses: 17
    Dernier message: 13/05/2018, 20h22
  3. fonction récursive
    Par bastinoute dans le forum Mathématiques du collège et du lycée
    Réponses: 20
    Dernier message: 22/09/2013, 13h45
  4. fonction primitive-récursive
    Par Brumaire dans le forum Mathématiques du supérieur
    Réponses: 16
    Dernier message: 06/06/2009, 05h30
  5. fonction recursive
    Par hterrolle dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 23/05/2006, 18h24