La preuve de la complexité de Kolmogorov n'est pas calculable à l'aide de réductions

9

Je cherche une preuve que la complexité de Kolmogorov n'est pas calculable en utilisant une réduction d'un autre problème non calculable. La preuve commune est une formalisation du paradoxe de Berry plutôt qu'une réduction, mais il devrait y avoir une preuve en réduisant quelque chose comme le problème de l'arrêt, ou le problème de correspondance de Post.

Krishna Chikkala
la source

Réponses:

11

Vous pouvez trouver deux preuves différentes dans:

Gregory J. Chaitin, Asat Arslanov, Cristian Calude: La complexité de la taille du programme calcule le problème de l'arrêt. Bulletin de l'EATCS 57 (1995)

Dans Li, Ming, Vitányi, Paul MB; Une introduction à la complexité de Kolmogorov et à ses applications, il est présenté comme un exercice (avec un indice sur la façon de le résoudre qui est attribué à P. Gács par W. Gasarch dans une communication personnelle le 13 février 1992).

** J'ai décidé d'en publier une version étendue sur mon blog .

Marzio De Biasi
la source
1
De plus, la preuve de Chaitin (dans ce lien) montre que les requêtes oracle peuvent être faites en parallèle.
Ces preuves sont-elles vraiment des réductions tournantes (une à une (ou) une à plusieurs)? Je suis confus !! s'il vous plaît aidez-moi
Krishna Chikkala
@ KrishnaChikkala: le premier est sûrement une réduction de Turing . Je ne l'ai pas trouvé si clair, j'ai donc décidé d'en publier une version étendue sur mon blog . Si vous voulez y jeter un œil (et dites-moi par email si vous pensez qu'il peut être amélioré). Notez également que les réductions de Turing sont différentes des réductions de plusieurs (qui sont des réductions "plus fortes"); en effet, la réponse de Joe Bebel prouve qu'une telle réduction ne peut exister.
Marzio De Biasi
7

C'était une question amusante à laquelle réfléchir. Comme décrit dans l'autre réponse et les commentaires ci-dessous, il y a une réduction de Turing du problème de Halting au calcul de la complexité de Kolmogorov, mais notamment il n'y a pas une telle réduction de plusieurs, au moins pour une définition du `` calcul de la complexité de Kolmogorov ''.

Définissons formellement ce dont nous parlons. Soit le langage standard des MT qui s'arrêtent lorsqu'on leur donne une description d'eux-mêmes en entrée. Laissez K O représentent chacun { x , k | x  a la complexité de Kolmogorov exactement  k } .HALTKO{x,kx has Kolmogorov complexity exactly k}

HALTKOf:{0,1}{0,1}HALTff(HALT)

f(HALT)x,kxkkf(HALT)kf(HALT)

HALTf(HALT)kf(HALT)x,kkMkx,kf(HALT)

M|M|M|M|+1x,|M|+1f(HALT)x

xM|M|x,|M|+1f(HALT)

kk

Joe Bebel
la source
1
Mais qu'en est-il d'une réduction de Turing?
Sasho Nikolov
RSx,kKOHALTRKOx,kKOSkRx,k
R
3
Quelques endroits affirment que la complexité de Kolmogorov équivaut à Turing au problème de l'arrêt, par exemple les notes de Miltersen daimi.au.dk/~bromille/DC05/Kolmogorov.pdf . Si c'est vrai, il doit y avoir une réduction de Turing. Au fait, une réduction de Turing de la complexité de Kolmogorov au problème de l'arrêt est facile et donne une preuve différente que l'arrêt est indécidable.
Sasho Nikolov
HALTTKOHALTTKO