La constante de Chaitin est normale?

Selon cette source, la constante de Chaitin $\Omega$ Est normal.

Chaque probabilité d'arrêt est un nombre réel normal et transcendantal qui n'est pas calculable, ce qui signifie qu'il n'y a pas d'algorithme pour calculer ses chiffres. En effet, chaque probabilité d'arrêt est aléatoire de Martin-Löf, ce qui signifie qu'il n'y a même pas d'algorithme qui puisse deviner de manière fiable ses chiffres.

Source (Wikipedia)

En outre, la définition de la normale est que chaque chiffre se produit avec une probabilité égale $1/b$ . Et que chaque duo de chiffres se produit avec $1/b^2$ probabilité et tous les triplets se produisent avec probabilité $1/b^3$ etc.

L'oméga de Chaitin est calculé via

$\Omega = \sum_{p \in halts} 2^{-|p|}$

L'écriture $\Omega$ en binaire, on obtient une liste de 0 et 1. Par exemple,

2^-1=0.1 +
2^-2=0.01 +
2^-3=0.001 +
~skip 2^-4 as it does not halt
2^-5=0.00001 +
...
=\Omega
=0.11101...

On voit bien que la position de chaque bit correspond à l'état d'arrêt du programme de longueur correspondant au bit.

Voici ce avec quoi je me bats

Si $\Omega$ est en effet normal, cela signifie que exactement 50% des programmes s'arrêtent et exactement 50% ne s'arrêtent pas. Cela semble très contre-intuitif.

Par exemple, supposons que je génère des programmes Java en concaténant au hasard des caractères uniques. La majorité d'entre eux, je suppose que plus de 99,99% ne compileraient même pas. Cela n'impliquerait-il pas qu'au moins 99,99% d'entre eux ne s'arrêteront pas? Comment pouvons-nous justifier que exactement la moitié s'arrêtera et exactement la moitié ne le sera pas, en vertu de $\Omega$ être normal.

Ou Wikipédia est-il incorrect $\Omega$ être normal?

halting-problem Alexandre H. Tremblay
la source

Bienvenue sur le site! Si vous mettez votre LaTeX entre des dollars au lieu de backticks, nous pourrons lire la sortie, plutôt que la source.

David Richerby

Et pour les fractions \ frac {1} {b ^ 2} donne

\frac{1}{b^{2}}

$\frac{1}{b^2}$ au lieu de

1 / b^{2}

$1/b^2$ .

Evil

Je crois que l'Omega de Chaitin est défini pour les encodages Turing Machine sans préfixe , pas pour les encodages arbitraires. Si c'est le cas, je pense que nos intuitions normales sur ce qui constitue une MT "aléatoire" pourraient ne pas être aussi fiables.

mhum

@mhum Vous pouvez ré-encoder n'importe quel programme en un encodage sans préfixe en ajoutant un 1 entre chaque bit du programme d'origine, puis en le terminant par un 0. Ensuite, la machine Turing lit tous les deux bits jusqu'à ce qu'elle trouve le 0 de fin. Cela laisse le code java intact mais le rend libre de préfixe. Le problème demeure donc.

Alexandre H. Tremblay

"Si Ω est en effet normal, cela signifie qu'exactement 50% des programmes s'arrêtent et exactement 50% ne le font pas. Cela semble très contre-intuitif." Cela signifie que, asymptotiquement, la moitié des programmes s'arrête. Ce n'est pas si contre-intuitif. Même si cela peut prendre un certain effort pour trouver un programme d'arrêt (c'est-à-dire que vous avez frappé une longue chaîne de 0 en Ω), une fois que vous en avez trouvé un, vous allez avoir une très longue chaîne de programmes d'arrêt qui le suit (c'est-à-dire un chaîne également longue de 1), par exemple des programmes qui sont fonctionnellement le même programme mais avec un tas de commentaires superflus (une sorte de lemme de pompage).

Marcel Besixdouze

Réponses:

Contrairement à votre exemple, la constante de Chaitin n'est pas définie comme suit:

Ω = \sum_{n : n th program halts} 2^{- n} .

$\Omega = \sum_{n\colon \text{$n$th program halts}} 2^{-n}.$

Au lieu de cela, il y a un ensemble $\Pi \subseteq \{0,1\}^*$ des programmes autorisés sans préfixe (aucune chaîne n'est le préfixe d'une autre chaîne). Chacun des programmes $\Pi$ est légal (cela nie votre exemple Java). Si les programmes sont encodés en unaire, il est en effet vrai que le $n$ e programme a une longueur $n$ , puis votre définition de $\Omega$ travaux. Mais pour les autres encodages, la définition de $\Omega$ est

Ω = \sum_{p \in Π : p halts} 2^{- | p |},

$\Omega = \sum_{ p \in \Pi\colon p \text{ halts} } 2^{-|p|},$ où

| p |

$|p|$ est la longueur de la chaîne binaire

p

$p$ . L'inégalité de Kraft montre que

\sum_{p \in Π} 2^{- | p |} \leq 1

$\sum_{p \in \Pi} 2^{-|p|} \leq 1$ .

La constante de Chaitin est algorithmiquement aléatoire : la (préfixe) complexité de Kolmogorov du premier $n$ bits est $n - O(1)$ . Pour le montrer, notez d'abord que $\Omega_n$ , la première $n$ un peu de $\Omega$ , suffit pour déterminer si un programme de longueur $n$ (sous l'encodage $\Pi$ ) s'arrête ou non. En effet, en fraction, $\Omega_n \leq \Omega < \Omega_n + 2^{-n}$ . Exécutez tous les programmes en parallèle et chaque fois $p$ s'arrête, ajouter $2^{-|p|}$ à un comptoir $C$ (initialisé à zéro). Finalement $C \geq \Omega_n$ (depuis $C \to \Omega$ par le bas). À ce stade, si le programme d'entrée de longueur $n$ ne s'est pas arrêté, alors vous savez qu'il ne s'arrête pas, car sinon $\Omega \geq C + 2^{-n} \geq \Omega_n + 2^{-n}$ .

Compte tenu de cela, supposons que pour certains $K>0$ et infiniment $n$ , vous pourriez calculer $\Omega_n$ en utilisant $n - K$ morceaux. Pour chacun $n$ , vous pouvez trouver une chaîne dont la complexité de Kolmogorov est supérieure à $n$ , en considérant la sortie de tous les programmes de durée $n$ . Pour assez grand $K$ , le résultat est un programme de longueur au plus $n$ pour calculer la chaîne dont la complexité de Kolmogorov est supérieure à $n$ . Cette contradiction prouve que pour certains $K$ , la complexité de Kolmogorov $\Omega_n$ Est au moins $n-K$ .

Aléatoire algorithmique de $\Omega$ implique, en particulier, que la fréquence de 0 et de 1 dans son expansion binaire tend vers 1/2. En effet, supposons que pour certains (rationnels) $\epsilon > 0$ il existe une infinité de $n$ de telle sorte que la fraction de 1 s $\Omega_n$ est tout au plus $1/2-\epsilon$ . Puisqu'il n'y a que $2^{h(1/2-\epsilon)n}$ cordes avec au plus $1/2-\epsilon$ plusieurs 1, nous pouvons compresser $\Omega_n$ sur mesure $h(1/2-\epsilon)n + 2\log n + C_\epsilon$ (la constante $C_\epsilon$ dépend de $\epsilon$ puisque le programme a besoin de savoir $\epsilon$ ). Cependant, c'est $n - \omega(1)$ , contredisant le caractère aléatoire algorithmique de $\Omega$ .

Yuval Filmus
la source

Merci pour la réponse très complète. Je me bats avec le tout premier paragraphe et je m'excuse de ne pas avoir traversé mon crâne. Si nous ne prenons que les programmes java qui se compilent, puis les codons en unaire, cela signifie-t-il alors que exactement la moitié d'entre eux s'arrêtera?

Alexandre H. Tremblay

@ AlexandreH.Tremblay Oui, c'est l'implication. Pour en savoir plus, je recommande un manuel sur la complexité de Kolmogorov, comme Li et Vitanyi.

Yuval Filmus

Pourriez-vous rendre la machine Turing telle qu'elle inclut un compilateur java? Imaginez ceci. Tout d'abord, répertoriez toutes les chaînes de caractères générées de manière aléatoire, du plus court au plus long. Deuxièmement, encodez ces chaînes en unaire. Troisièmement, introduisez les cordes unaires dans la machine de Turing en entrée. La machine Turing vérifie si l'entrée se compile en Java. Si c'est le cas, il l'exécute et la moitié s'arrêtera et la moitié ne le fera pas. S'il ne compile pas, alors il boucle pour toujours (while (true) {};). Cela ne fausserait-il pas le rapport arrêt / non-arrêt? J'ai lu Li et Vitanyi la semaine dernière, mais je devrai le relire;).

Alexandre H. Tremblay

Je soupçonne qu'un codage unaire de la manière que vous suggérez ne serait pas admissible . Par exemple, dans le codage unaire (même le plus simple), vous ne pourrez pas composer de programmes avec une surcharge constante. Je vérifierais Li et Vitanyi pour une liste de propriétés qu'un ordinateur universel admissible doit satisfaire. Cela ferait partie de la définition de la complexité de Kolmogorov.

Yuval Filmus

Bonjour, pouvez-vous recommander la section de Li et Vitanyi où ces informations sont présentes. J'ai lu le livre une deuxième fois et je ne l'ai pas trouvé.

Alexandre H. Tremblay

Votre erreur est sur la ligne suivante:

Si $\Omega$ est en effet normal, cela signifie que exactement 50% des programmes s'arrêtent et exactement 50% ne s'arrêtent pas.

Nan. Ce n'est pas ce que signifie "normal". Ou, pour le dire autrement: définir $d_0(n)$ être le nombre de bits qui sont un 0, dans le premier $n$ bits de l'expansion base-2 de $\Omega$ . Dire que $\Omega$ est normal implique que

lim_{n \to \infty} \frac{d_{0} (n)}{n} = 1 / 2.

$\lim_{n \to \infty} {d_0(n) \over n} = 1/2.$

En d'autres termes, "normal" est une notion asymptotique. Cela signifie que si vous regardez suffisamment loin dans les morceaux de $\Omega$ , environ la moitié d'entre eux seront en moyenne des 0. (De même, environ la moitié avec un 1.)

Cependant, cela ne dit rien sur les premiers bits de $\Omega$ . Par exemple, il n'y a aucune implication que l'expansion binaire $\Omega$ commence comme 0,01 ... ou à toute autre chose - et il n'y a aucune implication que $\Omega$ est proche de 1/2. $\Omega$ peut être proche de 0, ou proche de 1, ou n'importe où entre les deux; cela ne contredit pas le fait d'être normal, et être normal n'implique rien sur la taille $\Omega$ est.

DW
la source

Notez que

Ω

$\Omega$ est la probabilité qu'une machine de Turing aléatoire s'arrête sous une distribution très étrange. Le PO s'intéresse à la distribution uniforme (dans un certain sens limitatif). Donc, personne n'implique que

Ω

$\Omega$ est proche de 1/2.

Yuval Filmus