Equivalence des définitions de Kolmogorov-complexité

Question

Il y a plusieurs façons de définir le Kolmogorov-complexité, et généralement, toutes ces définitions qu'ils sont équivalents à un constante additive. C'est si $ K_1 $ et k_2 $ sont Kolmogorov fonctions de complexité (définies par différentes langues ou modèles), alors il existe un $ constant c $ tel que pour chaque chaîne $ x $, $ | K_1 (x) - K_2 (x ) |

Je suis intéressé par les définitions suivantes pour $ K $, sur des machines de Turing-

1. nombre d'états : Définir K_1 $ (x) $ pour être q nombre minimal de $ $ tel qu'un TM avec $ q états $ de $ x $ sur la chaîne vide
2. Durée du programme : Définir K_2 $ (x) $ pour être le plus court "programme" que les sorties $ x $. A savoir, fixer un moyen de coder en chaînes binaires mémoires de traduction; pour une machine $ M $ désignent son (binaire) codant pour que $ \ langle M \ rangle $. K_2 $ (x) = \ min | \ langle M \ rangle |. $ Où le minimum est sur tous les M $ '$ s $ que la sortie de x $ sur l'entrée vide

sont K_1 $ $ et K_2 $ équivalent $? Quelle est la relation entre eux, et que l'on saisit mieux le concept de complexité de Kolmogorov, si elles ne sont pas équivalents.

Ce qui surtout me dérange est le taux K_2 $ augmentation de $ avec $ x $, ce qui ne semble pas être super-linéaire (ou au moins linéaire avec C $ constante> 1 $ tel que K_2 $

Answer 1

Je me excuse à l'avance pour que je donne trop de détails, mais je suis sur le point de gens démentir.

À propos de $ K (x) =K '(x) + c $

Le fait que $ K_1 (x) =K_2 (x) + c $ provient généralement d'un interprète de la langue de description # 2 dans la description langue # 1 et pas d'une traduction des programmes de n ° 2 dans les programmes de # 1.

Par exemple $ K_ de la mathtt {C} (x) =K_ \ mathtt {Python} (x) + c_ \ mathtt {py2c} $ et vous obtenez cette inégalité aussi simple que ceci:

void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

Ensuite, votre constante $ c_ \ mathtt {py2c} $ sera quelque chose comme 528 $ + 490.240.688 $ lorsque 528 $ est le nombre de bits pour ce code et 490.240.688 $ bits $ est la taille l'interpréteur Python officiel écrit en C. Bien sûr il vous suffit d'interpréter ce qui est possible dans votre langage de description pour Python afin que vous puissiez faire mieux que 69 Mo: -)

Ce qui est important est que vous pouvez écrire votre programme Python linéaire dans votre code C. Par exemple, une langue où vous avez besoin de mettre « BANANE » entre chaque caractère est pas un programme très bonne description et la propriété est alors faux. (Mais si le langage de description vous autorise à des données d'écriture dans un fichier séparé ou dans un bloc, ce problème disparaît)

Pourquoi votre K_1 $ (x) = q $ est viciée

Le problème avec votre définition de $ K_1 $ est que vous devrez peut-être plus de $ q bits $ pour décrire une machine de Turing avec $ q états $ parce que vous avez besoin d'encoder des transitions.

Donc pas K_1 $ $ et k_2 $ sont probablement pas équivalents, mais c'est principalement K_1 $ $ faute de. Je pense que nous pouvons prouver que pour tout $ a> 0 $ il y a un $ C_A $ tel que $ K_1 (x) = a | x | + c_a $. Bien sûr, toute $ a <1 $ est suffisant pour réfuter le fait que $ K_1 $ n'est pas une fonction valide, car cela signifierait que nous pouvons encoder plus tous les 2 $ ^ n $ chaînes possibles de longueur $ n $ en $ de + c_a $ BITS.

Mais la taille est une limite très serré lors de la construction des machines de Turing. L'idée est que dans un bloc de $ b $ indique il y a $ b ^ {2b} $ façons de trouver des transitions pour chaque état et qui est mieux que l'habituel 2 $ ^ b $ façons dont vous pouvez remplir $ b bits $. Ensuite, vous pouvez stocker dans chaque bloc $ \ log_2 b $ bits d'information. (Pas 2 $ \ log_2 b $ parce que vous devez entrer et sortir le bloc d'une manière ou d'une autre)

Alors oui ... Avec des blocs de taille 2 $ ^ {1 / a} $ que vous pourriez probablement prouver K_1 $ (x) = a | x | + c_a $. Mais je l'ai déjà écrit beaucoup trop pourquoi le nombre d'états n'est pas une fonction de la complexité de Kolmogorov valide. Si vous me voulez élaborer, je le ferai.

Parlons maintenant de K_2 $ $

Les correspond linguistiques descriptives naïves à peu près à $ K_2 (x) = q \ cdot 2 \ cdot (\ log_2 q + 2) $ (soit $ \ log_2q $ pour chaque état suivant et des détails sur écriture et résiliation).

Comme vous semblez être, je suis convaincu que d'une manière meilleure / tricheur serait d'autoriser à coder « données » dans la machine de Turing, peut-être en ajoutant une balise binaire dans le langage de description qui dit que si un Etat est un état de données (qui vient écrit un peu et aller à l'étape suivante) ou si elle fait autre chose. De cette façon, vous pouvez stocker un bit de votre $ x $ en un peu de votre langage descriptif.

Toutefois, si vous gardez le même K_2 $ $ vous pouvez utiliser la même technique je dans la partie précédente pour sauver quelques bits, mais il me semble être coincé à K_2 $ (x) = a | x | \ log | x | + c $ (pour tout $ a> 0 $) .. peut-être moins de $ \ log | x | $, même, mais l'obtention d'O $ (| x |) $ semble difficile. (Et je pense qu'il devrait être $ | x | $, même pas O $ (| x |.) $)