Discussion:Nombre réel calculable

"Tout nombre réel est la limite d'une suite de nombres rationnels ; ainsi s'il est possible d'expliciter un terme général pour une telle suite, le nombre qui en est la limite est calculable" est incorrect à mon avis.— Le message qui précède, non signé, a été déposé par Wikipedist (discuter)

Oui, cette phrase dans son ensemble me parait suspecte aussi. Tout nombre réel est certes la limite d'une suite de nombres rationnel, mais pas forcément d'une suite calculable de rationnels. Le 'ainsi' est donc a priori un peu rapide.

Je pense, étant donné le titre du paragraphe que la phrase devrait être "Tout nombre réel calculable est la limite d'une suite calculable de nombres rationnels ; ainsi..." mais cela devient un peu tautologique.

Globalement, on ne voit pas bien où veut en venir le paragraphe et quelles conclusions en tirer : tous les nombres calculables sont définissables comme la limite d'une suite calculable de rationnels ? Toute limite d'une suite calculable de rationnels est un nombre réel calculable ? Est-ce qu'il y a d'autres moyens de construire un réel calculable ? Autant de questions sur lesquelles ce paragraphe n'est pas clair. --Jean-Christophe BENOIST (d) 18 décembre 2009 à 17:54 (CET)

En fait c'est franchement faut: un réel calculable est certes toujours la limite d'une suite calculable, par contre la limite d'une suite calculable n'est PAS nécessairement un réel calculable: par exemple les suites de Specker --Wikipedist (d)

Ou le nombre Oméga qui est la limite d'une suite calculable, mais qui n'est pas calculable.. --Jean-Christophe BENOIST (d) 12 mars 2010 à 13:38 (CET)

Il y a bien plus grave : depuis quand est-ce un corps? Comment calculer les décimales de l'inverse du réel de Brouwer (celui obtenu en prenant pour kème décimale un 1 si la kème tranche d'un million de décimales de pi est formée uniquement de 7, et 0 sinon ; lequel est (presque sûrement) non nul...)?--Dfeldmann (d) 21 avril 2011 à 21:17 (CEST)

Oubliez ça, c'est la fatigue... (mais c'est amusant de chercher l'erreur (tout de même assez grossière) de mon "raisonnement")--Dfeldmann (d) 21 avril 2011 à 21:27 (CEST)

Ensemble calculable de réels

Bonjour,

• j'ai une source sur la formalisation de la notion de suite calculable de réels, cf. Discussion:Algèbre des périodes mais je ne sais pas encore trop comment l'exploiter. Ce serait à la fois pour remplacer ici "la réponse de Turing est que l'on ignore..." par "ce paradoxe apparent démontre simplement qu'aucune énumération (avec répétitions éventuelles) des réels calculables n'est calculable" et pour, dans l'article sur l'algèbre des périodes, justifier un petit T.I. traduit de :en.
• en attendant, je pense qu'il faudrait au moins corriger "... que l'on ignore comment attribuer un numéro à chaque nombre calculable" en quelque chose comme "...que l'on sait énumérer (avec répétitions éventuelles) les nombres calculables, mais pas de façon « effective »"

Anne (d) 29 juillet 2012 à 17:48 (CEST)

Le premier paragraphe de en:Computable_number#Properties donne des indications à ce sujet, mais qui manque de sources et qui n'est pas super clair. Je vais essayer d'en trouver. Je pars bientôt en vacances, ce pourra être un de mes "devoirs de vacances".. --Jean-Christophe BENOIST (d) 29 juillet 2012 à 18:20 (CEST)

En effet, ce qu'ils racontent ne prouve rien du tout à part le fait qu'ils s'y prennent très mal. Partir des machines de Turing ne mène à rien. Cf. plutôt Yoshinaga, Periods and elementary real numbers « 0805.0349 », texte en accès libre, sur arXiv. : je suppose que (et je cherche où) l'analogue pour les nombres calculables a déjà été fait (i.e. : à partir d'une énumération calculable arbitraire d'un ensemble A de réels calculables, construire par le procédé diagonal un réel calculable n'appartenant pas à A, ce qui prouve que A ne peut pas être l'ensemble de tous les calculables). Anne (d) 29 juillet 2012 à 19:43 (CEST)

Ce qui prouverait que l'ensemble des calculables n'est pas, sortons un gros mot, définissable, p.-e ? Au pif je verrais bien un résultat du genre "le problème de savoir si un réel donné est calculable ou non n'est pas décidable" ... sauf que je crains qu'on n'ai pas dans la littérature un tel théorème justement parce que le mode de donation (qui suppose une définition ou une construction) d'un réel quelconque risque de ne pas dépasser le dénombrable. Mais je dis p.-e. n'importe quoi. --Epsilon0 ε₀ 29 juillet 2012 à 20:01 (CEST)

Ce que je cherche est plus modeste donc plus sûrement réalisable : quelque chose du genre « l'ensemble des réels calculables n'est pas récursivement énumérable » Mais j'ai lu récemment en page de garde d'une thèse : « Si tu as atteint ton but, c'est que tu n'as pas fixé la barre assez haut. » Anne (d) 29 juillet 2012 à 20:32 (CEST)

Bon, j'ai trouvé une source sur la preuve originale de Turing, démontrant la non-calculabilité de l'élément diagonal (ce qui exclut de trouver un nombre calculable par diagonalisation). C'est le Copland "Annotated Turing", qui commente le texte original de Turing. En fait, ce n'est PAS ce qui dit le texte dans cet article, et cela ne ressemble pas non plus à WP:en (mais il existe peut-être une démonstration plus moderne qui y ressemble plus). En gros et en bref, Turing exhibe une machine qui calcule la diagonale en émulant tour à tour (c'est une machine universelle) les machines donnant des nombres calculables. Le problème, comme toujours quand on fait appel au procédé diagonal, c'est qu'elle en vient forcément à s'émuler elle-même et recommence tout au début, cela à l'infini. Donc le procédé diagonal n'est pas un procédé calculable. J'essaierais de mettre ceci noir sur blanc à mon retour. --Jean-Christophe BENOIST (d) 31 juillet 2012 à 14:42 (CEST)

En fait si, il y a un rapport entre le texte actuel et la démo de Turing. Si on va jusqu'au bout du chapitre 8 de Turing, il déduit de l'échec du procédé diagonal ce qui est précisément non calculable dans tout le processus. Pour énumérer toutes les machines donnant les nombres calculable, le processus énumère les numéros de 1 à l'infini et détermine si le numéro est "satisfaisant" ou non. Un nombre est "satisfaisant" s'il correspond au code valide d'une machine de Turing, et si cette machine s'arrête. C'est évidemment ce test de "satisfabilité" qui n'est pas calculable. "on ignore comment attribuer un numéro à chaque nombre calculable" signifie je pense "on ignore comment identifier les numéros satisfaisants". --Jean-Christophe BENOIST (d) 31 juillet 2012 à 15:38 (CEST)

Pour Turing, un nombre réel calculable est décrit par une machine de Turing qui ne s'arrête pas, « les machine gentilles » dans sa terminologie française, les machines qui s'arrêtent étant « méchantes » Bulletin de SPECIF n◦63 (avril 2010). L'indécidabilité de l'arrêt nous dit que l'ensemble des machines qui s'arrêtent n'est pas décidable, il est semi-décidable (récursivement énumérable suivant la terminologie que l'on adopte). Son complémentaire, l'ensemble des machines qui ne s'arrêtent pas, n'est pas semi-décidable (pas récursivement énumérable). On devrait à partir de là pouvoir dire que l'ensemble des nombres réels calculables n'est pas semi-décidable. --Pierre de Lyon (d) 2 août 2012 à 12:25 (CEST)

De retour ! Pas eu le temps de beaucoup lire, mais suffisamment pour m’apercevoir que j'avais mal interprété le terme "circle-free" dans la source (et dans l'original de Turing). Turing nomme (paradoxalement) "circle-free" les machines qui ne s'arrêtent pas et qui impriment un nombre infini de chiffres (et effectivement Copland qualifie ce terme de "poor choice", car on traduit instinctivement "circle-free" par "qui ne boucle pas" et donc qui s'arrête). En fait, les machines "circle-free" semblent être les "machines gentilles" dans cette très intéressante source primaire, ou les machines "satisfaisantes". Mais cela ne change pas fondamentalement la démonstration de la non-calculabilité de la diagonale.

Plusieurs points à noter : 1) Les nombres finis, entiers notamment, sont "non calculables" au sens originel de Turing, puisqu'ils ne peuvent être générés par une machine "circle-free". Copland dit que des définitions "plus modernes" incluent ces nombres. 2) Toutes les machines qui ne s'arrêtent pas ne sont pas forcément "gentilles", ou "circle-free", une machine qui ne s'arrête jamais mais imprime un nombre fini de chiffres n'est pas "circle-free".

Bref, partir de la source de 1936, même à travers une source secondaire, n'est pas évident. Mais j'ai un peu de mal à trouver une source plus récente sur les nombres calculables (par le biais de l'informatique théorique). Sur la calculabilité en général, il y a des tonnes de sources bien sûr, mais sur celle des nombres en particulier, avec ses subtilités de "circle-free" etc.., pas vraiment. Mais la recherche continue. Cordialement --Jean-Christophe BENOIST (d) 8 août 2012 à 15:34 (CEST)

Le nombre 2 est aussi le nombre 2,00000...000... c'est-à-dire 2, suivi d'une infinité de zéros après la virgule. C'est donc un nombre calculable au sens de Turing. Est-ce que je me trompe?--Pierre de Lyon (d) 11 août 2012 à 19:54 (CEST)

Ce n'est pas ce que semble dire Copeland. « Notice that although the finite sequence 010 for example is the sequence computed by some machine, this sequence is not a computable sequence, according to Turing's definition » (italiques de l'auteur). Mais ta remarque est judicieuse, et ce cas n'est pas évoqué ni explicitement ni implicitement dans cette source (un cas encore plus intéressant serait 1.999999.., qui est égal à 2, au lieu de 2). L'autre phrase est « Modern writers usually define 'computable' in such a way that every finite sequence is a computable sequence ». Malheureusement, Copeland ne dit pas quels sont ces "modern writers" et quels sont ces "ways".. --Jean-Christophe BENOIST (d) 11 août 2012 à 21:41 (CEST)

Je commence à réaliser la complexité de ce sujet. En fait, l'approche de Turing semble datée et ne plus faire l'objet de développement direct. Les sources actuelles sont beaucoup plus mathématiques qu'informatiques, et abordent ce sujet par le biais de différents domaines des mathématiques constructives. Deux sources intéressantes  : A Simple Introduction to Computable Analysis et Real Number Computability and Domain Theory, dont la première partie est une source secondaire intéressante sur le sujet (la seconde partie est une source primaire). L'approche de Turing ne devrait être citée qu'à titre historique dans cet article.

Un des points complexes est justement sur l'utilisation de la diagonalisation pour créer des nombres calculables. Par l'approche de Turing, cela n'est pas possible, et c'était ce que j'expliquais plus haut. Par l'approche moderne, cela semble possible (voir "A Simple Introduction..", théorème 3.4). Cela mène à notre interrogation sur l'aspect "récursivement énumérable" de l'ensemble des nombres calculables. Les nombres calculables ne sont pas RE de manière effective, car il est toujours possible de créer un nombre calculable par diagonalisation d'une liste RE quelconque. Donc aucune liste RE ne donne tous les nombres calculables (mais ceux-ci restent toujours dénombrables). Si j'ai bien compris "A Simple Introduction.." aux alentours du théorème 3.4. Cordialement --Jean-Christophe BENOIST (d) 10 août 2012 à 00:03 (CEST)

Je me permets de citer deux références liées à l'informatique théorique. Je ne sais pas si c'est ce que tu cherches.

• Y. Bertot. Affine functions and series with co-inductive real numbers. Mathematical Structures in Computer Science, 17(1):37–63, 2007.
• N. Julien. Certified exact real arithmetic using co-induction in arbitrary integer base. In Jacques Garrigue and Manuel V. Hermenegildo, editors, FLOPS, volume 4989 of Lecture Notes in Computer Science, pages 48–63. Springer, 2008.

--Pierre de Lyon (d) 11 août 2012 à 19:54 (CEST)

Il reste à mettre la main dessus ;) Merci en tout cas. Pour faire le bilan de tout ce que j'ai lu, j'ai encore deux points d'incompréhension.

1) Je ne saisis pas clairement les relations entre la définition de Turing et les définitions "modernes" (à base typiquement de suite de Cauchy et de critère de convergence), et notamment sur la diagonalisation qui semble en effet impossible avec Turing (Copeland est clair là dessus) et possible avec les définitions modernes (théorème 3.4 de Di Gianantonio).

2) J'ai une grosse incompréhension sur la notation décimale, qui semble acceptée sans sourciller par Rice et Pour-El (références dans l'article), et évitée dans les sources plus modernes. Surtout Rice et Pour-El affirment qu'elle est équivalente aux suites de Cauchy, alors que Di Gianantonio et Weihrauch affirment qu'elles ne le sont pas (sauf si on accepte des "digits" négatifs), et l'évitent. Soit Rice et Pour-El n'ont pas vu le problème (ce qui serait surprenant), soit il y a un détail qui m'échappe. --Jean-Christophe BENOIST (d) 11 août 2012 à 21:41 (CEST)

Pour moi, la notation décimale brutale n'est pas une bonne représentation des réels, car elle n'est pas bijective. En effet, 0,9999... et 1,0000... représentent le même nombre. Mais il y a des moyens de désambiguer cela. --Pierre de Lyon (d) 12 août 2012 à 11:41 (CEST)

Le problème n'est pas tant la non-bijectivité en elle-même que la non-calculabilité de la multiplication. Les digits négatifs résolvent le problème de la non calculabilité, mais la notation reste non bijective (et encore beaucoup plus non-bijective d'ailleurs) (voir Di Gianantonio). Plus concrètement, je reste peu satisfait par la phrase de l'article « Un réel est calculable si la suite de ses décimales est calculable » qui est incontestablement sourcée, mais soit Rice est trop ancien et a négligé un problème, soit il y a quelque-chose que je n'ai pas compris. La clé du mystère est peut-être dans cet extrait de Di Gianantonio :

« Different representations already occur in classical analysis: Cauchy sequences of rational numbers, Cauchy sequences of decimal rationals, Dedekind cuts in the field of rationals, infinite decimal expansions, and so on. Classically all these representations are equivalent and we can study Analysis without worrying about which representation for real numbers we are currently using. Also in computable Analysis many of these representations turn out to be equivalent. But there are also some exceptions: for instance Dedekind cuts and Cauchy sequences turn out not to be equivalent. » (les italiques sont de moi).

Il dit qu'en analyse classique tout est équivalent, y compris la notation décimale (comme Rice et Pour-El le disent, mais pourtant ils ne travaillent pas en analyse classique, a priori). En revanche en analyse calculatoire les coupures de Dedekind ne sont pas équivalentes aux suites de Cauchy, et sans doute aussi l'expansion décimale. Les deux peuvent avoir raison, mais dans des domaines différents. Mais je pense que on devrait éviter de parler de la notation décimale dans l'article, au moins pour attirer l'attention du lecteur sur la notion de représentation des réels qui est capitale pour leur calculabilité, et car son statut est complexe et pas clair. --Jean-Christophe BENOIST (d) 12 août 2012 à 12:39 (CEST)

Anne, merci pour cette nouvelle source, mais je reste sur l'incompréhension 2) que j'ai énoncé ci-dessus. Mostowski vient plussoyer Rice et Pour-El, mais c'est une source à peu près de la même époque. Pourquoi Motowski, Rice et Pour-El disent que la notation décimale est équivalente aux suites de Cauchy, et pourquoi Di Gianantonio et Weihrauch (lemme 3.2) disent que non et mettent en garde contre la notation décimale ? Pourquoi tentes-tu d'affermir cette affirmation alors que je dis plus haut qu'il faudrait éviter de la citer, sans répondre du tout à mon texte ? --Jean-Christophe BENOIST (d) 12 août 2012 à 16:44 (CEST)

Pas nouvelle (déjà utilisée en dernière section), mais plus explicite sur cette équivalence

Pas "tenter", mais vraiment affermir : parce que je serais désolée de la voir disparaître si, malgré ce que tu dis, elle est vraie

Je ne répondrai à vos textes qu'à mon retour de vacances fin août, car là je suis trop mal installée pour les lire avec l'attention qu'ils méritent, réfléchir, naviguer, et je ne fais que du "travail bête". Anne (d) 12 août 2012 à 17:13 (CEST)

Pas de problème Anne, cela peut attendre. Je pense que cette phrase est vraie, mais dans un domaine et avec une signification bien précise, qu'il faudrait expliciter dans l'article. Si nous ne sommes pas en mesure de comprendre 2), il faudra peut-être la faire disparaitre mais en unissant nos efforts, nous y arriverons sans doute. Cordialement --Jean-Christophe BENOIST (d) 12 août 2012 à 17:55 (CEST)

Bon. Plus je trouve des sources, plus je me sens finalement à l'aise avec cette définition (celle des digits calculables). Des sources récentes (notamment Algorithmic Randomness and Complexity (chapitre 8) et Real number from computable to random vont sans problème dans cette direction, sans faire allusion au problème relevé par Di Gianantonio et Weihrauch (je n'aurais pas dû commencer par ces sources !). Je pense en fait que la notation décimale (ou en base b) est suffisante pour définir la calculabilité d'un réel, mais pas suffisante pour faire des calculs avec, ce qui n'est pas forcément contradictoire. --Jean-Christophe BENOIST (d) 15 août 2012 à 16:19 (CEST)

Tant mieux ! Pas encore bien approfondi toutes les sources (faudrait rajouter dans l'article, parmi les nouvelles sources qui ont fleuri ici, celles qui sont utiles et consultables) mais il me semble déjà que, plutôt que l'équivalence avérée entre les définitions (sans nécessité de digits négatifs, et sans se prendre la tête avec les réels admettant deux développements puisque tout rationnel est calculable quelle que soit la définition choisie), c'est plutôt ce dernier bémol qu'il faudrait modérer : « n'est pas la représentation préférée » : par qui ? citation ? « multiplication par 3 pas calculable » : en quel sens ? (pour épargner au lecteur de cliquer sur le lien externe) et en quoi cela justifierait une « non-préférence de la représentation décimale pour l'étude de la calculabilité des réels » ? Je crois que c'est plutôt dans la dernière section qu'il faut (continuer d')effleurer les finesses sur la calculabilité d'autre chose qu'un nombre. « les notations redondantes où l'on admet qu'un nombre a plusieurs notations » : pas clair, car la représentation décimale en fait partie. Anne (d) 31 août 2012 à 13:38 (CEST)

Suggestion : remplacer l'intégralité du « dernier bémol » que j'incrimine ci-dessus par une toute petite phrase qui renverrait (un peu) à Di Gianantonio 1996, p. 5 et (surtout) à Nombre réel calculable#Suite calculable de réels, qui me semble plus clair et suffisant comme justification d'une préférence ultérieure une fois l'équivalence établie. Anne (d) 31 août 2012 à 14:36 (CEST)

Finitude

In vivo, tout calculateur effectif se soucie de la finitude du procédé de calcul, donc des représentations qu'il manipule. De ce fait, $\pi$ me semble plutôt semi-calculable que calculable : on sait énumérer ses décimales, mais le processus est, comme on dit "un peu long, surtout vers la fin". Pas de calculabilité sans finitude du procédé et des représentations(ou, plus généralement, des ressources nécessaires). Sinon, on devrait parler de semi-calculabilité ou de proto-calculabilité ou toute autre forme faible (nécessaire non suffisante). --Lf69100 (discuter) 17 octobre 2015 à 10:55 (CEST)

Non. La définition de la calculabilité est que on sait prédire combien de décimales on va calculer dans un temps fini, ou - ce qui revient au même - combien de temps fini on va prendre pour calculer un nombre de décimales voulu. Un tel nombre (dont pi fait partie) est pleinement calculable. Ce n'est pas le cas du nombre Oméga, dont on peut en théorie calculer autant de décimales que on veut, mais dans un temps indéterminé, qui n'est donc pas calculable. Le terme pour ce genre de nombre n'est pas "semi-calculable", mais approchable. --Jean-Christophe BENOIST (discuter) 17 octobre 2015 à 11:25 (CEST)

En 1936, un chercheur s'est intéressé à ce type de nombres comme $\pi$ et a a écrit un article intitulé On Computable Numbers with an Application to the Entscheidungsproblem qui a eu un certain écho. Il a appelé « calculables » ces nombres, je pense que nous devrions conserver sa terminologie! . --Pierre de Lyon (discuter) 17 octobre 2015 à 17:35 (CEST)