La constante de Chaitin est un exemple (en fait une famille d'exemples) d'un nombre non calculable. Il représente la probabilité qu'un programme généré aléatoirement (dans un certain modèle) s'arrête. Il peut être calculé approximativement, mais il n'existe (probablement) aucun algorithme pour le calculer avec une précision arbitraire.
Qu'est-ce qui rend un nombre calculable ?
Un nombre calculable est un nombre qui peut être calculé par un programme informatique fini. Tous les nombres dont vous avez entendu parler comme 3, √2, π, e, etc. sont calculables. Certains nombres (comme π) sont représentés par une chaîne infinie de chiffres non répétitifs.
Que signifie non calculable ?
Un non calculable est un problème pour lequel il n'existe aucun algorithme permettant de le résoudre. L'exemple le plus célèbre de non-calculabilité (ou d'indécidabilité) est le problème de l'arrêt.
Les nombres non calculables existent-ils ?
Non seulement les nombres non calculables existent, mais en fait ils sont beaucoup plus abondants que les nombres calculables. Beaucoup, beaucoup de nombres réels sont simplement des séquences infinies de chiffres apparemment aléatoires, sans modèle ni propriété spéciale. … Comme exemple, considérons un nombre dont la partie avant la virgule décimale est 0.
Les nombres réels sont-ils calculables ?
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 vu comme une fonction caractéristique) est calculable. Chaque calculateurle nombre est arithmétique.
