Saltar para o conteúdo

Constante de Chaitin

Origem: Wikipédia, a enciclopédia livre.
Representação em ASCII da ômega de Chaiting

Em ciência da computação, na sub-área de teoria da informação algorítmica, a constante de Chaitin (número Ômega de Chaitin)[1] ou probabilidade de parada é um número real que informalmente representa a probabilidade de que um programa construído de forma aleatória irá parar. Estes números são formados de uma construção de Gregory Chaitin.

Apesar de haver uma infinidade de probabilidades de parada, é comum usar o letra Ω para nos referirmos a elas como se fossem apenas uma. Porque Ω depende da codificação utilizada no programa, então é chamado as vezes de Construção de Chaitin ao invés de Constante de Chaitin quando não referencia nenhuma codificação específica.

Cada probabilidade de parada é um número real normal e transcendente que não é computável, o que significa que não existe algoritmo para computar aqueles dígitos. De fato, cada probabilidade de parada é uma sequência aleatória de Martin-Löf, representando que não existe algoritmo algum que possa adivinhar de fato seus dígitos.

A definição de uma probabilidade de parada remete à existência de funções computáveis universais livres de prefixo. Como uma função, intuitivamente, representa uma linguagem de programação com a propriedade de que nenhum programa válido pode ser obtido como uma extensão apropriada de outro programa válido.

Suponha que F é uma função parcial que recebe um argumento, uma string binária finita, e possivelmente retorna uma única string binária como saída. A função F é chamada computável se existe uma Máquina de Turing que a computa (no sentido de que para qualquer string binária x tal que F(x) = y a máquina de Turing para com y em sua fita quando dada a entrada x).

A função F é chamada universal se a possui a seguinte propriedade: para cada função computável f de uma única variável, existe uma string w de modo que para todo x, F(w x) = f(x); aqui w x representa a concatenação de duas strings w e x. Isso significa que F pode ser usado para simular qualquer função computável de uma variável. Informalmente, w representa um "script" para a função computável f, e F representa um "interpretador" que analisa o script como um prefixo de sua entrada e então executa ele no restante da entrada.

O domínio de F é o conjunto de todas as entradas p em que ele é definido. Para os F que são universais, p podem ser geralmente vistas como ambos uma concatenação de uma parte de um programa e parte de dados, e como um único programa para a função F.

A função F é chamada livre de prefixo se não houver dois elementos p, p′ em seu domínio tal que p′ é uma extensão própria de p. Isso pode ser definido como: o domínio de F é um código livre de prefixo (código instantâneo) no conjunto de strings binárias finitas. Uma maneira simples de aplicar o prefixo livre é usar máquinas das quais a entrada é um fluxo binário de bits que são lidos um por vez. Não existe marcador de fim da cadeia; o fim da entrada é determinado pela máquina universal que decide parar de ler mais bits. Aqui, a diferença entre duas noções de programas mencionados no último parágrafo se tornam claras; uma é facilmente reconhecida por alguma gramática, enquanto a outra requer computação arbitrária para ser reconhecida.

O domínio de qualquer função universal computável é um computavelmente enumerável mas nunca um conjunto computável. O domínio é sempre Turing equivalente ao problema da parada.

Seja PF o domínio de uma função computável universal livre de prefixo universal F. A constante ΩF é então definida como

,

onde é o tamanho de uma string p. É uma soma infinita que tem uma soma para cada p no domínio de F. O requerimento é que o domínio seja livre de prefixo, juntamente a desigualdade de Kraft, garante que essa soma converge para um número real entre 0 e 1. Se F é uma consequência do contexto então ΩF pode ser simplesmente denominado Ω, ainda que diferentes funções universais livres de prefixo levam à difrentes valores de Ω.

Relação com o problema da parada

[editar | editar código-fonte]

Conhecendo os primeiros bits de , pode-se calcular o problema da parada para todos os programas de tamanho até . Seja o programa para qual o problema da parada deve ser resolvido em N bits de tamanho. Em um implementador universal de forma, todos os programas de todos os tamanhos são rodados, até que um número suficiente deles tiverem parado para assim contribuir conjuntamente com probabilidade suficiente para combinar estes primeiros N bits. Se o programa ainda não parados, então ele nunca irá parar, desde que sua constribuição à probabilidade da parada irá afetar os primeiros N bits. Assim, o problema da parada vai ser resolvido por .

Por causa de muitos problemas pendentes em teoria dos números, como a conjectura de Goldbach são equivalentes à resolver o problema da paradapara programas especiais (que irão basicamente procurar por contraexemplos e para se um for achado), sabendo bits o suficiente da constante de Chaitin irá também significa saber a resposta para esses problemas. Mas como o problema da parada geralmente não é solúvel, e portanto calcular qualquer um exceto os primeiros bits da constante de Chaitin não é possível, isso apenas reduz problemas difíceis para problemas impossíveis, seria como tentar construir uma máquina de oráculo para o problema da parada.

Interpretação como uma probabilidade

[editar | editar código-fonte]

O espaço de Cantor é uma coleção de todas as sequencias infinitas de 0s e 1s. A probabilidade de parada pode ser interpretada como a medida de um determinado subconjunto do espaço de Cantor sob a medida de probabilidade no espaço de Cantor. É a partir dessa interpretação que as probabilidades de paradas têm seu nome.

A medida de probabilidade no espaço Cantor, algumas vezes chamada de "medida da moeda justa", é definido tal que para qualquer string binária x o conjunto de sequências que começam com x tem medida 2−|x|. Isso implica que para cada número natural n, o conjunto de sequências f no espaço de Cantor tal que f(n) = 1 tem medida 1/2, e o conjunto de sequências as quais o n-ésimo elemento é 0 também tem medida 1/2.

Seja F uma função computável universal livre de prefixo. O domínio P de F consiste em um conjunto infinito de strings binárias

.

Cada uma dessas strings pi determina um subconjunto Si do espaço de Cantor; o conjunto Si contém todas as sequências no espaço de Cantor que começam com pi. Esses conjuntos são disjuntos porque P é um conjunto livre de prefixo. A soma

representa e medida do conjunto

.

Desta forma, ΩF representa a probabilidade de que selecionado aleatoriamente uma sequência infinita de 0s e 1s que começam com uma cadeia de bits (de algum tamanho finito) que está no domínio de F. É por essa razão que ΩF é chamado probabilidade de parada.

Cada constante de Chaitin Ω tem as seguintes propriedades:

  • É algoritmicamente aleatória.[2] Isso significa que o menor programa para produzir os primeiros n bits de Ω deve ser de tamanho pelo menos n-O(1). Isso porque, como no exemplo de Goldbach, aqueles n bits nos permitem achar exatamente qual programa para entre todos aqueles de tamanho no máximon.
  • É um número normal, o que significa que seus dígitos são igualmente distribuidos como se fossem gerados por um lançamento de uma moeda justa.
  • Não é um número computável; não há função computável que enumera sua expansão binária, como discutido abaixo.
  • É o conjunto de números racionais q tal que q < Ω é computavelmente enumerável;[3] um número real com a propriedade que é chamada número real c.e.-esquerda (computavelmente enumerável à esquerda) em teoria da recursão.
  • É o conjunto de números racionais q tal que q > Ω não é computavelmente enumerável.
  • Ω é um número aritmético.
  • É Turing equivalente ao problema da parada e, assim, ao nível da hierarquia aritmética.

Nem todo conjunto que é Turing equivalente ao problema da parada é uma probabilidade de parada. A mais fina relação de equivalência, equivalência Solovay, pode ser usada para caracterizar a probabilidade de parada entre os reais c.e.-esquerda.[4]

Incomputabilidade

[editar | editar código-fonte]

Um número real é chamado calculável se existe um algoritmo que, dado n, retorna os primeiros n dígitos do número. Isto é equivalente à existência de um programa que enumera os dígitos do número real.

Nenhuma probabilidade de parada é computável. A prova desse fato depende de um algoritmo que, dada os primeiros n dígitos de Ω, resolve o problema da parada de Turing por programas de tamanho até n. Uma vez que o problema da parada é indecidível, Ω não pode ser computado.

O algoritmo procede como descrito a seguir. Dado os primeiros n dígitos de Ω e um kn, o algoritmo enumera o domínio de F até elementos suficientes do domínio serem encontrados de modo que a probabilidade de que eles representam é dentro do limite de 2−(k+1) de Ω. Depois deste ponto, nenhum programa adicional de tamanho k pode estar em seu domínio, porque cada um destes iria adicionark para a medida, o que é impossível. Assim, o conjunto de cadeias de comprimento k no domínio é exatamente o conjunto de tais sequências já enumerados.

Teorema da incompletude para probabilidade de parada

[editar | editar código-fonte]

Para cada sistema axiomático específico representado consistentemente e eficazmente para números naturais, como os da Aritmética de Peano, existe uma constante N tal qual nenhum bit de Ω depois do N-ésimo pode ser provado ser 1 ou 0 dentor desse sistema. A constante N depende de como o sistema formal [e efetivamente representado, e assim não reflete diramente a complexidade do sistema axiomático. Esse resultado da incompletude é similar ao Teorema da Incompletude de Gödel que mostra que nenhuma forma teórica consistente para aritmética pode ser completa.

Como mencionado acima, os primeiros n bits da constante Ômega de Gregory Chaitin são aleatórios ou incompreensíveis no sentido de que nós não podemos computá-los por um algoritmo de parada com menos que n-O(1) bits. Entretanto, considere o algoritmo curto, mas nunca um de parada que lista sistematicamente e executa todos os programas possíveis;sempre que um deles é interrompido sua probabilidade é adicionado à saída (inicializada em zero). Depois de um tempo finito os primeiros n bits da saída nunca mais vão mudar (não importa que se desta vez não é computável por um programa de parada). Portanto, há um algoritmo não-parante e curto cuja saída converge (depois de tempo finito) nos primeiros n bits de Ômega. Em outras palavras, os primeiros n bits enumeráveis de Omega são altamente compreensíveis no sentido que são limite computáveis por um algoritmo muito pequeno; eles não são aleatórios com respeito ao conjunto de algoritmos enumerados. Jürgen Schmidhuber (2000) construiu um "Super Ômega" limite computável que num certo sentido é muito mais aleatória do que o limite computável Ômega original, como não se pode comprimir significativamente o Super Ômega por qualquer algoritmo enumerado não-parante.

Referências

  1. MathWorld, Chaitin's Constant. Visitado em 28 de Maio de 2012
  2. Downey & Hirschfeldt 2010, Teorema 6.1.3.
  3. Downey & Hirschfeldt 2010, Teorema 5.1.11.
  4. Downey & Hirschfeldt 2010, p. 405.
  • Calude, Cristian S. (2002). Information and Randomness: An Algorithmic Perspective second ed. [S.l.]: Springer. ISBN 3-540-43466-6 
  • Downey, R.; Hirschfeldt, D. (2010). Algorithmic Randomness and Complexity. [S.l.]: Springer-Verlag 
  • Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. [S.l.]: Springer 
  • Schmidhuber, Jürgen (2002). «Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit». International Journal of Foundations of Computer Science. 13 (4): 587–612. doi:10.1142/S0129054102001291 

Ligações externas

[editar | editar código-fonte]