A complexidade de Kolmogorov é uma função adjetiva?

Vamos fixar uma codificação de máquinas de Turing e uma máquina de Turing universal, U, que na entrada (T, x) produz qualquer saída de T na entrada x (possivelmente ambas funcionando para sempre). Defina a complexidade de Kolmogorov de x, K (x), como a duração do programa mais curto, p, de modo que U (p) = x.

Existe um N tal que para todo n> N exista um x com K (x) = n?

Observação. Se definirmos máquinas de Turing universais de uma maneira diferente, a resposta pode ser negativa. Por exemplo, considere um U que na entrada (T, x) simula T em x se o comprimento de (T, x) é divisível por 100 e, caso contrário, não faz nada. Pode-se modificar este exemplo de várias maneiras para obter contra-exemplos para diferentes definições de máquinas de Turing universais.

Apenas um comentário extenso, sem informações aprofundadas: talvez você possa trapacear na codificação de uma máquina de Turing e criar uma codificação artificial que leve a uma complexidade Kolmogorov excessiva:

• representa a máquina de Turing que gera 0 (1 estado TM);$0$$0$
• representa a máquina de Turing que gera p + 1 (o número representado pela cadeia binária p mais um); é simplesmente uma versão implícita "compactada" de uma MT decidível que gera p + 1 ;$0p$$p+1$$p$$p+1$
• representa amáquina de Turing p + 1- em uma enumeração padrão (a enumeração pode pular as TMs já incluídas com 0 e 0 p ).$1p$$p+1$$0$$0p$

A TM universal correspondente na entrada verifica qual é o valor de b , se for 0 , emite simplesmente x + 1 ; caso contrário, simula TM M x + 1 ( M 0 quando x é a sequência vazia); note que M x + 1 incorpora as entradas.$bx$$b$$0$$x+1$$M_{x+1}$$M_0$$x$$M_{x+1}$

Para todas as cadeias , 1 ≤ K ( x ) ≤ | x | + 1 ; e para todo n ≥ 1, existem 2 n cadeias de comprimento n, mas existem apenas 2 n - 1 - 1 programas de comprimento < n que podem ser representados usando a codificação 1 p ; e apenas 2 n - 1 programas de comprimento n que podem ser representados usando o 1 $x$$1 \leq K(x) \leq |x|+1$$n \geq 1$$2^{n}$$n$$2^{n-1}-1$$< n$$1p$$2^{n}-1$$n$$1p$codificação; portanto, pelo menos uma string de comprimento n não pode ser representada com um programa 1 p de comprimento ≤ n ; mas certamente pode ser representado com o programa 0 x ′ de comprimento n + 1 (não nos preocupamos se houver também um programa 1 p do mesmo comprimento n + 1 que o gera).$x'$$n$$1p$$\leq n$$0x'$$n+1$$1p$$n+1$

Podemos concluir que, para todos os , existe uma string x ′ , | x ′ | = n tal que K ( x ′ ) = n + 1 (então este K em particular é adjetivo).$n > 1$$x', |x'|=n$$K(x') = n+1$