Não podemos produzir a complexidade de Kolmogorov?

28

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 .U(T,x)TxTxxK(x)pU(p)=x

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 ?TxT(x)|x|xT(x)K(x)lim inf|x|T(x)=

As condições são necessárias, porque

(a) se T(x)|x|, seria fácil gerar um número que seja trivialmente diferente de K(x) porque é maior que |x|+cU ,

(b) se lim inf|x|T(x)<C é permitido, então podemos apenas gerar 0 (ou alguma outra constante) para quase todos os números, adivinhando "felizmente" o máximo (finitamente muitos números) que avaliam como 0 (para alguma outra constante) e produzem outra coisa. Podemos até garantir lim sup|x|T(x)= produzindo algo como 2logn para x=2n .

Observe também que nosso trabalho seria fácil se soubermos que T(x) não é adjetivo, mas pouco se sabe sobre isso, portanto a resposta pode depender de U , 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 .

domotorp
fonte
5
Depende da sua codificação, uma vez que, como mencionado no tópico sobre surjectivity de K você liga, que poderia ser o caso que apenas programas p de comprimento ainda são válidos. Portanto, para tornar sua pergunta não trivial, você precisa ter mais hipóteses sobre a codificação.
Denis
2
Para sua segunda pergunta: sim. Dado um número inteiro M , deixe [M] denotar a M ésima máquina de Turing. Uma função diagonalmente não recursiva (ou DNR) é uma função f:NN modo que, para todos os números inteiros M , [M](M)f(M) . (Ou seja, se [M] parar em M , então f(M)[M](M) e, caso contrário, f(M) podem ser arbitrários.) Estes foram estudados um pouco recentemente na computabilidade / computação comunidade aleatória. Google "na diagonal não recursiva" para encontrar documentos sobre isso.
Joshua Grochow
1
@ Denis: Eu acho que você está errado. De acordo com minha definição de máquinas de Turing universais, dada no primeiro parágrafo, todos os comprimentos podem ser programas válidos.
Domotorp
3
Algumas vezes atrás, pensei (em vão) em uma versão aparentemente mais simples: (des) provando que para x_0 grande o suficiente x0, K(x)|x|/2 para todos xx0 .
Marzio De Biasi
1
@ Ricky: Tudo bem, não tenho restrições quanto às codificações das máquinas de Turing, apenas aos programas, que você pode ler no primeiro parágrafo.
Domotorp

Respostas:

7

A questão pode ser reformulada como se liminf|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:

Seja T:{0,1}N uma função computável que satisfaça 0T(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, deixe n ser um aleatório b número de bits, ou seja, 0n<2b e K(n)b . Para todos os b existe bum 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)>bc1 , porque K(n)b e npode 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 alguns cZ , T(x)=K(x)+c infinitamente frequentemente. Pode-se dizer que não podemos produzir algo que não seja a complexidade de Kolmogorov!

Dan Brumleve
fonte
1
Bom, acho que isso deve funcionar. Obviamente, pode não haver strings com f(x)=b , então talvez você queira exigir f(x)b , certo?
domotorp
1
Ele precisa ser f(x)=b para que n seja computável a partir de xb,n . Então, acho que é preciso escolher b para que 2b+1 ou mais sejam mapeadas para ele. Presumivelmente, as suposições deveriam implicar que existem infinitamente muitos desses b (embora eu ainda não o veja no momento). (Até onde eu sei, as suposições não foram usadas de nenhuma outra maneira.)
Emil Jeřábek apoia Monica em
1
Sim, de fato isso é necessário. Mas a prova é fácil por contradição - se é sempre <2b se b>b0 , olhando para qualquer intervalo b0<bB , podemos concluir que pelo menos Bb0 cadeias B-b_0 são mapeadas para b0 , assim, infinitamente muitos, o que contradiz lim inf= .
9116 domotorp
O que Denis fala não se aplica à maneira como defini a universalidade na primeira linha da minha pergunta. Sua observação também é trivial, não faço idéia do motivo pelo qual tantas pessoas votaram positivamente em seu comentário. Mas, infelizmente, também resposta incorreta de Pedro recebeu tantas upvotes, eu estou perdendo a fé em este site ...
domotorp
Não importa como as TMs são codificadas, desde que meus critérios sobre a TM universal sejam satisfeitos, o comentário de Denis está incorreto. Se fosse declarado como uma observação sobre outro modelo, seria uma coisa diferente. De qualquer forma, em vez de deprimido sobre isso, vamos tentar ver se podemos reforçar a sua ideia ...
domotorp
3

Eu acho que o seguinte funciona. Vou usar C(x) para a complexidade de Kolmogorov

  • Dê a U um limite de tempo t (digamos, alguma função exponencial da duração do programa de entrada) e chame o resultado Ut . Se um programa exceder o limite de tempo, Ut entra em um loop infinito.
  • Seja Ct(x) o programa mais curto para x em t . Note que Ct é computável.
  • Seja T(x) retornado Ct(x)+1 , a menos que esse valor seja igual a |x|nesse caso, retorne 0. A menos que x seja a saída do programa vazio, nesse caso, retorne 1.
  • Como C(x)Ct(x) , T(x) sempre será diferente de C(x) . A lógica na etapa anterior cuida dos casos extremos.
  • Ut funciona como um código para todas as strings, portanto, limita o infinito inferior.
Pedro
fonte
alguns comentários, a teoria KC em uma interpretação alternativa (mas equivalente) afirma o seguinte: Quase todas as seqüências de caracteres já estão em sua representação ideal ( escrita em um determinado modelo), exceto muitas numerosas que podem ser transformadas em uma representação ideal (no mínimo) wrt para um determinado modelo de computação (ou TM). Nesse sentido, quase todos os programas produzem representações ótimas de strings, mas elas não são conhecidas (ou computáveis) a-priori #
Nikos M.
Por que você terá? T(x)|x|
Domotorp
@domotorp Tecnicamente, temos onde é a duração do programa de impressão mais curto. Obviamente, essa constante também existe para (e, de fato, a menos que o programa de impressão seja realmente lento, é a mesma constante). T(x)|x|+ccC(x)
Peter
Mas é isso que torna toda a questão interessante! Eu poderia ter perguntado qualquer função em vez de, por exemplo, , meu único objetivo era eliminar soluções semelhantes às suas. |x||x|/2+99
Domotorp
@domotrop Entendo, então você quer forçar a não ser um limite superior a . Isso é mais interessante ... #T(x)C(x)
Peter