Valeur du nombre omega de Chaitin

jreeman · 04/01/2007 - 10h17

Bonjour et bonne année à tous

,

si je comprends bien ce nombre est incalculable voudrait dire qu'il serait vain de chercher à trouver une valeur ou d'approximation pour ce nombre, c'est bien cela ?

Jamais on pourra trouver disons ne serait-ce que la 1ere décimale de ce nombre ?

martini_bird · 04/01/2007 - 13h11

Salut,

à en croire la définition de wikipedia, un nombre est calculable lorsqu'il existe un algorithme permettant d'en trouver toutes les décimales. A priori, il n'est donc pas interdit de calculer les premières décimales de $\Omega$ . Ce qui en revanche est impossible, c'est de les trouver toutes.

Cordialement.

jreeman · 04/01/2007 - 13h19

Envoyé par martini_bird

Salut,

à en croire la définition de wikipedia, un nombre est calculable lorsqu'il existe un algorithme permettant d'en trouver toutes les décimales. A priori, il n'est donc pas interdit de calculer les premières décimales de $\Omega$ . Ce qui en revanche est impossible, c'est de les trouver toutes.

Cordialement.

Merci, effectivement, donc pour ce nombre au mieux on peut dire qu'il existe une décimale dont on ne peut pas connaitre la valeur par un algorithme.

J'ai fait des recherches dans google et il semble qu'on en sache pas bcp plus sur les décimales de ce nombre.

jreeman · 04/01/2007 - 16h38

En fait, j'ai compris qu'il n'y a pas un nombre "universel" Omega de Chaitin, il y en a plusieurs, suivant la base que l'on considère.

"Ici" un article donnant les premières décimales en base 2 et 16.

jreeman · 06/01/2007 - 19h41

Bonjour,

ce nombre est incalculable, mais je me demande encore si ca empeche clairement qu'on puisse tomber dessus grâce à un algorithme, mais sans pouvoir le prouver.

jreeman · 07/01/2007 - 02h04

Bon, je me réponds moi-même, en faisant un raisonnement par l'absurde, aucun nombre calculable ne peut être le nombre omega.

Mais en logique intuitioniste, on ne s'autorise pas les raisonnements par l'absurde, donc dans cette logique, on ne peut pas rejetter l'hypothèse que iomega soit calculable.

D'ou finalement : logique classique/intuitioniste, que choisir ?

spi100 · 08/01/2007 - 10h53

Envoyé par martini_bird

Salut,

à en croire la définition de wikipedia, un nombre est calculable lorsqu'il existe un algorithme permettant d'en trouver toutes les décimales. A priori, il n'est donc pas interdit de calculer les premières décimales de $\Omega$ . Ce qui en revanche est impossible, c'est de les trouver toutes.

Cordialement.

Dans le cas de $\Omega$ , c'est presque ça mais pas tout à fait. Il est impossible de borner l'erreur par une fonction calculable.
J'ai fait une ébauche de démo là http://forums.futura-sciences.com/post913398-224.html (c'est tiré d'un bouquin de Delahaye), l'exposé que j'en fait n'est pas très rigoureux mais l'idée est là. J'aimerais bien avoir votre avis, ça me permettra de savoir si j'ai compris ou pas.

jreeman · 08/01/2007 - 11h28

Envoyé par spi100

Le nombre de Chaitin étant par définition la probabilité qu'un programme s'arrête, la suite $\Omega_m$ converge vers $\Omega$ .

Je crois qu'il y a une incohérence ici : $\Omega$ vaudrait donc 0 ? de toute facon $\Omega$ est plutôt la probabilité sur tous les programmes possibles de tomber sur un programme qui s'arrete au bout d'un temps fini.

PS : de quel livre il s'agit ?

**Médiat** · 08/01/2007 - 11h49

Envoyé par spi100

Dans le cas de $\Omega$ , c'est presque ça mais pas tout à fait. Il est impossible de borner l'erreur par une fonction calculable.

Je pense avoir raté quelque chose, car il me semblait que ce $\Omega$ était une probabilité, ce qui doit pouvoir me permettre d'affirmer que
$\Omega = 0,5$ avec une erreur d'au plus 0,5 ?