Constante de Chaitin

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 devido a Gregory Chaitin.

Embora existam infinitas probabilidades de parada, uma para cada método de codificação de programas, é comum usar a letra Ω para se referir a elas como se houvesse apenas uma. 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 há nenhum algoritmo que possa adivinhar com segurança seus dígitos.

Fundo

A definição de uma 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 é chamada de computável se houver uma máquina de Turing que a calcule (no sentido de que para quaisquer strings binárias finitas x e y, F(x) = y se e somente se a máquina de Turing parar com y em sua fita quando dada a entrada x).

A função F é chamada de universal se a seguinte propriedade for válida: para cada função computável f de uma única variável existe 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 "intérprete" 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, tal p geralmente pode ser visto como a concatenação de uma parte de programa e uma 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 apropriada de p. Isso pode ser reformulado como: o domínio de F é um código sem prefixo (código instantâneo) no conjunto de strings binárias finitas. Uma maneira simples de impor a ausência de prefixo é usar máquinas cujo meio de entrada seja um fluxo binário do qual os bits possam ser lidos um por 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 fica clara a diferença entre as duas noções de programa mencionadas no último parágrafo; 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 computavelmente enumerá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 computável universal sem prefixo F. A constante Ω_F é então definida como

Ω Ω F= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Gerenciamento Gerenciamento p∈ ∈ PF2- Sim. - Sim. |p|Não. Omega _{F}=sum _{pin P_{F}}2^{-|p|}},

Onde? |p|{displaystyle left|pright|}} denota o comprimento de uma string p. Esta é uma soma infinita que tem uma soma 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 convergiu para um número real entre 0 e 1. Se F é claro do contexto, então Ω_F pode ser denotado simplesmente Ω, embora diferentes funções computáveis universais livres de prefixo levem a diferentes valores de Ω.

Relação com o problema de parada

Conhecendo os primeiros N bits de Ω, pode-se calcular o problema de parada para todos os programas de tamanho até N. Deixe o programa p para o qual o problema de 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 o suficiente tenha parado para contribuir conjuntamente com probabilidade suficiente para corresponder a esses primeiros N bits. Se o programa p ainda não parou, 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.

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

Interpretação como uma probabilidade

O espaço de 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 de Cantor sob a medida de probabilidade usual no espaço de Cantor. É a partir dessa interpretação que as probabilidades de parada recebem 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 meça 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 compasso 1/2, e o conjunto de sequências cujo nésimo elemento é 0 também tem compasso 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

P= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(p1,p2,...... ?Não. P={p_{1},p_{2},ldots }}.

Cada uma dessas strings p_i determina um subconjunto S_i do espaço 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 disjuntos porque P é um conjunto sem prefixo. A soma

Gerenciamento Gerenciamento p∈ ∈ P2- Sim. - Sim. |p|{displaystyle sum _{pin P}2^{-|p|}}

representa a medida do conjunto

⋃ ⋃ Eu...∈ ∈ NSEu...{displaystyle bigcup _{iin mathbb {N} }S_{i}}.

Desta forma, Ω_F representa a probabilidade de que uma sequência infinita de 0s e 1s selecionada aleatoriamente comece com uma cadeia de bits (de algum comprimento finito) que está em o domínio de F. É por esta razão que Ω_F é chamado de probabilidade de parada.

Propriedades

Cada constante de Chaitin Ω tem as seguintes propriedades:

• É algoticamente aleatório (também conhecido como Martin-Löf aleatório ou 1-random). Isso significa que o programa mais curto para produzir o primeiro n bits de Ω deve ser de tamanho pelo menos n - O(1). Isso é porque, como no exemplo Goldbach, aqueles n bits nos permitem descobrir exatamente quais programas param entre todos os 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 fossem gerados por lançar uma moeda justa.
• Não é um número computável; não há nenhuma 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; um número real com tal propriedade é chamado de número real. em teoria da recursão.
• O conjunto de números racionais q tal que q > Ω não é computavelmente enumerável. (Reason: cada esquerda-c.e. real com esta propriedade é computável, que Ω não é.)
• Ω é um número aritmético.
• É Turing equivalente ao problema de parada e, portanto, em nível ? ? 20{displaystyle Delta _{2}^{0}} da hierarquia aritmética.

Nem todo conjunto que é Turing equivalente ao problema da parada é uma probabilidade de parada. Uma relação de equivalência mais refinada, equivalência de Solovay, pode ser usada para caracterizar as probabilidades de parada entre a esquerda-c.e. reais. 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 livre de prefixo) se e somente se for c.e. 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 é de todo típico de todos os números aleatórios algorítmicos.

Incomputabilidade

Um número real é dito computável se existe 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 deste fato se baseia em um algoritmo que, dados os primeiros n dígitos de Ω, resolve o problema de parada de Turing para programas de comprimento até n. Como o problema da parada é indecidível, Ω não pode ser calculado.

O algoritmo procede da seguinte forma. Dados os primeiros n dígitos de Ω e um k ≤ n, o algoritmo enumera o domínio de F até elementos do domínio foram encontrados de modo 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 cadeias de comprimento k no domínio é exatamente o conjunto de tais cadeias já enumeradas.

Aleatoriedade algorítmica

Um número real é aleatório se a sequência binária que representa o número real é 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 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ésimo 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 Ômega

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 calculá-los por um algoritmo de parada com menos de n-O(1) bits. No entanto, considere o algoritmo curto, mas nunca parado, que lista e executa sistematicamente todos os programas possíveis; sempre que um deles pára, 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 sem parada 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 compressíveis no sentido de que são computáveis no 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 Ω" que, em certo sentido, é muito mais aleatório do que o Ω limite computável original, já que não se pode comprimir significativamente o Super Ω por qualquer algoritmo de enumeração sem interrupção.

Para uma alternativa "Super Ω", a probabilidade de universalidade de uma máquina de Turing Universal sem prefixo (UTM) – ou seja, a probabilidade de que ela permaneça universal mesmo quando cada entrada dele (como uma cadeia binária) é prefixada por uma cadeia binária aleatória – pode ser vista como a probabilidade não-medida de uma máquina com oráculo a terceira iteração do problema de parada (ou seja, O(3){displaystyle O^{(3)}}usando Turing Jump notation).