Devinette mathématique

[Schrodies-cat]

@goel:
Vous dites que votre mathématicien a représenté un nombre pour lequel il n'existe aucun moyen de le représenter (excusez moi de dévoiler votre spoiler).
Vous n'avez pas l'impression qu'il y a un problème ?
-----

[ansset]

l ambiguïté vient peut être de l'interprétation du mot "représenter".
car on pourrait penser à l'Oméga de Chaitin, voire aux nb de ramifications d'une fractale "sans fin".
pour ma part j'attend des nouvelles de Goel.

[Schrodies-cat]

"Représenter", ou "définir", c'est ici synonyme, c'est pour ça que j'ai mentionné le paradoxe de Berry sur la définissabilité.

[Schrodies-cat]

"Représenter" dépend de la théorie dont on dispose.
Si on ne connait que la numération en base 10 , la méthode pour représenter le plus grand nombre possible est d'écrire le plus possible de "9" sur la feuille de papier dont on dispose. (on aurait pu mettre un comptable dans l'énigme)
Si on connait l'exponentiation, par exemple, on peut faire mieux.

[Médiat]

Un rapport avec les nombres de Ramsey ?

[Schrodies-cat]

Un rapport avec les nombres de Ramsey ?

Les nombres de Ramsey sont calculables au sens de Turing.(Théoriquement, dans la pratique c'est plus coton)
Donc on pourrait faire mieux avec cette idée :

On peut bien entendu faire mieux que notre informaticien en définissant une fonction qui croit plus vite que toute fonction calculable par ordinateur.

[Schrodies-cat]

Considérons une famille dénombrable de fonctions entières d'une variable entière.
On peut définir une fonction qui croit plus vite que toute fonction de cette famille.
Simple diagonalisation.

Considérons les fonctions définissables.
Elles sont définies par une formule contenant un nombre fini de symboles.
Donc l'ensemble des fonctions définissable est dénombrable.
Donc on peut définir une fonction qui croit plus vite que toute fonction définissable.
Euh ...
Cherchez l'erreur !

[Médiat]

Donc on peut définir une fonction qui croit plus vite que toute fonction définissable.

Un peu abusif ce donc, mais ...Faites le

[_Goel_]

La bonne réponse a été donnée !!!
Mais, j'ai l'impression que beaucoup sont passés au travers, vu les derniers posts !

Donc on peut définir une fonction qui croit plus vite que toute fonction définissable.

=> On parle d'une fonction qui correspond à un concept mathématique et donc non réitérée (du type G(x) = F(F(x)) avec F croissante > 1 au dela d'un rang donné)

Vous dites que votre mathématicien a représenté un nombre pour lequel il n'existe aucun moyen de le représenter (excusez moi de dévoiler votre spoiler).
Vous n'avez pas l'impression qu'il y a un problème ?

=> Disons que le nombre est "légèrement" trop grand pour être représenté


Ce nombre peut être néanmoins borné entre :
- n(4) (qui vaut "environ" selon la notation d'Ackermann, sachant que le nombre de Graham est "juste" de l'ordre de )
- et majoré par le nombre de loader qui est fini aussi (mais bon, D(D(D(D(D(99))))) étant défini de manière récursive, c'est pas vraiment du jeu, et D(99) est inférieur à notre nombre !)

[Médiat]

Bonjour,

Je ne comprends pas votre réponse, d'autant plus que :

On cherche en fait une fonction mathématique qui :- a la plus grosse vitesse de croissance que l'on connaisse. En fait, pour toute fonction mathématique, celle que l'on cherche la majorera à partir d'un rang suffisamment grand.

Cette phrase est contradictoire (une fonction mathématique plus grande que toutes les fonctions mathématiques (donc plus grande qu'elle même + 1)),

Mais il y a plus problématique, pour moi : une fonction n'est pas un nombre, et toute valeur d'une fonction en un point peut être majorée par une fonction récursive primitive très simple.

[ansset]

La bonne réponse a été donnée !!!

pardonnes moi, mais il me semble pas que tu l'ais pas précisée dans le fil.
ou bien ai je loupé un passage.
cela aurait certainement permis de mieux comprendre le sens de ton énigme et par là même de répondre indirectement aux interrogations ou remarques qui ont été émises par certains ici ( je pense surtout aux spécialistes des maths )
cordialement.

[Schrodies-cat]

Un peu abusif ce donc, mais ...Faites le

On formalise rarement complètement les démonstrations mathématiques, mais une démonstration, en français par exemple, doit être formalisable.
Évidemment, ça coince quelque part.
Je crois que le problème n'est pas tant dans le donc que dans l'usage du mot "définissable".
La définissabilité est relative à une théorie et se définit dans une métathéorie de cette théorie.
J'utilise le terme définissable comme s'il avait un sens absolu alors qu'il n'est que relatif.

[Médiat]

Je vois deux problèmes :

1) Pour définir cette fonction il faut écrire la définition de toutes les fonctions définissables, même si elles sont en nombre dénombrable, cela ferait une formule de longueur infinie, donc pas une formule.

2) Avoir une fonction telle que f(0) soit plus grand que l'image par 0 de la première fonction définissable, n'impose en rien que cette fonction soit plus pour toutes valeurs de n (ou en tout cas à partir d'une certaine valeur de n), mais ce point est facilement corrigeable.

[Schrodies-cat]

Je vois deux problèmes :

1) Pour définir cette fonction il faut écrire la définition de toutes les fonctions définissables, même si elles sont en nombre dénombrable, cela ferait une formule de longueur infinie, donc pas une formule.

(...)

Pour définir une fonction qui croit (asymptotiquement) plus vite que toute fonction Turing-calculable, on n'a pas besoin de citer un algorithme calculant chacune de ces fonctions, il suffit d'une bonne définition de la calculabilité.
C'est à mon sens la définition de la définissabilité qui pose problème.

[Médiat]

Je faisais allusion à votre message #37 qui fait explicitement appel à une argument diagonal.

Je ne vois pas ce qu'il y aurait d'étonnant à ce qu'une fonction strictement plus grande que toutes les fonctions définissables ne soit pas définissable

[ansset]

Pour le péquin que je suis, je serais ravi d'être instruit sur le rapport avec l'énoncé inital : les arbres, les allumettes, le papier,.....
et tj pas compris ou la "bonne" réponse a pu être donnée.
merci pour vos éclairages.
Cdt

[Schrodies-cat]

@Médiat
Bien entendu, j'ai prétendu en définir une, mais je n'y ai jamais cru !

[Schrodies-cat]

Pour le péquin que je suis, je serais ravi d'être instruit sur le rapport avec l'énoncé inital : les arbres, les allumettes, le papier,.....
et tj pas compris ou la "bonne" réponse a pu être donnée.
merci pour vos éclairages.
Cdt

Il s'agit d'obtenir un grand nombre.
Pour cela, l'idée d'un mathématicien sera d'utiliser une fonction qui croit aussi rapidement que possible.
Et donc comment obtenir des fonctions qui croissent le plus vite possible.

[Schrodies-cat]

La bonne réponse a été donnée !!!
(...)
=> On parle d'une fonction qui correspond à un concept mathématique et donc non réitérée (du type G(x) = F(F(x)) avec F croissante > 1 au dela d'un rang donné)


=> Disons que le nombre est "légèrement" trop grand pour être représenté


(...)

Si vous vous réservez le droit d'ajouter de nouvelles règles au cours de la discussion ...
Qu'entendez-vous par "représenter" ? Il faut pour cela lister les outils mathématiques que vous acceptez dans une représentation, et non introduire des interdictions au cas par cas.

[ansset]

Il s'agit d'obtenir un grand nombre.
Pour cela, l'idée d'un mathématicien sera d'utiliser une fonction qui croit aussi rapidement que possible.
Et donc comment obtenir des fonctions qui croissent le plus vite possible.

merci, ça, j'ai fini par le comprendre.
mais dit ainsi, cela reste un "concept" ( pour moi, mais je veux bien être éclairé ) , pas une "bonne" réponse. ( au sens d'une réponse juste et claire mathématiquement ).
et tj pas de lien avec ces histoires d'arbres ( ou alors c'est sacrement tarabiscoté comme énoncé )

[Schrodies-cat]

(...)
et tj pas de lien avec ces histoires d'arbres ( ou alors c'est sacrement tarabiscoté comme énoncé )

Les deux à mon avis .

[jacknicklaus]

- le mathématicien demande à l'artisan de lui garder juste 3 arbres + une feuille de papier au physicien

Je suis comme ansset. C'est quoi le rapport entre la partie ci-dessus de l'énoncé, et la solution (laquelle, d'ailleurs?).

[Jacques 1515]

pardonnes moi, mais il me semble pas que tu l'ais pas précisée dans le fil.
ou bien ai je loupé un passage.
cela aurait certainement permis de mieux comprendre le sens de ton énigme et par là même de répondre indirectement aux interrogations ou remarques qui ont été émises par certains ici ( je pense surtout aux spécialistes des maths )
cordialement.

Je partage cet avis car par rapport à l'énoncé de l'énigme qui était clair, je n'ai lu qu'une suite de réflexions ou de remarques de haut niveau mais à aucun moment de solution clairement exposée !

[ansset]

comme on est dans le forum ludique, je propose un lien entre l'énoncé et la suite des réflexions mathématiques ( au passage fortement plus intéressantes que "l'énigme" )
je dirais que le mathématicien ( dans l'imagerie populaire du pur cérébral avec la tête qui tourne en orbite ) a cru bon de vouloir préserver 3 arbres afin de fabriquer un crayon qui lui était utile, mais qu'il n'avait pas sous la main, avec la feuille de papier , ne sachant pas fabriquer un crayon pour écrire une "formule" ou un "truc"( dont on ignore tj la nature )
ps : me suis mis volontairement en mode [humour] puisque d'on est dans le forum ad hoc.

[_Goel_]

Je sens que vous êtes à bout !
La fonction est "TREE"
A ma connaissance, il n'existe pas à ce jour de fonction naturelle (découlant d'un principe simple) qui croit plus rapidement.
TREE(1) = 1
TREE(2) = 3
TREE(3) = très grand.
Pour en revenir à la devinette, Le mathématicien a gardé 3 arbres pour figurer TREE(3).

plus d'infos ici : https://www.youtube.com/watch?v=3P6DWAwwViU
pour les non anglophones :

Considérons des séries graphes avec des nœuds de couleur. On part avec les règles suivantes :
- il faut construire une suite de graphes enracinés, le 1er ayant au maximum 1 nœud, le second au maximum 2 etc...
- Considérons un graphe avec n nœuds (chacun avec leur couleur) et leur plus proche ancêtre commun (le nœud auquel sont rattachés ces 2 nœuds, peu importe la longueur des 2 branches considérées (en terme de nombre de nœuds).
- On considère un graphe "inclus" dans un autre si il existe on peut retrouver dans le second à la fois ces nœuds et leurs ancêtres de la même couleur.
- Si on arrive à un tel cas de graphe inclus, la suite de graphes s'arrête et on compte le nombre de graphes réalisés.

TREE(n) désigne pour n couleurs de nœuds, le nombre maximal de graphes que la suite peut avoir avant de tomber inévitablement sur un graphe "contenant" un des graphes précédent.

PS : a priori, si qqn connaît un moyen de borner TREE(3) plus finement que ce que je viens de faire : bravo !
PS 2 : TREE(4) est encore moins concevable, mais fini aussi.
PS 3 : on ne peut pas prouver que TREE(n) est fini... mais pour n donné, quelque soit n entier positif, on peut prouver que TREE(n) est fini (et je suis assez perplexe du fait qu'on ne puisse pas généraliser !)
PS 4 : On peut s'amuser à penser à TREE(TREE(3)) voire à
PS 5 : si vous trouvez une fonction non récursive majorant TREE(n), ben bravo également !
PS 6 : si vous pouvez donner la valeur d'un des chiffres de TREE(3) (le premier, le dernier, on n'importe lequel au milieu), ben bravo également !

@+ Et merci pour vos efforts ! (n'hésitez pas à prolonger ce fil avec de svidéos, articles sur TREE(3) ! )

[Médiat]

Et donc le mathématicien perd si l'un des autres répond TREE(3) + 1

[Jacques 1515]

C'est un peu n'importe quoi , cet arbre qui cache la foret ...
faut faire du tri dans les énigmes

Et surtout ne pas trop s'approcher de l'infini, il y en a qui ont essayé ils ont eu des problèmes , et même sont morts fous (Cantor, Gödel, ....)

[Schrodies-cat]

Cette fonction TREE(n) m'a l'air Turing-calculable (Synonyme: récursive) d'après ce que j'ai lu.
Il me semble qu'on peut donner un algorithme la calculant,il faudrait que j'éclaircisse ça, même si la preuve de terminaison de cette algorithme demande une théorie mathématique particulièrement puissante.
Si c'est le cas, en utilisant une fonction g qui croit plus vite que toutes fonction récursive, on peut facilement majorer les valeurs de la fonction TREE, et de toute autre fonction analogue.

Et si on cherche simplement une fonction récursive qui majore strictement TREE, la méthode de Médiat marche très bien.

[Deedee81]

Salut,

Et donc le mathématicien perd si l'un des autres répond TREE(3) + 1

J'y avais pensé et ça m'a fait aussi penser à une question amusante. Appelons les trois protagonistes A, B et C ainsi que le nombre qu'ils proposent.

A propose max(B,C)+1
B propose max(A,C)+1
C propose max(A,B)+1

Que se passe-t-il ? Ils gagnent tous les trois ?

[Schrodies-cat]

Si on fait entrer dans le jeu des devins ...
Tous ont perdu car ils n'ont pas défini de nombre !
Il ne peut donc exister qu'un devin.
Tiens ! Je n'ai pas comme Kurt Gödel une preuve de l'existence de Dieu, mais j'ai une preuve de son unicité ! (dans le cas de dieux omniscients)

Je ne suis pas devin, mais j'avais deviné que Goel nous proposerait quelque chose à base de fonctions calculables.
D'où mon idée d'utiliser une fonction qui croit plus vite que toute fonction calculable.

Comment je procède:

Je dispose d'un langage L de description d'algorithme.
Je définit ma fonction M ainsi : M(n) est le plus grand nombre qu'on puisse calculer par un algorithme de longueur n dans L.
Ma fonction M est définie à partir d'un certain rang et strictement croissante. (pour cela, je prévois dans L une instruction élémentaire permettant d'incrémenter le résultat final)

Comment faire mieux que TREE(3) , je prends simplement M(a+1), où a est la longueur d'un algorithme calculant TREE(3)

Comment faire mieux tout nombre défini à partir de fonctions calculable ?
Je prends M(b+1) ou b est le nombre maximal de symboles qu'on puisse écrire sur le papier dont on dispose,
Il me faut une certaine quantité de papier pour définir M et proposer M(b+1) , mais cela reste limité.

Bien sur, ma fonction n'est pas récursive.
Sa définition n'est pas récursive en raison du théorème d'indécidabilité de l’arrêt de Turing, et on peut montrer, avec des techniques classiques de théorie de Turing, qu'elle croit plus vite que toute fonction calculable.

Après tout, un mathématicien ne s'interdit pas de considérer des fonctions non calculables !