Constante de Chaitin - Chaitin's constant

No subcampo da ciência da computação da teoria da informação algorítmica , uma constante de Chaitin ( número ômega de Chaitin ) ou probabilidade de parada é um número real que, informalmente falando, representa a probabilidade de que um programa construído aleatoriamente pare. Esses números são formados a partir de uma construção devida a Gregory Chaitin .

Embora haja infinitas probabilidades de parada, uma para cada método de codificação de programas, é comum usar a letra Ω para se referir a eles como se houvesse apenas um. Como Ω depende da codificação do programa usada, às vezes é chamado de construção de Chaitin quando não se refere a nenhuma codificação específica.

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. Cada probabilidade de parada é aleatória de Martin-Löf , o que significa que não existe nenhum algoritmo que possa adivinhar seus dígitos com segurança.

Fundo

A definição de probabilidade de parada depende da existência de uma função computável universal sem prefixo. Tal 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 adequada de outro programa válido.

Suponha que F seja 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 é chamado calculável se existe uma máquina de Turing que calcula TI (no sentido que para qualquer finito binário cadeias X e Y, F (x) = y se e somente se as paragens da máquina de Turing com y na sua fita quando dada a entrada x ).

A função F é chamada universal se a seguinte propriedade for válida: para cada função computável f de uma única variável, há uma string w tal que para todo x , F ( w  x ) = f ( x ); aqui w  x representa a concatenação das 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 o executa no restante da entrada.

O domínio de F é o conjunto de todas as entradas p nas quais ele é definido. Para F que são universais, de tal p pode geralmente ser visto tanto como a concatenação de uma parte do programa e uma parte de dados, e como um programa único para a função F .

A função F é chamada de livre de prefixo se não houver dois elementos p , p ′ em seu domínio de forma que p ′ seja uma extensão própria de p . Isso pode ser reformulado como: o domínio de F é um código sem prefixo (código instantâneo) no conjunto de cadeias binárias finitas. Uma maneira simples de impor a ausência de prefixo é usar máquinas cujo meio de entrada é um fluxo binário do qual os bits podem ser lidos um de cada vez. Não há marcador de fim de fluxo; o fim da entrada é determinado quando a máquina universal decide parar de ler mais bits, e os bits restantes não são considerados parte da string aceita. Aqui, a diferença entre as duas noções de programa mencionadas no último parágrafo torna-se clara; um é facilmente reconhecido por alguma gramática, enquanto o outro requer computação arbitrária para ser reconhecido.

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

Definição

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

${\ displaystyle \ Omega _ {F} = \ sum _ {p \ in P_ {F}} 2 ^ {- | p |}}$,

onde denota o comprimento de uma string p . Esta é uma soma infinita que tem uma summand para cada p no domínio de F . A exigência de que o domínio seja livre de prefixo, juntamente com a desigualdade de Kraft , garante que essa soma converta para um número real entre 0 e 1. Se F for claro no contexto, então Ω _F pode ser denotado simplesmente Ω, embora seja diferente universal sem prefixo funções computáveis ​​levam a diferentes valores de Ω. ${\ displaystyle \ left | p \ right |}$

Relação com o problema da parada

Conhecer os primeiros N bits de Ω, pode-se calcular o problema da parada para todos os programas de um tamanho de até N . Seja o programa p para o qual o problema da parada deve ser resolvido ter N bits de comprimento. No modo de encaixe , todos os programas de todos os comprimentos são executados, até que um número suficiente pare para contribuir conjuntamente com probabilidade suficiente para corresponder a esses primeiros N bits. Se o programa p ainda não parou, então nunca o fará, pois sua contribuição para a probabilidade de parada afetaria os primeiros N bits. Assim, o problema da parada seria resolvido para p .

Como muitos problemas pendentes na teoria dos números, como a conjectura de Goldbach , são equivalentes a resolver o problema de parada para programas especiais (que basicamente buscariam contra-exemplos e parariam se algum fosse encontrado), saber bits suficientes da constante de Chaitin também implicaria em saber a resposta para esses problemas. Mas como o problema da parada geralmente não tem solução e, portanto, o cálculo de qualquer um, exceto os primeiros bits da constante de Chaitin não é possível, isso apenas reduz os problemas difíceis a problemas impossíveis, da mesma forma que tentar construir uma máquina de oráculo para o problema da parada seria.

Interpretação como uma probabilidade

O espaço Cantor é a coleção de todas as sequências infinitas de 0s e 1s. Uma probabilidade de parada pode ser interpretada como a medida de um certo subconjunto do espaço Cantor sob a medida de probabilidade usual no espaço Cantor. É dessa interpretação que as probabilidades de parada levam seu nome.

A medida de probabilidade no espaço de Cantor, às vezes chamada de medida de moeda justa, é definida de modo que para qualquer string binária x o conjunto de sequências que começam com x tenha 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 cujo n- ésimo elemento é 0 também tem medida 1/2.

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

${\ displaystyle P = \ {p_ {1}, p_ {2}, \ ldots \}}$.

Cada uma dessas cadeias p _i determina um subconjunto S _i do espaço de Cantor; o conjunto S _i contém todas as sequências no espaço do cantor que começam com p _i . Esses conjuntos são separados porque P é um conjunto sem prefixo. A soma

${\ displaystyle \ sum _ {p \ in P} 2 ^ {- | p |}}$

representa a medida do conjunto

${\ displaystyle \ bigcup _ {i \ in \ mathbb {N}} S_ {i}}$.

Desta forma, Ω _F representa a probabilidade de que uma sequência infinita seleccionado aleatoriamente de 0 e 1 começa com uma cadeia de bits (de alguns comprimento finito) que se encontra no domínio de F . É por esta razão que Ω _F é chamada de probabilidade de parada.

Propriedades

Cada constante de Chaitin Ω tem as seguintes propriedades:

• É algoritmicamente aleatório (também conhecido como Martin-Löf random ou 1-random). Isso significa que o programa mais curto para produzir os primeiros n bits de Ω deve ter o tamanho de pelo menos n -O (1). Isso ocorre porque, como no exemplo de Goldbach, esses n bits nos permitem descobrir exatamente quais programas param entre todos aqueles de comprimento no máximo n .
• Como consequência, é um número normal , o que significa que seus dígitos são equidistribuídos como se tivessem sido gerados pelo lançamento de uma moeda justa.
• Não é um número computável ; não há função computável que enumere sua expansão binária, conforme discutido abaixo.
• O conjunto de números racionais q tais que q <Ω é computável enumerável ; um número real com tal propriedade é chamado de número real esquerdo na teoria da recursão .
• O conjunto de números racionais q tais que q > Ω não é computavelmente enumerável. (Motivo: todo real ce esquerdo com esta propriedade é computável, o que Ω não é.)
• Ω é um número aritmético .
• É Turing equivalente ao problema da parada e, portanto, no nível da hierarquia aritmética .${\ displaystyle \ Delta _ {2} ^ {0}}$

Nem todo conjunto equivalente a Turing ao problema da parada é uma probabilidade de parada. Uma relação de equivalência mais fina , a equivalência de Solovay , pode ser usada para caracterizar as probabilidades de parada entre os reais da esquerda. Pode-se mostrar que um número real em [0,1] é uma constante de Chaitin (ou seja, a probabilidade de parada de alguma função computável universal sem prefixo) se e somente se for à esquerda e algoritmicamente aleatório. Ω está entre os poucos números aleatórios algorítmicos definíveis e é o número aleatório algorítmico mais conhecido, mas não é típico de todos os números aleatórios algorítmicos.

Incomputabilidade

Um número real é denominado computável se houver um algoritmo que, dado n , retorna os primeiros n dígitos do número. Isso equivale à 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, dados os primeiros n dígitos de Ω, resolve o problema de parada de Turing para programas de comprimento até n . Uma vez que o problema da parada é indecidível , Ω não pode ser calculado.

O algoritmo prossegui como desejado. Dados os primeiros n dígitos de Ω e a k ≤ n , o algoritmo enumera o domínio de F até que elementos suficientes do domínio sejam encontrados para que a probabilidade que eles representam esteja dentro de 2 ^{- ( k +1)} de Ω. Após este ponto, nenhum programa adicional de comprimento k pode estar no domínio, porque cada um deles adicionaria 2 ^{- k} à medida, o que é impossível. Assim, o conjunto de strings de comprimento k no domínio é exatamente o conjunto de tais strings já enumeradas.

Aleatoriedade algorítmica

Um número real é aleatório se a sequência binária que representa o número real for uma sequência algorítmica aleatória . Calude, Hertling, Khoussainov e Wang mostraram que um número real recursivamente enumerável é uma sequência algorítmica aleatória se e somente se for um número Ω de Chaitin.

Teorema da incompletude para probabilidades de parada

Para cada sistema axiomático consistente específico efetivamente representado para os números naturais , como a aritmética de Peano , existe uma constante N tal que nenhum bit de Ω após o N- th pode ser provado ser 1 ou 0 dentro desse sistema. A constante N depende de como o sistema formal é efetivamente representado e, portanto, não reflete diretamente a complexidade do sistema axiomático. Este resultado da incompletude é semelhante ao teorema da incompletude de Gödel , pois mostra que nenhuma teoria formal consistente para a aritmética pode ser completa.

Super Omega

Como mencionado acima, os primeiros n bits da constante Ω de Gregory Chaitin são aleatórios ou incompressíveis no sentido de que não podemos computá-los por um algoritmo de parada com menos de nO (1) bits. No entanto, considere o algoritmo curto, mas nunca interrompido, que lista e executa sistematicamente todos os programas possíveis; sempre que um deles para, sua probabilidade é adicionada à saída (inicializada por zero). Depois de um tempo finito, os primeiros n bits da saída nunca mais mudarão (não importa que esse tempo em si não seja computável por um programa de parada). Portanto, existe um algoritmo curto não interrompido cuja saída converge (após um tempo finito) para os primeiros n bits de Ω. Em outras palavras, os primeiros n bits enumeráveis de Ω são altamente compactáveis ​​no sentido de que são computáveis por limite por um algoritmo muito curto; eles não são aleatórios em relação ao conjunto de algoritmos de enumeração. Jürgen Schmidhuber (2000) construiu um "Super Ω" limite-computável que, em certo sentido, é muito mais aleatório do que o limite-computável Ω original, visto que não se pode comprimir significativamente o Super Ω por qualquer algoritmo enumerador não interrompido.

Para um "Super Ω" alternativo, a probabilidade de universalidade de uma Máquina de Turing Universal (UTM) sem prefixo - ou seja, a probabilidade de que permaneça universal mesmo quando cada entrada dela (como uma string binária ) é prefixada por uma string binária aleatória - pode ser visto como a probabilidade de não parada de uma máquina com oráculo a terceira iteração do problema de parada (ou seja, usando a notação de Turing Jump ). ${\ displaystyle O ^ {(3)}}$

Veja também

• Teorema da Incompletude
• Complexidade de Kolmogorov

Referências

Trabalhos citados

• Cristian S. Calude (2002). Information and Randomness: An Algorithmic Perspective , second edition. Springer. ISBN  3-540-43466-6
• Cristian S. Calude, Michael J. Dinneen e Chi-Kou Shu. Computing a Glimpse of Randomness .
• R. Downey e D. Hirschfeldt (2010), Algorithmic Randomness and Complexity , Springer-Verlag.
• Ming Li e Paul Vitányi (1997). Uma introdução à complexidade de Kolmogorov e suas aplicações . Springer. Texto completo do capítulo de introdução .
• Jürgen Schmidhuber (2000). Teorias Algorítmicas de Tudo (arXiv: quant-ph / 0011122). Referência do jornal: J. Schmidhuber (2002). Hierarquias de complexidades de Kolmogorov generalizadas e medidas universais inumeráveis ​​computáveis ​​no limite. International Journal of Foundations of Computer Science 13 (4): 587-612.

links externos

• Aspectos do artigo da Pesquisa Ômega de Chaitin que discute os avanços recentes no estudo do Ômega de Chaitin.
• Omega e por que a matemática não tem nenhum artigo TOEs baseado em um escrito por Gregory Chaitin que apareceu na edição de agosto de 2004 do Mathematics Today, por ocasião do 50º aniversário da morte de Alan Turing.
• The Limits of Reason , Gregory Chaitin, apareceu originalmente na Scientific American, março de 2006.
• Super Omega computável com limite mais aleatório do que Omega e generalizações de informações algorítmicas, por Jürgen Schmidhuber