Complexidade de Kolmogorov com linguagens de descrição fracas

Podemos pensar na complexidade de Kolmogorov de uma string como o comprimento do programa mais curto P e inserir y de modo que x = P ( y ) . Normalmente, esses programas são extraídos de um conjunto completo de Turing (como P pode ser a descrição de uma máquina de Turing ou pode ser um programa em LISP ou C). Mesmo quando analisamos a complexidade de Kolmogorov com recursos, ainda observamos as máquinas de Turing, mas com alguns limites no tempo de execução ou no uso de espaço. Uma das conseqüências disso é que a complexidade de uma string é indecidível. Isso parece um recurso estranho.$x$$P$$y$$x = P(y)$$P$

O que acontece se usarmos modelos completos de computação não-Turing para definir a complexidade de Kolmogorov?

Se escolhermos um modelo restritivo o suficiente (digamos que nosso modelo possa implementar apenas a identidade), a complexidade de uma string se tornará decidível, embora também percam o teorema da invariância. É possível ter um modelo forte o suficiente para ter complexidade igual (até um deslocamento constante, ou mesmo um fator multiplicativo) ao modelo de Turing-complete, mas fraco o suficiente para permitir que a complexidade de uma sequência seja decidida? Existe um nome padrão para a complexidade de Kolmogorov com modelos completos de computação não-Turing? Onde eu poderia ler mais sobre isso?

$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))$

$x$