Discussion :

[bosskev62]

bonjour

j'ai une question qui me trotte dans la tête depuis un certain temps maintenant :
est-ce qu'il existe un algorithme capable de vérifier si un nombre est bien un nombre univers ou pas ?

d'avance !

[yahiko]

Si tu trouves l'algo, tu devrais certainement remporter la médaille fields.

[tbc92]

Imaginons que cet algorithme existe.
Dans ce cas, vérifions si racine(2) est un nombre univers ou pas.... et mettons à jour Wikipédia et tous les sites qui disent que personne ne sait si racine(2) est un nombre univers ou non.

[Obsidian]

Si je ne dis pas de bêtise, un nombre univers est un nombre qui contient tous les nombres de longueur finie (ou plus précisément n'importe quelle suite finie de chiffres), du style :

0,12345678910111213141516…

Comme il y a une infinité de nombre finis, il est impossible de savoir si un nombre, rédigé comme ci-dessus, est un nombre univers pour la bonne raison que sa longueur sera infinie et que tu ne pourras jamais le lire en entier pour pouvoir trancher. Par contre, si on te donne un nombre de longueur finie, aussi grande soit-elle, tu peux immédiatement en conclure que ce n'est pas un nombre univers.

Après, si le nombre en question est en fait une formule algébrique, c'est une autre histoire.

[Flodelarab]

Bonjour,

pour la bonne raison que sa longueur sera infinie et que tu ne pourras jamais le lire en entier

Cette réflexion est fausse.
Voici un nombre: 987/999=0.987987987987987987987987...
Son écriture est infinie. Mais je peux te donner toutes ces décimales et te prouver que ce n'est pas un nombre univers.
On ne peut pas exclure la possibilité théorique de trouver un nombre univers dont on serait capable de définir chaque décimale et prouver qu'il est capable, dans sa mantisse, de contenir n'importe quel nombre entier.

[OlivANoyaux]

On ne peut pas exclure la possibilité théorique de trouver un nombre univers dont on serait capable de définir chaque décimale et prouver qu'il est capable, dans sa mantisse, de contenir n'importe quel nombre entier.

Hum... Ca ferait quand même une boucle infinie, non ? Parce que si on doit tester tous les entiers ça en fait un paquet quand même. Après il me semble que si on veut montrer qu'un nombre est un nombre univers il faut être capable de définir chaque décimale sinon même mathématiquement on va avoir du mal...

[Obsidian]

Cette réflexion est fausse.
Voici un nombre: 987/999=0.987987987987987987987987...
Son écriture est infinie. Mais je peux te donner toutes ces décimales et te prouver que ce n'est pas un nombre univers.

C'est ce que j'expliquais au-dessus : si on te donne le nombre sous forme de fraction, tu peux tout de suite en tirer les bonnes conclusions, mais si je te passes « 0.987987987987987987987987... », tu ne pourras être sûr que c'est vraiment la valeur correspondant à la fraction en question qu'à partir du moment où tu l'auras lu en entier, ce qui n'est pas possible avec un nombre à la longueur infinie.

[Flodelarab]

En substance, vous dites tous les deux la même chose, et c'est faux! N'ayez pas peur de l'infini. Ce n'est pas parce que quelque chose est infinie qu'on ne peut rien prouver.

Je n'ai pas besoin de calculer tous les 1/x pour x de plus en plus grand, pour savoir que le résultat tend vers 0. Et pourtant, il y a une infinité de valeurs que vous voudriez calculer.

Je n'ai pas besoin de couper un gâteau en 2, puis en 2, puis en 2, à l'infini, pour savoir que la somme des miettes tend vers 1 gâteau. Pourtant la découpe que vous voudriez réaliser est infinie.

Un homme (comment s'appelle-t-il ? ) a passé sa vie a cherché une fonction continue partout et dérivable nulle-part. Et il a fini par la trouver.
Donc courage: cherchez ce nombre univers.

[OlivANoyaux]

Un homme (comment s'appelle-t-il ? ) a passé sa vie a cherché une fonction continue partout et dérivable nulle-part. Et il a fini par la trouver.

Son nom c'est Weierstrass il me semble, et il a fait plein d'autres choses (le théorème de Bolzano-Weierstrass est un résultat "classique" d'analyse).

Ce que l'on dit c'est que d'un point de vue purement informatique l'infini est problématique. D'un point de vue mathématique heureusement qu'on arrive à considérer l'infini. Et en plus on a déjà trouvé des nombres univers mathématiquement : l'exemple d'Obsidian en est un par définition mais il y en a plein d'autres ! Trouver un nombre univers c'est pas trop compliqué, prouver mathématiquement qu'un nombre "au hasard" est univers peut être très compliqué (exemple de pi ou e), prouver informatiquement q'un nombre est univers est impossible. Voilà ce qu'on dit (enfin pour ma part, peut-être qu'Obsidian n'adhère pas).

[picodev]

Bonjour,

Reprenons la question :

est-ce qu'il existe un algorithme capable de vérifier si un nombre est bien un nombre univers ou pas ?

Ce que j'interprète comme « existe-t-il un algorithme qui prend un `nombre´ en entrée et qui répond «oui» si ce nombre a la propriété d'être un nombre univers en base 10 (non précisé dans la question d'origine et arbitrairement fixé) et «non» dans le cas contraire . `nombre´ en entrée signifiant algorithme permettant de calculer un nombre réel avec une précision arbitraire (définition de nombre calculable).»

Je pense qu'il faut y réfléchir mais que ce problème de décision a un grand goût d'indécidabilité, voir le théorème de Rice.

...
Trouver un nombre univers c'est pas trop compliqué, prouver mathématiquement qu'un nombre "au hasard" est univers peut être très compliqué (exemple de pi ou e), prouver informatiquement q'un nombre est univers est impossible.
...

Si on arrive à le prouver mathématiquement on arrive forcément à le prouver informatiquement, pour autant qu'il y ait une différence entre les deux.

[OlivANoyaux]

Si on arrive à le prouver mathématiquement on arrive forcément à le prouver informatiquement, pour autant qu'il y ait une différence entre les deux.

Ok, j'avais mal compris la question : je parlais de l'exécution pratique d'un tel algorithme. Pour le reste, je n'en ai aucune idée : ça sort très largement de mes modestes compétences.

[yahiko]

Je pense qu'il faut y réfléchir mais que ce problème de décision a un grand goût d'indécidabilité, voir le théorème de Rice.

Je pense effectivement qu'il y a un lien également entre un algorithme pour savoir si un nombre est un nombre univers et le problème de l'arrêt, sachant qu'un nombre est une forme de programme au sens de Turing.
Évidemment seuls des experts du domaine pourraient confirmer cette intuition.

[Obsidian]

En substance, vous dites tous les deux la même chose, et c'est faux! N'ayez pas peur de l'infini. Ce n'est pas parce que quelque chose est infinie qu'on ne peut rien prouver.

Ce n'est absolument pas ce que l'on a dit.

L'auteur veut savoir s'il existe un algorithme universel qui permet de déterminer si un nombre est un nombre univers et la seule chose que j'ai affirmée, peut-être de manière confuse, c'est qu'il ne pourra pas le savoir si ce nombre est passé uniquement sous sa forme numérique. Il faudra au minimum des informations complémentaires : si j'écris 0,123123123123123123… je vois bien qu'il s'agit d'un développement décimal périodique qui peut se résoudre en 123 ÷ 999… mais ce n'est qu'une hypothèse ! Si je suis obligé de m'arrêter aux points de suspension soit par limitation de la taille de mes registres, soit parce qu'il faut poser une limite arbitraire, rien ne me permet de savoir si c'est un nombre exact fini, continuant donc en « 0000… », si c'est un développement périodique « 123123123… » ou s'il va finir par dégénérer vers n'importe quelle autre valeur.

Il lui faudra forcément des indications mathématiques qui lui permettront de faire de l'analyse.