Fonction récursive étonnante

[Deedee81]

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 ?
-----

[Liet Kynes]

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?

[vgondr98]

A mon avis, il faut l'aborder comme cela

 Cliquez pour afficher

M(-1) => 1

M(0) => M(0 - M(-1))/2 => M(0 - 1)/2 => M(-1)/2 => 1/2

[jacknicklaus]

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:

factorielle(x)
si x = 1 alors résultat = 1
sinon résultat = x * factorielle(x-1)

[A voir en vidéo sur Futura]

[pm42]

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.

[jacknicklaus]

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.

[vgondr98]

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.

[Liet Kynes]

Ca y est j'ai pigé, merci pour les explications.

[Deedee81]

Salut,

Que de bonnes remarques et réflexions

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

[invitec0b62935]

 Cliquez pour afficher

J'ai pu calculer jusqu'à M(2.75), pour M(3) il faudrait que je programme ça de façon plus intelligente.

M(0) = 1/2
M(0.5) = 1/2^2
M(1) = 1/2^3
M(1.25) = 1/2^4
M(1.5) = 1/2^5
M(1.75) = 1/2^7
M(2) = 1^2^10
M(2.25) = 1^2^15
M(2.5) = 1/2^31
M(2.75) = 1/2^112

Ca ressemble à du M(n) = 1/(2^f(n)) avec f(n) qui croit encore plus vite qu'une fonction exponentielle. Je suis bien avancé !

[Deedee81]

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

[pm42]

https://www.pourlascience.fr/sr/logi...ches-22274.php

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.

[Deedee81]

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

[jacknicklaus]

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

[Médiat]

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

[pm42]

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)

[Deedee81]

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

[Stan_94]

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 ?

[Deedee81]

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

[Médiat]

ils citent aussi Goldstein

ni lui ni Goldfinger mais Goodstein

[Deedee81]

Roooooooh !!!!!!

Merci Médiat

[invitec0b62935]

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

[Deedee81]

Salut,

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