Complejidad de Kolmogorov con lenguajes de descripción débiles

Podemos pensar en la complejidad de Kolmogorov de una cadena $x$ como la longitud del programa más corto $P$y la entrada $y$ tal que $x = P(y)$ . Por lo general, estos programas se extraen de un conjunto completo de Turing (como $P$ podría ser la descripción de una máquina de Turing, o podría ser un programa en LISP o C). Incluso cuando miramos la complejidad de Kolmogorov limitada por los recursos, todavía miramos las máquinas Turing pero con algunos límites en su tiempo de ejecución o uso del espacio. Una de las consecuencias de esto es que la complejidad de una cadena es indecidible. Esto parece una característica incómoda.

¿Qué sucede si utilizamos modelos completos de cómputo que no son de Turing para definir la complejidad de Kolmogorov?

Si elegimos un modelo lo suficientemente restrictivo (digamos que nuestro modelo solo puede implementar la identidad), entonces la complejidad de una cadena se vuelve decidible, aunque también perdemos el teorema de la invariancia. ¿Es posible tener un modelo lo suficientemente fuerte como para tener una complejidad igual (hasta un desplazamiento constante, o incluso un factor multiplicativo) al modelo completo de Turing, pero lo suficientemente débil como para permitir que la complejidad de una cadena sea decidible? ¿Existe un nombre estándar para la complejidad de Kolmogorov con modelos completos de cómputo que no sean de Turing? ¿Dónde podría leer más sobre esto?

$D(s)$$K(s)$$f(n)$$K(s) > f(D(s))$

$D(s)$$s_n$$f(D(s_n))> \mathrm{vff}(n)$$\mathrm{vff}$$\exp(\exp(\exp(n)))$

$K(s_n) > \mathrm{vff}(n)$$s(n)$$n$$n$$s(n)$$K(s_n)$$n$$\log(n)$$K(s_n)$

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

La falta de cálculo de KC general es una consecuencia de la indecidibilidad del problema de detención sobre la clase de máquinas utilizadas para KC. Si podemos decidir el problema de detención sobre la clase de las máquinas, entonces podemos calcular el KC de una cadena dada de acuerdo con ellas. Simplemente ejecute todos los pares de máquina y entrada que se detienen hasta el primero que genera , y luego elija el más corto.$x$