Complexidade de Kolmogorov com linguagens de descrição fracas

12

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.xPyx=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?

Artem Kaznatcheev
fonte
2
uma nota: tanto tempo limitado e espaço delimitado complexidades Kolmogorov são computáveis
Marzio De Biasi

Respostas:

5

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

D(s)snf(D(sn))>vff(n)vffexp(exp(exp(n)))

K(sn)>vff(n)s(n)nns(n)K(sn)nlog(n)K(sn)

fsK(s)f(D(s))

user396672
fonte
1

x

Kaveh
fonte