Complexité de Kolmogorov avec des langages de description faibles

Nous pouvons considérer la complexité de Kolmogorov d'une chaîne $x$ comme la longueur du programme le plus court $P$ et saisir $y$ tel que $x = P(y)$ . Habituellement, ces programmes sont tirés d'un ensemble complet de Turing (comme $P$ pourrait être la description d'une machine de Turing, ou ce pourrait être un programme en LISP ou C). Même lorsque nous examinons la complexité de Kolmogorov liée aux ressources, nous examinons toujours les machines Turing, mais avec des limites sur leur durée d'exécution ou leur utilisation de l'espace. L'une des conséquences de cela est que la complexité d'une chaîne est indécidable. Cela semble être une fonction délicate.

Que se passe-t-il si nous utilisons des modèles de calcul complets non Turing pour définir la complexité de Kolmogorov?

Si nous choisissons un modèle suffisamment restrictif (disons que notre modèle ne peut implémenter que l'identité), alors la complexité d'une chaîne devient décidable, bien que nous perdions également le théorème d'invariance. Est-il possible d'avoir un modèle suffisamment fort pour avoir une complexité égale (jusqu'à un décalage constant, voire un facteur multiplicatif) au modèle Turing-complet, mais suffisamment faible pour permettre à la complexité d'une chaîne d'être décidable? Existe-t-il un nom standard pour la complexité de Kolmogorov avec des modèles de calcul complets non Turing? Où pourrais-je en savoir plus à ce sujet?

Supposons qu'il existe une complexité "décidable" différente de la complexité de Kolmogorov K ( s ) par décalage, par facteur ou, plus généralement, par toute fonction numérique monotone décidable f ( n ) telle que K ( s ) > f ( D ( s ) ) .$D(s)$$K(s)$$f(n)$$K(s) > f(D(s))$

Comme est décidable, il est possible de choisir (effectivement) une séquence de chaînes s n telle que f ( D ( s n ) ) > v f f ( n ) où v f f est une "croissance très très rapide" fonction "comme exp ( exp ( exp ( n ) ) ) .$D(s)$$s_n$$f(D(s_n))> \mathrm{vff}(n)$$\mathrm{vff}$$\exp(\exp(\exp(n)))$

Supposons que nous ayons , c'est-à-dire que la complexité de Kolmogorov de la chaîne s ( n ) croît rapidement avec n . Mais l'indice n identifie également la chaîne s ( n ) et, par conséquent, peut être traité comme la limite supérieure de K ( s n ) (avec un certain décalage const). Tout nombre n n'a besoin que de log ( n $K(s_n) > \mathrm{vff}(n)$$s(n)$$n$$n$$s(n)$$K(s_n)$$n$$\log(n)$bits pour le représenter, ce qui contredit la croissance rapide de la complexité de .$K(s_n)$

$f$$s$$K(s) \not> f(D(s))$

L'incalculabilité du KC général est une conséquence de l'indécidabilité du problème d'arrêt sur la classe de machines utilisées pour le KC. Si nous pouvons décider du problème d'arrêt sur la classe des machines, alors nous pouvons calculer le KC d'une chaîne donnée en fonction d'eux. Exécutez simplement toutes les paires de machines et d'entrées qui s'arrêtent jusqu'à la première qui génère , puis choisissez la plus courte.$x$