Un nombre réel non calculable

Bonsoir,

dans les questions un peu tordues, voici la mienne :

Quelqu'un peut-il exhiber un nombre réel qu'une machine de Turing ne peut pas calculer ?

Puisqu'il existe un nombre dénombrable de machines de Turing, et un nombre indénombrable de réels, il doit en exister beaucoup. Il s'agit donc de trouver un nombre réel pour lequel il n’existe pas d'algorithme qui permette de le calculer…

Je cherche, je cherche, mais pas si simple de trouver une réponse.

Bonne soirée

P.S. Si c'est compliqué de trouver un tel nombre, ne devrions-nous pas faire des mathématiques constructives seulement ? Après tout, le tiers-exclu, c'est un peu du bullshit non ? Est-ce qu'$\aleph_1$ existe bel et bien ?

Je ne comprends pas tout a fait la question non plus et a priori je dirais la meme chose que GuilOoo, a savoir un developpement infini.

Cependant, il faut faire attention car un changement de base peut fausser cela. Par exemple, $0.1$ a un developpement en decimal fini, mais pas un developpement binaire fini, ce qui fait par ailleurs qu'il n'est pas representable en machine de maniere exacte.

Je l'ai précisé dans mon premier post il me semble : calculer un réel signifie que tu peux trouver un algorithme qui peut le calculer.

Une machine de Turing à une mémoire infinie, donc si la représentation réelle est infinie, ça ne pose pas de problème. Il suffit juste d'avoir un algorithme qui calcule ce nombre.

L'exemple que propose GuilOooo est en effet ce que je recherchais. Je me souvenais d'avoir vu un autre exemple plus compliqué une fois, et du coup je cherchais beaucoup plus compliqué .

Je pinaille pour le plaisir de pinailler…

1
2
3

struct rationnel {
    int numerateur, denominateur;
} unsurdix = {1, 10};

On l'a bien représenté en valeur exacte, et ce n'est pas très compliqué de créer les opérations pour calculer avec.

Arithmetique flottante sous-entendue. Sinon, essaye de representer Pi avec cela.

Quitte à pinailler, autant dire qu'en français on écrit $0,1$ et pas $0.1$…

Arithmetique flottante sous-entendue.

Depuis 2008 le decimal32 est ton ami.

Cela ne change rien. Cela reste de l'arithmetique flottante qui ne permet pas de representer correctement des reels, meme sur sa plage de representation. Cela permet tout au plus d'avoir une plage differemment distribuee (la distributions des reels est logarithmique avec les doubles, et un peu plus complexe en prenant en compte les denormalises) et de meilleures erreurs d'affectation (et il me semble pas selon tous les modes. Je suis sur pour l'erreur de troncature basse et haute mais pas pour l'arrondi a l'infini).

Le decimal32 permet aussi de mieux gerer certaines erreurs liees aux operations sur les flottants, les erreurs de cancellation et d'absorption notamment.

Il ne s'agit que d'une forme de representation, qui presente un certain nombre d'avantages par rapport a d'autres, plus anciennes. Le probleme de representation exacte des reels en machine est de toute maniere resolu : elle n'existera jamais.

EDIT: Et pour la petite histoire, ce format a ete cree pour permettre les arrondis exacts de fonctions logarithmiques et exponentielles, en plus des fonctions elementaires de l'arithmetique (+,-,x,/).

Il convient de spécifier ce que tu entends par représentation Hod, car avec le calcul formel, on peut avoir une représentation d'un nombre réel exacte en machine, seulement cette représentation ne correspond pas à une représentation de ce nombre dans une base quelconque.

Je suis d'accord avec Saroupille. Si je citais le decimal32, c'était simplement pour dire qu'il est maintenant possible de représenter 0,1 en valeur exacte même avec de l'arithmétique flottante (ça faisait déjà longtemps que c'était possible en virgule fixe, mais là, on gagne un cran).

Ensuite, il est sans doute impossible de représenter tous les nombres réels sans exception sur une machine, mais avec le mode adéquat de représentation, je pense que l'on est capable de représenter tous les nombres que nous sommes effectivement amenés à manipuler.

Par exemple, $e^{\frac{i\pi}4}$ pourra assez facilement être représenté en Haskell-style comme ça.

1

Exponentielle (Fraction (Produit Imaginaire Pi) 4)

Le tout est d'avoir les fonctions adéquates pour calculer avec, mais si on se cantonne à la représentation, on a vite fait le tour des outils usuels.

Je l'ai précisé dans mon premier post il me semble : calculer un réel signifie que tu peux trouver un algorithme qui peut le calculer.

Ça n'est pas suffisant : le réel étant infini, ta machine de Turing ne s'arrêtera jamais. Dans ces conditions, quand estimes-tu que tu as «calculé» un réel ? Certains travaux proposent une condition du style : «la machine ne s'arrête pas mais pour tout indice i, à partir d'un certain temps t, la machine ne touchera plus au i-ème bit du réel». L'idée est que plus le temps passe, plus ta machine possède une bonne approximation du réel voulu. Certains travaux proposent également des conditions sur t en fonction de i, par exemple «t est un polynôme de i».

Pour répondre à la remarque de Höd sur le changement de base : l'opération de changement de base étant calculable, si on se donne «mon» réel dans n'importe quelle base, on sera quand même capables de résoudre le problème de l'arrêt via une simple réduction. (Et ainsi en est-il de tout codage d'un réel qui soit calculable, dans le sens où il est décidable de retrouver le i-ème bit du réel à partir de son codage).

Concernant les représentations des réels : ne vous fatiguez pas, les gens, il n'y a qu'une quantité dénombrable de choses qu'on peut représenter dans la mémoire de nos bons vieux ordinateurs VS une quantité indénombrable de réels.

Edit : correction orthographique

L'arithmetique en virgule fixe ne permet pas plus de representer $0.1$ en base $2$. Il est certes representable en base 10 en virgule fixe. Maintenant quid des nombres univers ? Sachant qu'ils sont denses dans $\mathbb R$ cela en fait un sacre paquet d'oublies.

Ensuite, il est sans doute impossible de représenter tous les nombres réels sans exception sur une machine, mais avec le mode adéquat de représentation, je pense que l'on est capable de représenter tous les nombres que nous sommes effectivement amenés à manipuler.

Tu ne peux pas representer en machine $0.1$ en base 2. Ou alors on pourrait passer dans une autre base, comme le fait decimal32 qui emule de la base 10 sur une petite plage. Et la encore, selon la base certains nombres auront un developpement $p$-adique non fini. Donc a moins de changer dynamiquement la base selon le reel a representer (ce qui n'est pas sans poser des soucis techniques et theoriques - cf. argument de la diagonale de Cantor), mais admettons), tu ne pourras pas representer tous les reels.

Ceci dit, meme dans une meme base, on pourra toujours trouver un reel avec un nombre fini de decimal qui ne sera pas non plus representable avec decimal32 ou decimal128 car en dehors de la plage de representation. Tu auras beau augmenter la taille de codage de ton reel, tu trouveras toujours un autre reel avec un nombre fini de decimal qui ne sera pas representable.

Comme dans tout ouvrage sur le calcul sur machine, j'appelle representation machine d'un nombre, la maniere dont est stockee un nombre en machine (souvent en base 2 pour des raisons evidentes).

Tu peux definir le corps des flottant $\mathcal F$ et le corps des reels $\mathbb R$ et etudier les liens entre les deux.
Soit $x \in \mathbb R$, s'il existe un nombre $X \in \mathcal F$ tel que $x - X = 0_{\mathbb R}$ alors $x$ est representable dans $\mathcal F$. J'insiste sur le fait qu'il s'agit du zero du corps des reels et pas celui du corps des flottants.

Comment tu representes $e$ et $\pi$ en machine ? Et tu pourras toujours me dire on code $e$ par la lettre $e$ et $\pi$ par $p$ par exemple. Mais evidemment, sur un exemple particulier tu peux toujours trouver un systeme de representation qui va coller. Le but c'est de pouvoir representer tout le corps des reels et pas un sous-ensemble qui arrange.

En d'autres termes, la question est de savoir s'il existe une mecanisme qui permet de stocker une quantite infinie d'information sur un support disposant d'une capcilite non-infinie. Clairement la repons est non.

Pour répondre à la remarque de Höd sur le changement de base : l'opération de changement de base étant calculable, si on se donne «mon» réel dans n'importe quelle base, on sera quand même capables de résoudre le problème de l'arrêt via une simple réduction. (Et ainsi en est-il de tout codage d'un réel qui soit calculable, dans le sens où il est décidable de retrouver le i-ème bit du réel à partir de son codage).

En fait la question que je me posais etait: si je te donne un nombre reel dans une base $b_1$ tel que son developpement dans cette base est infini, est-il possible de determiner en un temps fini une base $b_2$ dans laquelle ce reel a un developpement fini ? Je dirais non a premiere vue mais tu as peut etre des informations. La seconde question serait : peux-tu determiner que le developpement est infini a partir d'une entree quelconque et d'une base donnee ? La encore je dirais non mais je n'en suis pas sur.

En fait la question que je me posais etait: si je te donne un nombre reel dans une base $b_1$ tel que son developpement dans cette base est infini, est-il possible de determiner en un temps fini une base $b_2$ dans laquelle ce reel a un developpement fini ?

Si je ne me trompe pas, un réel $x$ a un développement fini dans la base $b$ ssi $x$ est un rationnel dont le dénominateur est une puissance de $b$, ou quelque chose du style. (Peu importe la condition exacte)

Le simple fait de déterminer si $x$ est rationnel implique de vérifier que son développement dans une base quelconque est fini ou périodique. Étant donné que l'on ne peut pas vérifier si le développement est périodique sans lire toute l'entrée, ça risque d'être tendu. (Avec un argument de théorie de l'information, on doit pouvoir dire qu'il est impossible de déterminer si l'entrée est périodique rien qu'à partir de ses $n$ premiers chiffres… ça paraît assez évident).

Encore une fois, je ne suis pas très à l'aise avec la question car on parle de manipuler une suite de symboles infinies avec une machine de Turing, qui n'est pas prévue pour ça. Je serais curieux de voir dans quel modèle de calcul vous vous placez (perso, je prends des MT à temps ordinal pour me faire une intuition).

Donc tu as un réel $x$ dans une base $b_1$ donné en entrée, ainsi qu'une base $b_2$ donnée en entrée, et tu te demandes si le développement de $x$ en base $b_2$ est infini ? Àmha en toute généralité c'est indécidable avec une MT classique, à cause d'un effet de «la MT ne peut lire qu'une partie finie de l'entrée, de longueur disons $K$, et je peux construire un réel dont le $K+1$-ème chiffre fait tout capoter».

Avec une MT à temps ordinal on s'en sort sans trop de problèmes, par contre.

Ok, j'avais en effet ce genre d'idées en tête de façon implicite.

L'arithmetique en virgule fixe ne permet pas plus de representer $0.1$ en base $2$.

Bien sûr que si, c'est même à ça qu'elle sert. Et c'est pour ça qu'elle est massivement utilisée dans les logiciels qui touchent à la compta et à la finance. Le système de virgule fixe représente des nombres de la forme $xenbase2 \ \times \ 10^{-n}$.

Mais evidemment, sur un exemple particulier tu peux toujours trouver un systeme de representation qui va coller.

Oui, c'est exactement de ça qu'on parle. D'ailleurs si tu relis ce que j'ai écris, tu y trouveras le bout de phrase suivant.

mais avec le mode adéquat de représentation, je pense que l'on est capable de représenter tous les nombres que nous sommes effectivement amenés à manipuler

Lequel annonce clairement la couleur. Il ne s'agit pas de représenter l'ensemble de tous les réels sans exception mais uniquement ceux qui peuvent effectivement avoir un sens.

Le but c'est de pouvoir representer tout le corps des reels et pas un sous-ensemble qui arrange.

Non. Ça on sait très bien que c'est impossible. Même les maths pures ne permettent pas de représenter n'importe quel réel, seulement ceux qui procèdent d'une combinaison d'opérations plus ou moins variées. Le but (alternatif, puisqu'on a déjà répondu depuis bien longtemps à la question de départ), c'est de savoir si on peut représenter informatiquement tous les nombres que les maths elles-mêmes sont capables de représenter et de les manipuler. Et globalement, la réponse semble pencher vers un oui.

Comment tu representes $e$ et $\pi$ en machine ? Et tu pourras toujours me dire on code $e$ par la lettre $e$ et $\pi$ par $p$ par exemple.

Tu les représentes comme $e$ et $\pi$ de la même manière que les maths les représentent $e$ et $\pi$ quand elles veulent travailler en valeur exacte. Leur représentation numérique n'est utilisée que quand on cherche une approximation convenable du résultat. Si l'informatique veut travailler avec des valeurs exactes, elle doit utiliser une simple représentation symbolique comme on fait en maths.

Et cela est assez simple à faire au moyen du typage algébrique des données. C'est d'ailleurs plus ou moins pour résoudre cette difficulté technique de la représentation exacte des réels qu'il a été inventé dans les années 1970.

Bien sûr que si, c'est même à ça qu'elle sert. Et c'est pour ça qu'elle est massivement utilisée dans les logiciels qui touchent à la compta et à la finance. Le système de virgule fixe représente des nombres de la forme $xenbase2 \ \times \ 10^{-n}$.

Essaye à la main de faire le développement dyadique de 0.1 en machine. Ce n'est pas possible en espace fini. Tu peux faire un petit test, ecrire un programme C / C++ qui affiche 0.1 en float (ou double) et utilise gdb pour afficher sa représentation. Fait la différence avec le développement dyadique fait « à la main », le résultat n'est pas zéro.

Et aussi, cela n'a jamais été inventé pour cela et cela ne sert pas à cela ni ne permet d'échapper aux problèmes d'erreur de cancellation, d'absorption et la propagation des erreurs d'affectation.

Non. Ça on sait très bien que c'est impossible. Même les maths pures ne permettent pas de représenter n'importe quel réel, seulement ceux qui procèdent d'une combinaison d'opérations plus ou moins variées. Le but (alternatif, puisqu'on a déjà répondu depuis bien longtemps à la question de départ), c'est de savoir si on peut représenter informatiquement tous les nombres que les maths elles-mêmes sont capables de représenter et de les manipuler. Et globalement, la réponse semble pencher vers un oui.

Les maths ne sont pas « pures » ou non pures et ce ne sont pas non plus une personne qui est « capable de quelque chose ». Je ne comprends donc pas ton « Même les maths pures ne permettent pas de représenter n'importe quel réel ». À la question « peux-tu représenter en machine un réel tiré aléatoirement sur la droite des réels » la réponse est non. Est-ce que tu peux représenter symbolique un certain jeu fini de nombre, la réponse est oui, mais pas intéressante.

Aucune représentation machine exacte des réels n'existe. Et si tu parles de calcul formel, ce n'est pas la même chose, et si c'est utilisé que de manière assez anecdotique en dehors (d'une certaine partie) du monde académique c'est peut être parce qu'on se heurte à de très gros soucis malgré l'intérêt intellectuel derrière ?

Essaye à la main de faire le développement dyadique de 0.1 en machine. Ce n'est pas possible en espace fini. Tu peux faire un petit test, ecrire un programme C / C++ qui affiche 0.1 en float (ou double) et utilise gdb pour afficher sa représentation. Fait la différence avec le développement dyadique fait « à la main », le résultat n'est pas zéro.

Et aussi, cela n'a jamais été inventé pour cela et cela ne sert pas à cela ni ne permet d'échapper aux problèmes d'erreur de cancellation, d'absorption et la propagation des erreurs d'affectation.

Tu le fais exprès ? Je te parle de virgule fixe et tu me dis de jouer avec C et les float qui, comme leur nom l'indique, sont des nombres à virgule flottante. Seulement pour ça, il faut utiliser un langage qui implémente l'arithmétique en virgule fixe. Genre…

Un nombre à virgule fixe est fondamentalement stocké en mémoire comme un entier, c'est tout l'intérêt. Ton $0,1$ pourra être stocké tout simplement comme $00000001$ (sur 8 bits), du moment que le langage qui s'en sert sait qu'il faut le multiplier par $10^{-1}$. Et un langage comme COBOL en est parfaitement capable.

Oui donc 0.1 n'est toujours pas représenté en base 2.

EDIT: Je parlais de float parce que c'était le plus simple pour tester, mais essaye de stocker en virgule fixe 0.1 base 2 et fait la différence avec le développement dyadique exact.