Comparaison de la complexité de Kolmogorov des théories

Le théorème d'incomplétude de Chaitin dit qu'aucune théorie suffisamment forte de l'arithmétique ne peut prouver où est la complexité de Kolmogorov de la chaîne et est une constante suffisamment grande. est suffisamment grand s'il est supérieur à la taille en bits d'une machine de vérification d'épreuve (PCM). A PCM pour la théorie prend une chaîne codée comme un entier en entrée et délivre en sortie un 1 si la chaîne est une preuve valable dans la langue de . $K(s) > L$ $K(s)$ $s$ $L$ $L$ $T$ $T$

Supposons quepour la théorie est une limite supérieure de la complexité des . Considérons la hiérarchie des théories suivante: Que la théorie de base soit l' arithmétique de Robinson ( ). Augmentez avec des axiomes de plus en plus forts d'induction bornée polynomiale. Soit la théorie des théorèmes prouvables avec et l'un de ces axiomes d'induction bornés. Supposons que nous pouvons définir et en définissant les PCM pour chaque théorie. $L(T) > |PCM_T|$ $T$ $T$ $Q$ $Q$ $Q^*$ $Q$ $L(Q)$ $L({Q^*})$

Je veux envisager une machine de vérification d'épreuves améliorée (EPCM) pour . Cet EPCM prend une chaîne en entrée comme un ECM et possède une deuxième entrée qui définit le rang et le niveau d'une sous-théorie de . Si la chaîne d'entrée est une preuve valide dans l'EPCM passe ensuite par les étapes de la preuve pour déterminer le rang et le niveau d'induction les plus élevés utilisés. Cet EPCM écrit ensuite un 1 si la phrase d'entrée est une preuve valide dans la sous-théorie spécifiée de . $Q^*$ $Q^*$ $Q^*$ $Q^*$

Le vérificateur d'épreuves amélioré que je décris est-il réalisable? Dans l'affirmative, la taille de cet EPCM serait-elle une limite supérieure non seulement pour la complexité de $Q^*$ , mais également une limite supérieure pour la complexité de toute sous-théorie de $Q^*$ ?

Est-il raisonnable de dire qu'il existe une limite supérieure constante sur la complexité de et de toutes ses sous-théories? $Q^*$

Cette question a été inspirée par la preuve manquée de Nelson de l'incohérence de l'arithmétique. Je n'ai pas souligné cela plus tôt parce que certaines personnes trouvent cette preuve troublante. Ma motivation est de poser une question intéressante. CSTheory semble être le bon forum pour cette question. La complexité de et de toutes ses sous-théories est soit limitée par une constante soit illimitée. L'une ou l'autre réponse mène à plus de questions. $Q^*$

Si la complexité des sous-théories n'est pas bornée, nous pouvons poser des questions comme quelle est la sous-théorie la plus faible de plus complexe que ? Ou plus complexe que PA et ZFC? La réflexion sur cette question m'a déjà montré qu'il y a une limite sévère à ce qu'une théorie peut prouver sur la complexité de Kolmogorov des cordes. Si est cohérent, aucune de ses sous-théories ne peut prouver pour une chaîne. Cela signifie que même des sous-théories vraiment fortes ne peuvent pas prouver qu'il existe des chaînes plus complexes que certaines sous-théories beaucoup plus faibles où la théorie plus faible est plus complexe que . $Q^*$ $Q^*$ $Q^*$ $K(s) > L(Q^*)$ $Q^*$

lo.logic kolmogorov-complexity Russell Easterly
la source

C'est correct dans la mesure où il va, mais bien sûr, l'entrée supplémentaire ( , disons) requise pour vérifier la restriction sur le schéma d'induction est d'une complexité illimitée elle-même, il est donc quelque peu trompeur de suggérer que vous avez limité ces complexités uniformément .

n

$n$

La complexité supplémentaire serait . Si j'ai besoin de alors je n'aurais qu'à montrer .

l o g (n)

$log(n)$

n \leq L

$n \le L$

L > c + l o g (L)

$L > c+log(L)$

Russell Easterly

Votre notation me rappelle quelque peu de manière troublante cette tentative incorrecte de prouver l'incohérence de l'arithmétique. Pouvez-vous clarifier vos motivations?

cody

Salut Russell. Cela me semble assez intéressant. Si jamais vous souhaitez discuter, faites-le moi savoir. Bonne journée! :)

Michael Wehar

Oui, une telle MT peut être utilisée pour définir la complexité d'une théorie. Je demande s'il y a une limite sur la taille de cette MT lorsque nous avons plusieurs théories.

Russell Easterly

Réponses:

Je vais essayer de répondre à cette question et essayer de dissiper une certaine confusion quant à la forme exacte de la question.

$L$ $T$ $T$ $L(T)$ pour toute chaîne , alors si est une théorie cohérente plus forte que ( implique pour toute phrase arithmétique ) alors . L'argument est très simple: s'il existe tel que

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

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

s

$s$

T^{'}

$T'$

T

$T$

T ⊢ φ

$T\vdash\varphi$

T^{'} ⊢ φ

$T'\vdash\varphi$

φ

$\varphi$

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

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

s

$s$

puis

par hypothèse.

T ⊢ K (s) \geq L

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

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

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

Cependant, cela n'est vrai que si est la constante absolue de Chaitin. En particulier, si prouve , alors $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$

en intériorisant l'argument de Chaitin. Cependant , un béton pour lequel $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$

ne sera en général pas égal à $L(T)$ . En particulier, elle peut être beaucoup plus grande, généralement proportionnelle à la taille de la preuve de dans $\mathrm{Con}(T)$ $T'$ . Cela peut facilement être vu dans la preuve du théorème lui - même, qui repose fondamentalement sur la cohérence des . $T$

Ainsi, alors que peut prouver la cohérence du système avec une induction bornée, la longueur de ces preuves s'allonge à mesure que vous vous rapprochez de dans l'expressivité (une façon de comprendre les théorèmes d'incomplétude est que la longueur devient infinie lorsque vous atteignez , il n'a donc pas de preuve de cohérence finie dans lui-même). Ainsi , le même pour les différentes limites supérieures sur la interne s peut décrire pour chaque sous-théorie. $Q^*$ $Q^*$ $Q^*$ $Q^*$ $L(T)$ $Q^*$

Voici donc la réponse courte à votre question: est borné uniformément pour toutes les sous-théories de , mais lui-même ne peut pas montrer que cette borne est valable pour toutes ces sous-théories. C'était l'erreur cruciale que Nelson a commise (enterrée sous plusieurs couches de formalisme) et que Tao a soulignée ici . $L(T)$ $Q^*$ $Q^*$

cody
la source

PRA peut prouver

. La taille de cette preuve est-elle une borne supérieure de la complexité de

et de toutes ses sous-théories (en supposant un codage compatible des axiomes, des phrases, etc.)?

C o n (Q^{*})

$Con(Q^*)$

Q^{*}

$Q^*$

Russell Easterly le

L'ARP peut donner une limite uniforme pour

pour chacune des sous-théories. puisque

et pour toute sous-théorie

, il n'est donc pas difficile de montrer que la borne pour

fonctionne également pour

(dans 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

Par toute sous-théorie de

j'entendais bien entendu toute sous-théorie qui peut être prouvée comme telle dans PRA.

Q^{*}

$Q^*$

cody

Salut Cody, merci pour la réponse. J'espère que tout va bien. :)

Michael Wehar

Merci Mike! C'était une question amusante. Le fait que Nelson lui-même se soit trompé dans les détails suggère qu'il y a des pièges subtils en cours de route ...

cody