Nombre calculable - Computable number

π peut être calculé avec une précision arbitraire, alors que presque tous les nombres réels ne sont pas calculables.

En mathématiques , les nombres calculables sont les nombres réels qui peuvent être calculés avec une précision quelconque par un algorithme de terminaison fini . Ils sont également connus sous le nom de nombres récursifs , nombres effectifs ( vanDerHoeven ) ou les réels calculables ou réels récursifs .

Des définitions équivalentes peuvent être données en utilisant les fonctions μ-récursives , les machines de Turing ou le λ-calcul comme représentation formelle des algorithmes. Les nombres calculables forment un véritable champ fermé et peuvent être utilisés à la place des nombres réels à de nombreuses fins mathématiques, mais pas toutes.

Définition informelle utilisant une machine de Turing comme exemple

Dans ce qui suit, Marvin Minsky définit les nombres à calculer d'une manière similaire à celles définies par Alan Turing en 1936 ; c'est-à-dire sous forme de « séquences de chiffres interprétées comme des fractions décimales » entre 0 et 1 :

Un nombre calculable [est] celui pour lequel il existe une machine de Turing qui, étant donné n sur sa bande initiale, se termine par le n ième chiffre de ce nombre [encodé sur sa bande].

Les notions clés de la définition sont (1) qu'un certain n est spécifié au début, (2) pour tout n, le calcul ne prend qu'un nombre fini d'étapes, après quoi la machine produit la sortie souhaitée et se termine.

Une forme alternative de (2) - la machine imprime successivement tous les n chiffres sur sa bande, s'arrêtant après l'impression du n ième - met l'accent sur l'observation de Minsky : (3) qu'en utilisant une machine de Turing, une définition finie - sous la forme de la table de la machine - est utilisé pour définir ce qui est une chaîne potentiellement infinie de chiffres décimaux.

Ce n'est cependant pas la définition moderne qui exige seulement que le résultat soit précis dans une précision donnée. La définition informelle ci-dessus est sujette à un problème d'arrondi appelé le dilemme du fabricant de table alors que la définition moderne ne l'est pas.

Définition formelle

Un nombre réel a est calculable s'il peut être approximé par une fonction calculable de la manière suivante : étant donné tout entier positif n , la fonction produit un entier f ( n ) tel que : ${\displaystyle f:\mathbb {N} \to \mathbb {Z} }$

${\displaystyle {f(n)-1 \sur n}\leq a\leq {f(n)+1 \sur n}.}$

Il existe deux définitions similaires qui sont équivalentes :

• Il existe une fonction calculable qui, étant donné toute erreur rationnelle positive borne , produit un nombre rationnel r tel que${\displaystyle \varepsilon }$ ${\displaystyle |ra|\leq \varepsilon .}$
• Il existe une séquence calculable de nombres rationnels convergeant vers telle que pour chaque i .${\displaystyle q_{i}}$${\style d'affichage a}$${\displaystyle |q_{i}-q_{i+1}|<2^{-i}\,}$

Il existe une autre définition équivalente des nombres calculables via les coupes calculables de Dedekind . Une coupe de Dedekind calculable est une fonction calculable qui, lorsqu'elle est fournie avec un nombre rationnel en entrée, renvoie ou , satisfaisant les conditions suivantes : ${\style d'affichage D\;}$${\style d'affichage r}$${\displaystyle D(r)=\mathrm {vrai} \;}$${\displaystyle D(r)=\mathrm {false} \;}$

${\displaystyle \exists rD(r)=\mathrm {true} \;}$

${\displaystyle \exists rD(r)=\mathrm {false} \;}$

${\displaystyle (D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;}$

${\displaystyle D(r)=\mathrm {vrai} \Rightarrow \exists s>r,D(s)=\mathrm {vrai} .\;}$

Un exemple est donné par un programme D qui définit la racine cubique de 3. En supposant que cela soit défini par : ${\displaystyle q>0\;}$

${\displaystyle p^{3}<3q^{3}\Rightarrow D(p/q)=\mathrm {true} \;}$

${\displaystyle p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false} .\;}$

Un nombre réel est calculable si et seulement s'il existe une coupe de Dedekind calculable D qui lui correspond. La fonction D est unique pour chaque nombre calculable (bien que, bien sûr, deux programmes différents puissent fournir la même fonction).

Un nombre complexe est dit calculable si ses parties réelle et imaginaire sont calculables.

Propriétés

Non dénombrable par calcul

L'attribution d'un nombre de Gödel à chaque définition de la machine de Turing produit un sous-ensemble des nombres naturels correspondant aux nombres calculables et identifie une surjection des nombres calculables. Il n'y a que de nombreuses machines de Turing, ce qui montre que les nombres calculables sont sous- comptables . L'ensemble de ces nombres de Gödel, cependant, n'est pas énumérable par calcul (et par conséquent, les sous-ensembles ne sont pas non plus définis en fonction de celui-ci). C'est parce qu'il n'y a pas d'algorithme pour déterminer quels nombres de Gödel correspondent aux machines de Turing qui produisent des réels calculables. Afin de produire un réel calculable, une machine de Turing doit calculer une fonction totale , mais le problème de décision correspondant est au degré de Turing 0′′ . Par conséquent, il n'y a pas de fonction calculable surjective des nombres naturels aux réels calculables, et l'argument diagonal de Cantor ne peut pas être utilisé de manière constructive pour en démontrer un nombre incalculable. ${\style d'affichage S}$${\style d'affichage S}$${\style d'affichage S}$${\style d'affichage S}$

Alors que l'ensemble des nombres réels est indénombrable , l'ensemble des nombres calculables est classiquement dénombrable et donc presque tous les nombres réels ne sont pas calculables. Ici, pour tout nombre calculable donné, le principe du bon ordre prévoit qu'il existe un élément minimal dans lequel correspond à , et donc il existe un sous-ensemble constitué des éléments minimaux, sur lesquels la carte est une bijection . L'inverse de cette bijection est une injection dans les nombres naturels des nombres calculables, prouvant qu'ils sont dénombrables. Mais, encore une fois, ce sous-ensemble n'est pas calculable, même si les réels calculables sont eux-mêmes ordonnés. ${\style d'affichage x,}$${\style d'affichage S}$${\style d'affichage x}$

Propriétés en tant que champ

Les opérations arithmétiques sur les nombres calculables sont elles-mêmes calculables dans le sens où chaque fois que les nombres réels a et b sont calculables, les nombres réels suivants le sont également : a + b , a - b , ab , et a/b si b est différent de zéro. Ces opérations sont en fait uniformément calculables ; par exemple, il y a une machine de Turing qui sur l'entrée ( A , B , ) produit la sortie r , où A est la description d'une machine de Turing approchant a , B est la description d'une machine de Turing approchant b , et r est une approximation de a + b . ${\style d'affichage \epsilon }$${\style d'affichage \epsilon }$

Le fait que les nombres réels calculables forment un champ a été prouvé pour la première fois par Henry Gordon Rice en 1954 (Rice 1954).

Les réels calculables ne forment cependant pas un champ calculable , car la définition d'un champ calculable nécessite une égalité effective.

Non-calculabilité de la commande

La relation d'ordre sur les nombres calculables n'est pas calculable. Soit A la description d'une machine de Turing approchant le nombre . Alors il n'y a pas de machine de Turing qui sur l'entrée A donne "OUI" si et "NON" si Pour voir pourquoi, supposons que la machine décrite par A continue à sortir 0 comme approximation. On ne sait pas combien de temps attendre avant de décider que la machine ne produira jamais une approximation qui force a à être positif. Ainsi, la machine devra éventuellement deviner que le nombre sera égal à 0, afin de produire une sortie ; la séquence peut ensuite devenir différente de 0. Cette idée peut être utilisée pour montrer que la machine est incorrecte sur certaines séquences si elle calcule une fonction totale. Un problème similaire se produit lorsque les réels calculables sont représentés comme des coupes de Dedekind . Il en est de même pour la relation d'égalité : le test d'égalité n'est pas calculable. ${\style d'affichage a}$${\style d'affichage a>0}$${\displaystyle a\leq 0.}$${\style d'affichage \epsilon }$

Alors que la relation d'ordre complet n'est pas calculable, sa restriction aux paires de nombres inégaux est calculable. Autrement dit, il y a un programme qui prend en entrée deux machines de Turing A et B nombre se rapprochant un et b , où a ≠ b , et les sorties si ou il suffit d'utiliser ε -approximations où donc en prenant de plus en plus petit ε (proche de 0 ), on peut éventuellement décider si ou${\style d'affichage a<b}$${\style d'affichage a>b.}$${\displaystyle \varepsilon <|ba|/2,}$${\style d'affichage a<b}$${\style d'affichage a>b.}$

Autres propriétés

Les nombres réels calculables ne partagent pas toutes les propriétés des nombres réels utilisés dans l'analyse. Par exemple, la plus petite borne supérieure d'une séquence calculable croissante bornée de nombres réels calculables n'a pas besoin d'être un nombre réel calculable (Bridges et Richman, 1987 :58). Une séquence avec cette propriété est connue sous le nom de séquence de Specker , car la première construction est due à E. Specker (1949). Malgré l'existence de contre-exemples tels que ceux-ci, des parties de calcul et d'analyse réelle peuvent être développées dans le domaine des nombres calculables, conduisant à l'étude de l' analyse calculable .

Tout nombre calculable est définissable , mais pas l'inverse. Il existe de nombreux nombres réels définissables et non calculables, notamment :

• tout nombre qui code la solution du problème d'arrêt (ou de tout autre problème indécidable ) selon un schéma de codage choisi.
• La constante de Chaitin , , qui est un type de nombre réel équivalent au problème de l'arrêt de Turing .${\style d'affichage \Oméga }$

Ces deux exemples définissent en fait un ensemble infini de nombres définissables et non calculables, un pour chaque machine de Turing universelle . Un nombre réel est calculable si et seulement si l'ensemble des nombres naturels qu'il représente (lorsqu'il est écrit en binaire et considéré comme une fonction caractéristique) est calculable.

Tout nombre calculable est arithmétique .

L'ensemble des nombres réels calculables (ainsi que chaque sous-ensemble dénombrable et densément ordonné de réels calculables sans extrémités) est d' ordre isomorphe à l'ensemble des nombres rationnels.

Chaînes de chiffres et espaces de Cantor et de Baire

L'article original de Turing définissait les nombres calculables comme suit :

Un nombre réel est calculable si sa séquence de chiffres peut être produite par un algorithme ou une machine de Turing. L'algorithme prend un entier en entrée et produit le -ième chiffre de l'expansion décimale du nombre réel en sortie.${\style d'affichage n\geq 1}$${\style d'affichage n}$

(L'expansion décimale d' un fait uniquement référence aux chiffres après la virgule.)

Turing savait que cette définition est équivalente à la définition approximative donnée ci-dessus. L'argument se déroule comme suit : si un nombre est calculable au sens de Turing, alors il est également calculable au sens : si , alors les n premiers chiffres du développement décimal pour a fournissent une approximation de a . Pour l'inverse, nous choisissons un nombre réel calculable a et générons des approximations de plus en plus précises jusqu'à ce que le n ième chiffre après la virgule soit certain. Cela génère toujours une expansion décimale égale à a mais elle peut se terminer de manière incorrecte par une séquence infinie de 9, auquel cas elle doit avoir une expansion décimale propre finie (et donc calculable). ${\style d'affichage \epsilon }$${\style d'affichage \epsilon }$${\displaystyle n>\log _{10}(1/\epsilon )}$${\style d'affichage \epsilon }$${\style d'affichage \epsilon }$

À moins que certaines propriétés topologiques des nombres réels ne soient pertinentes, il est souvent plus pratique de traiter des éléments de (fonctions à valeur totale 0,1) plutôt que des nombres réels dans . Les membres de peuvent être identifiés avec des développements décimaux binaires, mais puisque les développements décimaux et dénotent le même nombre réel, l'intervalle ne peut être que bijectivement (et homéomorphiquement sous la topologie du sous-ensemble) identifié avec le sous-ensemble de ne pas se terminer par des 1. ${\displaystyle 2^{\omega }}$${\style d'affichage [0,1]}$${\displaystyle 2^{\omega }}$${\displaystyle .d_{1}d_{2}\ldots d_{n}0111\ldots }$${\displaystyle .d_{1}d_{2}\ldots d_{n}10}$${\style d'affichage [0,1]}$${\displaystyle 2^{\omega }}$

Notez que cette propriété des développements décimaux signifie qu'il est impossible d'identifier efficacement les nombres réels calculables définis en termes de développement décimal et ceux définis dans le sens de l' approximation. Hirst a montré qu'il n'y a pas d'algorithme qui prend en entrée la description d'une machine de Turing qui produit des approximations pour le nombre calculable a , et produit en sortie une machine de Turing qui énumère les chiffres de a au sens de la définition de Turing (voir Hirst 2007) . De même, cela signifie que les opérations arithmétiques sur les réels calculables ne sont pas efficaces sur leurs représentations décimales comme lors de l'addition de nombres décimaux, afin de produire un chiffre, il peut être nécessaire de chercher arbitrairement loin à droite pour déterminer s'il y a un report vers le localisation actuelle. Ce manque d'uniformité est l'une des raisons pour lesquelles la définition contemporaine des nombres calculables utilise des approximations plutôt que des développements décimaux. ${\style d'affichage \epsilon }$${\style d'affichage \epsilon }$${\style d'affichage \epsilon }$

Cependant, du point de vue du calcul ou de la théorie de la mesure , les deux structures et sont essentiellement identiques, et les théoriciens de la calculabilité se réfèrent souvent aux membres de comme réels. Alors qu'il est totalement déconnecté , pour les questions sur les classes ou le hasard, il est beaucoup moins compliqué de travailler . ${\displaystyle 2^{\omega }}$${\style d'affichage [0,1]}$${\displaystyle 2^{\omega }}$${\style d'affichage [0,1]}$ ${\displaystyle 2^{\omega }}$${\displaystyle \Pi _{1}^{0}}$${\displaystyle 2^{\omega }}$

Les éléments de sont parfois aussi appelés réels et bien qu'ils contiennent une image homéomorphe de en plus d'être totalement déconnectés, ils ne sont même pas localement compacts. Cela conduit à de véritables différences dans les propriétés de calcul. Par exemple, la satisfaction avec un quantificateur libre doit être calculable tandis que l'unique satisfaisant une formule universelle peut être arbitrairement haut dans la hiérarchie hyperarithmétique . ${\displaystyle \omega ^{\omega }}$${\displaystyle \mathbb {R} }$ ${\displaystyle \omega ^{\omega }}$${\displaystyle x\in \mathbb {R} }$${\displaystyle \forall (n\in \omega )\phi (x,n)}$${\style d'affichage \phi (x,n)}$${\displaystyle x\in \omega ^{\omega }}$

Utiliser à la place des réels

Les numéros calculables comprennent les nombres réels spécifiques qui apparaissent dans la pratique, y compris tous les vrais nombres algébriques , ainsi que e , π , et bien d' autres numéros de transcendantal . Bien que les réels calculables épuisent ces réels que nous pouvons calculer ou approximer, l'hypothèse selon laquelle tous les réels sont calculables conduit à des conclusions sensiblement différentes sur les nombres réels. La question se pose naturellement de savoir s'il est possible de disposer de l'ensemble complet des réels et d'utiliser des nombres calculables pour toutes les mathématiques. Cette idée est séduisante d'un point de vue constructiviste et a été poursuivie par ce que Bishop et Richman appellent l' école russe des mathématiques constructives.

Pour développer réellement une analyse sur des nombres calculables, certaines précautions doivent être prises. Par exemple, si l'on utilise la définition classique d'une séquence, l'ensemble des nombres calculables n'est pas fermé sous l'opération de base consistant à prendre le supremum d'une séquence bornée (par exemple, considérons une séquence de Specker , voir la section ci-dessus). Cette difficulté est résolue en ne considérant que les séquences qui ont un module de convergence calculable . La théorie mathématique qui en résulte est appelée analyse calculable .

Mise en œuvre

Il existe des progiciels informatiques qui fonctionnent avec des nombres réels calculables, représentant les nombres réels sous forme de programmes calculant des approximations. Un exemple est le package RealLib Lambov (2015) .

Voir également

• Nombre définissable
• Fonction semi-calculable
• Problème transinformatique

Les références