nombre calculable

Demandons successivement une, deux, puis mille décimales de √2. Une même recette finie peut répondre à chaque demande : elle poursuit le calcul jusqu’au rang choisi, sans devoir connaître d’avance toutes les décimales.

C’est cette possibilité, et non le fait d’avoir déjà imprimé beaucoup de chiffres, qui rend un nombre calculable. La précision peut être aussi exigeante que l’on veut ; l’algorithme doit seulement terminer pour chaque précision fixée.

Un réel x est calculable s’il existe un algorithme qui, pour tout entier naturel n demandé, termine et produit un nombre rationnel q_n approchant x avec l’erreur garantie suivante : $\mathrm{\mid }x-q_n\mathrm{\mid }\le 2^{-n}|x-q\_n|\backslash leq\; 2^\{-n\}$. Choisir une autre règle effective de précision, par exemple 10⁻ⁿ, donne la même notion. Une formulation équivalente fait produire à une machine de Turing les chiffres d’une écriture décimale jusqu’à tout rang demandé, avec une convention fixée pour les écritures qui se terminent par une infinité de 9.

Alan Turing a formalisé cette notion en 1936. Tous les nombres algébriques réels sont calculables. Certains nombres transcendants, notamment π, le sont aussi, tout comme la constante d’Euler-Mascheroni. Les réels calculables sont stables par addition, soustraction, multiplication et division par un nombre non nul : ils forment un corps.

Il n’existe qu’un ensemble dénombrable d’algorithmes, donc seulement un ensemble dénombrable de réels calculables. Comme l’ensemble des réels ne l’est pas, la grande majorité des réels sont non calculables. Enfin, un nombre complexe est calculable exactement lorsque sa partie réelle et sa partie imaginaire le sont toutes les deux.

Calculons √2 jusqu’à trois chiffres après la virgule sans supposer ces chiffres connus. L’idée consiste à chercher un entier dont le carré encadre exactement 2 multiplié par une puissance de 100.

Données :
le nombre visé est le réel positif x tel que x² = 2 ;
la précision demandée est 10⁻³ ;
on cherche le plus grand entier m tel que m² ≤ 2 × 10⁶.

1. Un calcul entier donne 1414² = 1 999 396.
2. L’entier suivant donne 1415² = 2 002 225.
3. Ainsi, 1414² ≤ 2 000 000 < 1415².
4. Comme les trois nombres sont positifs, on peut prendre leurs racines et diviser par 1000 :

Le résultat est donc √2 = 1,414… avec une erreur strictement inférieure à 0,001 si l’on retient 1,414. Le contrôle consiste à refaire les deux carrés qui encadrent 2 000 000. Pour obtenir n chiffres après la virgule, la même procédure compare des carrés d’entiers autour de 2 × 10²ⁿ : elle ne dépend pas d’une limite fixée au nombre de chiffres.

Pour montrer qu’un réel est calculable, on décrit un algorithme qui accepte une précision quelconque et dont on justifie l’arrêt ainsi que l’erreur. Donner une longue liste de décimales ne suffit pas : il faut une procédure valable au-delà de la liste.

Pour √2, les comparaisons de carrés fournissent un encadrement rationnel de largeur 10⁻ⁿ. Si seules trois décimales sont nécessaires, l’encadrement [1,414 ; 1,415[ suffit ; si davantage sont demandées, on reprend exactement le même critère avec une puissance de 10 plus grande.

Pour un nombre complexe, le test se fait séparément sur ses deux coordonnées. Une procédure pour la seule partie réelle ne suffit pas : il faut aussi pouvoir approcher la partie imaginaire avec toute précision prescrite.

Calculable et rationnel. Un rationnel possède une écriture fractionnaire et est calculable, mais la réciproque est fausse : √2 et π sont calculables sans être rationnels. Le critère décisif est l’existence d’un algorithme d’approximation, pas la fin ou la périodicité des décimales.

Calculable et algébrique. Tout réel algébrique est calculable, mais certains transcendants le sont également. π tranche le cas : il est transcendant et pourtant un algorithme peut l’approcher à toute précision demandée.

Défini et calculable. Une définition mathématique peut caractériser un réel sans fournir un algorithme pour ses chiffres. Les nombres Ω de Chaitin sont définis à partir de machines de Turing universelles, mais ils ne sont pas calculables.

Une précision fixe ne suffit pas. Un programme qui livre seulement 1,414 pour √2 répond à la demande 10⁻³, mais ne prouve pas à lui seul la calculabilité. Il faut pouvoir fournir un résultat pour chaque entier n qui fixe la précision.

Les décimales ne doivent pas masquer la garantie d’erreur. Une suite de chiffres imprimés peut être longue sans que leur exactitude soit établie. Il faut accompagner la sortie d’un encadrement ou d’une borne d’erreur, comme 1,414 ≤ √2 < 1,415.

Une définition par machine n’est pas forcément un calcul. Pour un réel non calculable, connaître une infinité de chiffres isolés ne fournirait pas nécessairement une méthode uniforme pour atteindre chaque rang. Pour un nombre Ω de Chaitin, la machine universelle intervient dans la définition, mais, dans un système de preuve fixé, seuls un nombre fini de bits peuvent être certifiés en général. Dans aucun cas cela ne produit l’algorithme exigé.

Dénombrable ne signifie pas fini. Il existe une infinité de réels calculables, mais leurs algorithmes peuvent être rangés dans une liste. Le contraste porte sur l’ensemble de tous les réels, qui n’est pas dénombrable ; ce n’est pas une limite pratique de stockage.

Le glossaire machine de Turing précise le modèle de calcul qui formalise la production effective des approximations.

La fiche algorithme approfondit la notion de procédure finie employée dans la définition d’un nombre calculable.

Le glossaire Dénombrable explique pourquoi les algorithmes peuvent être listés alors que tous les réels ne le peuvent pas.

La fiche nombre transcendant permet de situer π parmi les nombres non algébriques qui restent calculables.