Comparando a complexidade das teorias de Kolmogorov

O teorema da incompletude de Chaitin diz que nenhuma teoria aritmética suficientemente forte pode provar onde é a complexidade Kolmogorov da corda e é uma constante suficientemente grande. é suficientemente grande se for maior que o tamanho em bits de uma máquina de verificação de provas (PCM). A PCM para a teoria leva uma string codificada como um inteiro como entrada e gera um 1 se a string é uma prova válida na linguagem da . $K(s) > L$ $K(s)$ $s$ $L$ $L$ $T$ $T$

Suponha quepara teoria é um limite superior para a complexidade de . Considere a seguinte hierarquia de teorias: Seja a teoria da base aritmética de Robinson ( ). Aumentar com axiomas cada vez mais fortes de indução limitada polinomial. Seja a teoria dos teoremas comprovável com e qualquer um desses axiomas de indução limitados. Suponha que possamos definir e definindo PCMs para cada teoria. $L(T) > |PCM_T|$ $T$ $T$ $Q$ $Q$ $Q^*$ $Q$ $L(Q)$ $L({Q^*})$

Quero considerar uma EPCM (máquina de verificação de provas aprimorada) para . Este EPCM usa uma string como entrada, assim como um ECM, e tem uma segunda entrada que define a classificação e o nível de uma sub-teoria de . Se a sequência de entrada for uma prova válida em o EPCM seguirá as etapas da prova para determinar a classificação mais alta e o nível de indução usado. Este EPCM então escreve 1 se a sentença de entrada for uma prova válida na subteoria especificada de . $Q^*$ $Q^*$ $Q^*$ $Q^*$

O verificador de prova aprimorado que descrevo é viável? Nesse caso, o tamanho deste EPCM seria um limite superior não apenas para a complexidade de $Q^*$ , mas também um limite superior para a complexidade de qualquer subteoria de $Q^*$ ?

É razoável dizer que há um limite superior constante na complexidade de $Q^*$ e em todas as suas sub-teorias?

Essa questão foi inspirada pela prova falhada de Nelson da inconsistência da aritmética. Não mencionei isso antes, porque algumas pessoas acham essa prova perturbadora. Minha motivação é fazer uma pergunta interessante. CSTheory parece ser o fórum certo para esta pergunta. A complexidade de $Q^*$ e todas as suas sub-teorias são limitadas por uma constante ou ilimitada. Qualquer resposta leva a mais perguntas.

Se a complexidade das sub-teorias é ilimitada, podemos fazer perguntas como qual é a sub-teoria mais fraca de mais complexa que ? Ou mais complexo que PA e ZFC? Pensar nessa questão já me mostrou que há um limite severo de quanto uma teoria pode provar sobre a complexidade das cordas de Kolmogorov. Se for consistente, nenhuma de suas sub-teorias pode provar para qualquer string. Isso significa que mesmo sub-teorias realmente fortes não podem provar que há seqüências mais complexas do que uma sub-teoria muito mais fraca, onde a teoria mais fraca é mais complexa que $Q^*$ $Q^*$ $Q^*$ $K(s) > L(Q^*)$ . $Q^*$

lo.logic kolmogorov-complexity Russell Easterly
fonte

Isso está correto, mas é claro que a entrada adicional (

, digamos) necessária para verificar a restrição no esquema de indução é de complexidade ilimitada, portanto é um pouco enganador sugerir que você limitou essas complexidades uniformemente .

n

$n$

A complexidade adicional seria

. Se eu precisar de

, teria apenas que mostrar

l o g (n)

$log(n)$

n \leq L

$n \le L$

L > c + l o g (L)

$L > c+log(L)$

Russell Easterly

Sua anotação me lembra um pouco perturbador desta tentativa incorreta de provar inconsistência aritmética. Você pode esclarecer suas motivações?

Oi Russell. Isso me parece bastante interessante. Se você quiser conversar, entre em contato. Tenha um bom dia! :)

Michael Wehar

Sim, essa TM pode ser usada para definir a complexidade de uma teoria. Estou perguntando se existe um limite no tamanho dessa TM quando temos várias teorias.

Russell Easterly 07/02

Respostas:

Tentarei dar uma resposta a esta pergunta e tentar esclarecer algumas confusões quanto à forma exata da pergunta.

O primeiro ponto que eu quero fazer: o no resultado do constante de chaitin é de fato uma função de . No sentido absoluto , é monotônico na expressividade de : se é o menor número natural para o qual para qualquer corda , então se é uma teoria consistente mais forte que ( implica $L$ $T$ $T$ $L(T)$

T ⊬ K (s) \geq L (T)

$T\not\vdash K(s)\geq L(T)$

s

$s$

T^{'}

$T'$

T

$T$

T ⊢ φ

$T\vdash\varphi$

para qualquer frase aritmética

), então

. O argumento é muito simples: se existe

tal que

então

por hipótese.

T^{'} ⊢ φ

$T'\vdash\varphi$

φ

$\varphi$

L (T^{'}) \geq L (T)

$L(T')\geq L(T)$

s

$s$

T ⊢ K (s) \geq L

$T\vdash K(s)\geq L$

T^{'} ⊢ K (s) \geq L

$T'\vdash K(s)\geq L$

No entanto, isso só é verdade se for a constante absoluta de Chaitin. Em particular, se prova , então $L(T)$ $T'$ $\mathrm{Con}(T)$

T^{'} ⊢ \exists L \forall s ⌈ T ⊬ K (\bar{s}) \geq \bar{L} ⌉

$T'\vdash \exists L\forall s\ \lceil T\not\vdash K(\overline{s})\geq \overline{L}\rceil$

internalizando o argumento de Chaitin. No entanto , um concreto para o qual $l$

T^{'} ⊢ \forall s ⌈ T ⊬ K (\bar{s}) \geq \bar{l} ⌉

$T'\vdash\forall s\ \lceil T\not\vdash K(\overline{s})\geq\overline{l}\rceil$

em geral, não será igual a $L(T)$ . Em particular, pode ser muito maior, geralmente proporcional ao tamanho da prova de em $\mathrm{Con}(T)$ $T'$ . Isso pode ser facilmente visto na prova do próprio teorema, que depende fundamentalmente da consistência da . $T$

Assim, enquanto pode provar consistência do sistema com indução limitada, o comprimento dessas provas fica mais longo quanto mais você se aproxima de em expressividade (uma maneira de entender os teoremas da incompletude é que o comprimento se torna infinito quando você atinge , portanto, não tem nenhuma prova finito de consistência no si). Assim, o mesmo aplica-se aos vários limites superiores no interna s pode descrever para cada sub-teoria. $Q^*$ $Q^*$ $Q^*$ $Q^*$ $L(T)$ $Q^*$

Então aqui está a resposta curta para sua pergunta: é delimitada uniformemente para todos os subteorias de , mas si não pode mostrar que esse limite é válido para todos esses subteorias. Esse foi o erro crucial que Nelson cometeu (enterrado sob várias camadas de formalismo) e que Tao apontou aqui . $L(T)$ $Q^*$ $Q^*$

cody
fonte

A PRA pode provar

. O tamanho dessa prova é um limite superior da complexidade de

e de todas as suas sub-teorias (assumindo uma codificação compatível de axiomas, sentenças etc.)?

C o n (Q^{*})

$Con(Q^*)$

Q^{*}

$Q^*$

Russell Easterly

O PRA pode dar um limite uniforme para

para cada uma das sub-teorias. desde que

e para qualquer sub-teoria

, e por isso, não é difícil para mostrar que o destino a

também funciona para

(dentro PRA).

L

$L$

P R A ⊢ C o n (Q^{*})

$\mathrm{PRA}\vdash \mathrm{Con}(Q^*)$

T

$T$

Q^{*}

$Q^*$

P R A ⊢ C o n (Q^{*}) \to C o n (T)

$\mathrm{PRA}\vdash\mathrm{Con}(Q^*)\rightarrow\mathrm{Con}(T)$

Q^{*}

$Q^*$

T

$T$

cody

Q^{*}

$Q^*$

Hey Cody, obrigado pela resposta. Espero que esteja tudo bem. :)

Michael Wehar

Obrigado Mike! Esta foi uma pergunta divertida. O fato do próprio Nelson ficou confuso nos detalhes sugere que existem algumas armadilhas sutis ao longo do caminho ...

Cody