Bon, comme les énigmes sur les nombres semble irrésistibles à la perspicacité de certains, en voici une autre :
Existe-t-il un nombre qui soit le plus petit nombre entier ne pouvant pas être décrit avec moins de cinq cents mots ?
Décidément, j’adore tes énigmes. Même si je trouve, elle est néanmoins superbe!
TRES GROS INDICE (ne pas lire si vous cherchez)
Non, la réponse étant pratiquement dans la question.
Ca me fait penser au paradoxe de l’ensemble des ensembles qui ne se contiennent pas eux-mêmes.
Une énigme plus profonde qu’elle ne parait au premier abord
En posant correctement le problème, c’est à dire en définissant ce qu’est un mot et, surtout, ce que signifie “pouvant être décrit”, on peut trouver qu’un tel nombre existe, puisque l’énnoncé ne se placera pas dans l’alphabet admis, mais ça fait appel à des notions assez avançées (machines de Turing, …)
En plus, je trouve que le verbe “décrire” est assez maladroit, j’aurais plutôt utilisé “défini”, ou au moins “complètement décrit”.
<\invisible>
Mais ça reste une bien belle énigme.
Etienne
J’en ai posé une du même genre. Est-ce la même ? Le même genre ?
Topic : “Encore des maths (mais pas de calcul)”
Richard dit:J'en ai posé une du même genre. Est-ce la même ? Le même genre ?
Topic : "Encore des maths (mais pas de calcul)"
Désolé, ça n'a absolument rien à voir.
Dans celle-là, il n'y a pas d'arithmétique, et même pas de nombre du tout.
Etienne
Je ne sais pas pourquoi je repensais à cette énigme, mais rendez-vous compte de ce qui est dit ici?
1- il n’existe pas un nombre entier qui soit le plus petit nombre entier ne pouvant pas être décrit en moins de 500 mots.
2- et pourtant il existe une infinité de nombres entiers ne pouvant pas être décrits en moins de 500 mots.
3- mais alors s’il y en a une infinité, pourquoi n’y en a-t-il pas un plus petit…
QUESTION 1: démontrez l’affirmation 1 (facile)
QUESTION 2: démontrez l’affirmation 2 (moyen)
QUESTION 3: expliquez le paradoxe (difficile)
(la notion de “pouvant être décrit” n’est pas maladroite à mon sens, considérez qu’il faut pour cela utiliser des mots ou des nombres de n’importe quel langage ou dialecte, et tout le bagage culturel que vous voudrez)
En tout cas moi, la question 3 me turlupine drolement…
(et oui je sais, je ferais mieux de travailler sur un autre parcours d’énigmes très compliquées… 
)
nim (fichu cookie) dit:(et oui je sais, je ferais mieux de travailler sur un autre parcours d'énigmes très compliquées...
Je ne te le fais pas dire
I.
D’abord, la démonstration de l’énigme initiale.
Supposons qu’il existe un nombre, tel qu’il soit le plus petit ne pouvant
être défini en moins de 500 mots.
Or, ce nombre peut être défini de la façon suivante : « le plus petit nombre
ne pouvant être défini en moins de 500 mots », c’est à dire par une
définition comportant bien moins de 500 mots, ce qui est absurde. Donc il
n’existe pas de tel nombre.
II.
Maintenant les parties plus sérieuses.
On définit d’abord mathématiquement quelques notions
D’abord, on se donne une machine de Turing générale T, munie d’un alphabet A.
(Pour ceux qui ne savent pas, un machine de Turing générale est l’expression mathématique d’un ordinateur muni d’une mémoire infinie, et d’un langage de programation qu’on appelle l’alphabet.)
Étant donné qu’on considère un alphabet, on va considérer non pas un nombre défini en n mots, mais par un mot de n lettres (ce qui revient au même)
On dit q’un mot définit un nombre si, lorsque ce mot est appliqué à la machine de Turing dans son état initial (des 0 partout, par exemple), elle s’arrète dans une configuration contenant exactement une représentation de ce nombre sur le ruban.
Pour chaque machine de Turing, il existe un nombre fini de mots de moins de n lettres ( (card(A))^n), et ils ne « définissent » pas tous un nombre, de la même façon qu’un assemblage aléatoire de mots n’a pas forcemment un sens dans une langue), et les nombres qui sont définis par un mot ne sont pas forcemment définis de façon unique.
Par conséquent, il existe un nombre fini de nombres définis par un mot de moins de n lettres, ce nombre étant borné par (card(A))^n, et par conséquent également un nombre infini d’entiers ne pouvant être définis par un mot de moins de n lettres.
L’ensemble des entiers naturels étant totalement strictement ordonné, il existe dans cet ensemble un plus petit élément.
III.
La troisième démonstration est la plus délicate. Elle impose de raffiner la signification de « défini », en introduisant la notion de « calculabilité ». Un nombre est calculable si, étant donné une machine de Turing, il existe un programme (un mot) pour lequel la machine de Turing s’arrète dans un état représentant ce mot. Cela correspond donc à ce qui peut être calculé par un ordinateur infini, un un temps fini non borné.
Étant donné un mot, il n’est pas calculable de déterminer son exécution par une machine de Turing générale termine ou non (théorème).
Cela signifie qu’une machine de Turing ne peut pas savoir si un mot définit ou non un nombre (plus précisemment, c’est semi-calculable, ce qui signifie que la machine de Turing va trouver en un temps fini, mais non borné, si le mot définit un nombre, mais il sera impossible de savoir si le mot ne correspond à aucun nombre)
Par conséquent, si on écrit un programme qui parcourt tous les mots de moins de n lettres, en cherchant le plus petit nombre non calculé, il ne terminera pas, et il ne permettra pas de calculer un nombre. Ceci est exactement la version mathématique (ou informatique, au choix), de l’énnoncé initial, lorsque le programme lui-même comporte moins de n lettres.
Par conséquent, bien que pour toute machine de Turing il existe un plus petit nombre ne pouvant être calculé par un mot de moins de 500 lettres, mais ce nombre n’est pas calculable par une machine de Turing.
Ce nombre existe bien, mais il n’est pas calculable.
Cette différence (existe mais non calculable), était noyée dans la première
démonstration dans la nature du mot «défini», qui signifiait parfois existance et unicité, et parfois calculabilité.
Lorsque les mots sont correctement définis, il n’y a plus de paradoxe:
« Le plus petit nombre ne pouvant calculé à partir d’un énnoncé de moins de 500 mots »
Il est bien défini par cette définition (existance, unicité et propriétés), mais on ne peut pas le calculer, ce qui ne contredit pas l’énnoncé initial.
Au mieux, on peux trouver une borne inférieure, et même programmer une machine de Turing qui trouve une suite de bornes inférieures de plus en plus grandes, les nombres les plus grands qui sont calculables à partir d’un mot de moins de n lettres, mais au bout d’un temps fini, on ne saura jamais si le nombre le plus grand trouvé à l’heure actuelle est effectivement le plus grand nombre possible.
Cette démonstration n’est bien sûr pas totalement rigoureuse, mais je pense qu’elle est assez proche d’une solution correcte. On pourrait bien sûr fixer la machine de Turing et l’alphabet, et exprimer directement l’énigme dans cet alphabet, mais je ne pense pas que ce soit nécessaire.
Étienne
PS. : Quand je disais qu’il s’agit d’une énigme plus profonde qu’elle n’en a l’air…
J’ai modifié ma réponse précédente, car elle contenait un certain nombre d’imprécisions, et même d’erreurs, mais le fond est le même.
Étienne
C’est terriblement impressionant tout ça Etienne S. Tu me vois ébahi par ton intervention.