L'incomputabilité de la complexité de Kolmogorov découle-t-elle du théorème du point fixe de Lawvere?

17

De nombreux théorèmes et "paradoxes" - diagonalisation de Cantor, indécidabilité de la hachure, indécisibilité de la complexité de Kolmogorov, Gödel Incompleteness, Chaitin Incompleteness, Russell's paradox, etc. - ont tous essentiellement la même preuve par diagonalisation (notez que c'est plus spécifique que ce qu'ils peuvent tout cela peut être prouvé par la diagonalisation; il semble plutôt que tous ces théorèmes utilisent vraiment la même diagonalisation; pour plus de détails, voir, par exemple, Yanofsky , ou pour un compte rendu beaucoup plus bref et moins formalisé, ma réponse à cette question ).

Dans un commentaire sur la question susmentionnée, Sasho Nikolov a souligné que la plupart de ces cas étaient des cas particuliers du théorème du point fixe de Lawvere . S'ils étaient tous des cas spéciaux, alors ce serait un bon moyen de saisir l'idée ci-dessus: il y aurait vraiment un résultat avec une preuve (Lawvere) à partir de laquelle tout ce qui précède a suivi comme corollaires directs.

Maintenant, pour Gödel Incomplétude et indécidabilité du problème d'arrêt et de leurs amis, il est bien connu qu'ils découlent du théorème du point fixe de Lawvere (voir, par exemple, ici , ici ou Yanofsky ). Mais je ne vois pas immédiatement comment faire cela pour l'indécidabilité de la complexité de Kolmogorov, malgré le fait que la preuve sous-jacente est en quelque sorte "la même". Donc:

L'indécidabilité de la complexité de Kolmogorov est-elle un corollaire rapide - ne nécessitant aucune diagonalisation supplémentaire - du théorème du point fixe de Lawvere?

lo.logic computability ct.category-theory kolmogorov-complexity Joshua Grochow
la source
2
Je dois dire que tout ce que j'ai jamais su sur ce sujet, j'ai appris de ce billet de blog d'Andrej Bauer: math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem
Sasho Nikolov
1
@MaxNew: Soit une fonction calculable, calculé par quelque TM M . Soit M k le TM suivant: sur une entrée vide, il commence à parcourir les chaînes une par une jusqu'à ce qu'il trouve un x avec f ( x ) ≥ | x | > k et sortie x . Notez que | M k | ≤ log 2 ( k ) + c pour certains c en fonction uniquement de | M | . Alors pour tout k tel quefMMkxf(x)≥|x|>kx|Mk|≤log2⁡(k)+cc|M|k(n'importe quel k suffisamment grandfera l'affaire), soit il n'y a pas un tel x (auquel cas f ≠ C ) soit M k produit un certain x tel que f ( x ) ≥ | x | > k (par construction), mais le fait que M k produit x implique que C ( x ) ≤ | M k | < k , so fk>|Mk|kxf≠CMkxf(x)≥|x|>kMkxC(x)≤|Mk|<k . f(x)≠C(x)
Joshua Grochow du
2
@NealYoung: Similaire, mais ceux-ci ne répondent pas tout à fait à ma question. Pour réduire le problème de l'arrêt, il faut considérer HALT comme la «source» de non calculabilité, puis utiliser les réductions. Mais (par exemple) la preuve que j'ai donnée dans les commentaires ci-dessus montre que vous pouvez également prendre la complexité K comme «source de non calculabilité», mais par une preuve très similaire à celle de HALT. Peut-on réellement prouver que cette preuve similaire est la même dans un certain sens technique? (Dans ce cas, en montrant qu'ils sont tous des exemples du théorème de Lawvere, qui me semble plus fort que de nombreux types de réduction.) C'est ce que je recherche vraiment.
Joshua Grochow
1
@NealYoung: Oui, il généralise le théorème du point fixe de Roger. Mais si vous ne le considérez que comme le théorème de Roger, vous allez manquer le point; le fait est que Lawvere est suffisamment général pour saisir la stratégie de preuve de nombreuses preuves différentes, au-delà de celle de Roger. L'article de Yonofsky lié à la question est destiné à être une exposition "sans catégorie" du théorème de Lawvere, amicale pour les personnes pour lesquelles la théorie des catégories de Lawvere pourrait être intimidante.
Joshua Grochow
3
Voir aussi cstheory.stackexchange.com/a/2830
András Salamon

Réponses:

14

EDIT: Ajout de la mise en garde que le théorème à virgule fixe de Roger peut ne pas être un cas spécial de Lawvere.

Voici une preuve qui peut être "proche" ... Elle utilise le théorème de Roger à virgule fixe au lieu du théorème de Lawvere. (Voir la section des commentaires ci-dessous pour plus de détails.)

Soit la complexité de Kolmogorov de la chaîne xK(x)x .

lemme . K n'est pas calculable .

Preuve .

  1. Supposons pour contradiction que K soit calculable.

  2. Définissez comme la longueur d'encodage minimale de toute machine de Turing M avec L ( M ) = { x } . K′(x)ML(M)={x}

  3. Il existe une constante telle que | K ( x ) - K ′ ( x ) | ≤ c pour toutes les chaînes x .c|K(x)−K′(x)|≤cx

  4. Définir la fonction telle que f ( ⟨ M ⟩ ) = ⟨ M ' ⟩ où L ( M ' ) = { x } de telle sorte que x est la chaîne de minimum de telle sorte que K ( x ) > | ⟨ M ⟩ | + c . ff(⟨M⟩)=⟨M′⟩L(M′)={x}xK(x)>|⟨M⟩|+c

  5. Puisque est calculable, f l' est aussi .Kf

  6. Par le théorème du point fixe de Roger , a un point fixe, qui est, il existe une machine de Turing M 0 de telle sorte que L ( M 0 ) = L ( M ' 0 ) où ⟨ M ' 0 ⟩ = f ( ⟨ M 0 ⟩ ) .fM0L(M0)=L(M0′)⟨M0′⟩=f(⟨M0⟩)

  7. Par la définition de à la ligne 4, nous avons L ( M 0 ) = { x } tel que K ( x ) > | ⟨ M 0 ⟩ | + cfL(M0)={x}K(x)>|⟨M0⟩|+c .

  8. Les lignes 3 et 7 impliquent K′(x)>|⟨M0⟩|.

  9. Mais par la définition de à la ligne 2, K ′ ( x ) ≤ | ⟨ M 0 ⟩ | , contredisant la ligne 8.K′K′(x)≤|⟨M0⟩|

Neal Young
la source
4
As far as I know Roger's fixed-point theorem is not an instance of Lawvere's fixed-point theorem. It is a variant, though, because in the effective topos it reads as follows: if f:N⇉AN is a mutlivalued surjection then A has the fixed-point property. (Lawvere's theorem in the effective topos is: if f:B→AB is a surjection then A has the fixed-point property.)
Andrej Bauer
ff:N→→AN), and what is A? Or maybe suggest an appropriate tutorial?
Neal Young
4
Slides 45 and 46 in math.andrej.com/wp-content/uploads/2007/05/syncomp-mfps23.pdf (the good news is that now I have a definite plan and a deadline for writing up an extensive paper on synthetic computability).
Andrej Bauer