Vamos fixar uma codificação sem prefixo de máquinas de Turing e uma máquina de Turing universal que na entrada (codificada como o código sem prefixo de seguido de ) produza o que produz na entrada (possivelmente ambos correndo para sempre). Defina a complexidade de Kolmogorov de , , como a duração do programa mais curto modo que .
Existe uma máquina de Turing tal que para cada entrada ela produza um número inteiroque é diferente da complexidade de Kolmogorov de , isto é, mas ?
As condições são necessárias, porque
(a) se , seria fácil gerar um número que seja trivialmente diferente de porque é maior que ,
(b) se é permitido, então podemos apenas gerar (ou alguma outra constante) para quase todos os números, adivinhando "felizmente" o máximo (finitamente muitos números) que avaliam como (para alguma outra constante) e produzem outra coisa. Podemos até garantir produzindo algo como para .
Observe também que nosso trabalho seria fácil se soubermos que não é adjetivo, mas pouco se sabe sobre isso, portanto a resposta pode depender de , embora eu duvide que sim.
Eu sei que as relações são muito estudadas em geral, mas
Alguém já fez uma pergunta semelhante em que nosso objetivo é fornecer um algoritmo que não produza algum parâmetro?
Minha motivação é esse problema http://arxiv.org/abs/1302.1109 .
fonte
Respostas:
A questão pode ser reformulada como seliminf|x|→∞|T(x)−K(x)|=0 , e como Denis aponta nos comentários isso é falso para algumas codificações. Aqui está uma declaração mais fraca e uma tentativa de prova dela que não depende de nenhum detalhe da codificação, mas assumirei uma linguagem binária para simplificar:
SejaT:{0,1}∗→N uma função computável que satisfaça 0≤T(x)≤|x| e liminf|x|→∞T(x)=∞ . Então liminf|x|→∞|T(x)−K(x)|<∞ . Informalmente, se houver um alvo em torno da complexidade Kolmogorov de cada string que cresça sem limites, nenhuma função computável poderá evitar atingi-lo.
Para ver esta, deixen ser um aleatório b número de bits, ou seja, 0≤n<2b e K(n)≥b . Para todos os b existe b um n aleatório n . De referir ainda que há um número infinito de valores de b para que |{T(x)=b}|≥2b , esta decorre das condições colocados em T . Agora seja x a nth menor string, de forma que T(x)=b . É evidente que existe uma constante c1 tal que K(x)>b−c1 , porque K(n)≥b e n pode ser calculado a partir de x . E existe uma constante c2 tal que K(x)<b+c2 , porque K(n) também é delimitado por cima apenas por uma constante maior que b , e x pode ser calculado a partir de n . Então |K(x)−T(x)|<c1+c2 , e temos um número infinito de opções para b (aquelas com uma pré-imagem de cardinalidade de pelo menos 2b ), produzindo um número infinito de valores para x , então terminamos.
Uma implicação é que, para algunsc∈Z , T(x)=K(x)+c infinitamente frequentemente. Pode-se dizer que não podemos produzir algo que não seja a complexidade de Kolmogorov!
fonte
Eu acho que o seguinte funciona. Vou usarC(x) para a complexidade de Kolmogorov
fonte