A constante de Chaitin é normal?

Segundo esta fonte, a constante Chaitin é normal. $\Omega$

Cada probabilidade de parada é um número real normal e transcendental que não é computável, o que significa que não há algoritmo para calcular seus dígitos. De fato, cada probabilidade de parada é aleatória de Martin-Löf, o que significa que não existe nenhum algoritmo capaz de adivinhar com precisão seus dígitos.

Fonte (Wikipedia)

Além disso, a definição de normal é que cada dígito ocorre com igual probabilidade . E que cada dueto de dígitos ocorre com probabilidade e todos os trigêmeos ocorrem com probabilidade e assim por diante. $1/b$ $1/b^2$ $1/b^3$

O ômega de Chaitin é calculado via

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

Escrevendo $\Omega$ em binário, obtemos uma lista de 0 e 1. Por exemplo,

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...

Claramente, podemos ver que a posição de cada bit corresponde ao estado de parada do programa de comprimento correspondente ao bit.

Aqui está o que eu estou lutando com

Se $\Omega$ é realmente normal, significa que exatamente 50% dos programas são interrompidos e exatamente 50% não. Isso parece muito contra-intuitivo.

Por exemplo, suponha que eu gere programas java concatenando aleatoriamente caracteres únicos. A maioria deles, acho que mais de 99,99% nem compilaria. Isso não implica que pelo menos 99,99% deles não parem? Como justificamos que exatamente metade irá parar e exatamente a metade não, em virtude de $\Omega$ ser normal.

Ou a wikipedia está incorreta sobre ser normal? $\Omega$

halting-problem Alexandre H. Tremblay
fonte

Bem vindo ao site! Se você colocar o LaTeX entre dólares em vez de reticulares, poderemos ler a saída, e não a fonte.

David Richerby

E para as frações \ frac {1} {b ^ 2} resulta em vez de .

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

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

1 / b^{2}

$1/b^2$

Mal

Acredito que o Omega de Chaitin é definido para codificações sem prefixo da Turing Machine, não para codificações arbitrárias. Nesse caso, acho que nossas intuições normais sobre o que constitui uma MT "aleatória" podem não ser tão confiáveis.

Mhum

@mhum Você pode recodificar qualquer programa em uma codificação sem prefixo adicionando 1 entre cada bit do programa original e finalizando-o com um 0. Em seguida, a máquina de Turing lê cada segundo bit até encontrar o 0 final. Isso deixa o código java intacto, mas o torna livre de prefixos. Portanto, o problema permanece.

Alexandre H. Tremblay,

"Se Ω é realmente normal, significa que exatamente 50% dos programas são interrompidos e exatamente 50% não. Isso parece muito contra-intuitivo". Isso significa que, assintoticamente, metade dos programas é interrompida. Isso não é tão contra-intuitivo. Mesmo que seja necessário algum esforço para encontrar um programa de interrupção (por exemplo, você atinge uma longa seqüência de zeros em Ω), depois de encontrar um, você terá uma série muito longa de programas de interrupção seguindo-o (por exemplo, um seqüência de 1s igualmente longa), por exemplo, programas que são funcionalmente o mesmo programa, mas com um monte de comentários supérfluos postados (uma espécie de lema de bombeamento).

Marcel Besixdouze 01/11/19

Respostas:

Em contraste com o seu exemplo, a constante de Chaitin não é definida da seguinte maneira:

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

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

Em vez disso, existe um conjunto de programas permitidos que não contém prefixos (nenhuma string é o prefixo de outra string). Cada um dos programas em é legal (isso nega o seu exemplo de Java). Se os programas são codificação em unário, então é realmente o caso que o º programa tem comprimento , em seguida, a sua definição de funciona. Mas para outras codificações, a definição de é $\Pi \subseteq \{0,1\}^*$ $\Pi$ $n$ $n$ $\Omega$ $\Omega$

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

$\Omega = \sum_{ p \in \Pi\colon p \text{ halts} } 2^{-|p|},$ queé o comprimento da cadeia binária . A desigualdade de Kraft mostra que .

| p |

$|p|$

p

$p$

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

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

A constante de Chaitin é algoritmicamente aleatória : a complexidade (prefixo) de Kolmogorov dos primeiros bits é . Para mostrar isso, observe primeiro que , os primeiros bits de , são suficientes para determinar se um programa de comprimento (na codificação ) é interrompido ou não. De fato, como uma fração, . Execute todos os programas em paralelo e, sempre que parar, adicione a algum contador (inicializado em zero). Eventualmente, (desde $n$ $n - O(1)$ $\Omega_n$ $n$ $\Omega$ $n$ $\Pi$ $\Omega_n \leq \Omega < \Omega_n + 2^{-n}$ $p$ $2^{-|p|}$ $C$ $C \geq \Omega_n$ $C \to \Omega$ de baixo). Nesse ponto, se o programa de entrada de comprimento não parar, você saberá que ele não será interrompido, pois caso contrário . $n$ $\Omega \geq C + 2^{-n} \geq \Omega_n + 2^{-n}$

Dado isso, suponha que, para alguns e infinitamente muitos , você possa calcular usando bits. Para cada um desses , é possível encontrar uma sequência cuja complexidade de Kolmogorov seja maior que , considerando a saída de todos os programas de duração de no máximo . Para suficientemente grande , o resultado é um programa de comprimento no máximo para computar a string cuja complexidade de Kolmogorov é maior que . Essa contradição prova que, para alguns , a complexidade Kolmogorov de é pelo menos . $K>0$ $n$ $\Omega_n$ $n - K$ $n$ $n$ $n$ $K$ $n$ $n$ $K$ $\Omega_n$ $n-K$

A aleatoriedade algorítmica de implica, em particular, que a frequência de 0s e 1s em sua expansão binária tende a 1/2. De fato, suponha que, para alguns , existam infinitamente muitos tais que a fração de 1s em seja no máximo . Como existem apenas no máximo seqüências com no máximo muitos 1s, podemos compactar no tamanho (a constante depende de pois o programa precisa saber $\Omega$ $\epsilon > 0$ $n$ $\Omega_n$ $1/2-\epsilon$ $2^{h(1/2-\epsilon)n}$ $1/2-\epsilon$ $\Omega_n$ $h(1/2-\epsilon)n + 2\log n + C_\epsilon$ $C_\epsilon$ $\epsilon$ $\epsilon$ ) No entanto, isso é , contradizendo a aleatoriedade algorítmica de . $n - \omega(1)$ $\Omega$

Yuval Filmus
fonte

Obrigado pela resposta muito completa. Estou lutando com o primeiro parágrafo e peço desculpas por não ter passado pelo meu crânio. Se pegarmos apenas os programas java que são compilados e os codificarmos para unários, isso significa que exatamente metade deles será interrompida?

Alexandre H. Tremblay,

@ AlexandreH.Tremblay Sim, essa é a implicação. Para mais, recomendo um livro sobre a complexidade de Kolmogorov, como Li e Vitanyi.

Yuval Filmus

Você poderia criar a máquina de Turing de forma a incluir um compilador java? Imagine isso. Primeiro, liste todas as seqüências de caracteres possíveis geradas aleatoriamente, do menor para o maior. Segundo, codifique essas strings em unárias. Terceiro, alimente as cordas unárias à máquina de Turing como entrada. A máquina de Turing verifica se a entrada é compilada em Java. Se isso acontecer, ele será executado e metade será interrompida e metade não. Se não compilar, será repetido para sempre (while (true) {};). Isso não distorceria a proporção de interrupção / não interrupção? Li Li e Vitanyi na semana passada, mas precisarei ler novamente;).

Alexandre H. Tremblay,

Eu suspeito que a codificação unária da maneira que você sugere não seria admissível . Por exemplo, na codificação unária (mesmo a simples), você não poderá compor programas com sobrecarga constante. Eu verificaria Li e Vitanyi para obter uma lista de propriedades que um computador universal admissível precisa satisfazer. Isso faria parte da definição de complexidade de Kolmogorov.

Yuval Filmus

Olá, você pode recomendar a seção de Li e Vitanyi, onde esta informação está presente. Li o livro uma segunda vez e não consegui encontrá-lo.

Alexandre H. Tremblay

Seu erro está na seguinte linha:

Se é realmente normal, significa que exatamente 50% dos programas são interrompidos e exatamente 50% não. $\Omega$

Não. Não é isso que "normal" significa. Ou, para dizer de outra forma: defina como o número de bits 0, nos primeiros bits da expansão da base-2 de . Dizer que é normal implica que $d_0(n)$ $n$ $\Omega$ $\Omega$

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

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

Em outras palavras, "normal" é uma noção assintótica. Isso significa que, quando você olhar o suficiente para os bits de , em média cerca de metade deles será zero. (Da mesma forma, cerca da metade com 1). $\Omega$

No entanto, isso não diz nada sobre os primeiros bits do . Por exemplo, não há implicações de que a expansão binária comece como 0,01 ... ou qualquer outra coisa - e não há implicações de que esteja próximo de 1/2. pode estar próximo de 0 ou próximo de 1 ou em qualquer outro local; isso não contradiz ser normal, e ser normal não implica nada sobre o tamanho do . $\Omega$ $\Omega$ $\Omega$ $\Omega$ $\Omega$

DW
fonte

Observe que é a probabilidade de uma máquina de Turing aleatória parar sob uma distribuição muito estranha. O OP está interessado na distribuição uniforme (em certo sentido limitante). Portanto, ninguém está sugerindo que está perto de 1/2.

Ω

$\Omega$

Ω

$\Omega$

Yuval Filmus