Existe x tal que K (xx) <K (x), onde K é complacência de Kolmogorov.

Seja $K(x)$ denotado a complexidade Kolmogorov de uma string . Existe uma cadeia de caracteres tal que . (Aqui é a concatenação de consigo). Uma pergunta semelhante, mas diferente, foi feita aqui , mas o contra-exemplo dado na resposta a essa pergunta não funciona para essa. $x$ $K(xx)<K(x)$ $xx$ $x$

cc.complexity-theory kolmogorov-complexity Sune Jakobsen
fonte

Respostas:

Não sou especialista em complexidade de Kolmogorov, mas acho que esse x pode ser construído para cada função de complexidade K da seguinte maneira. Como 1, 11, 1111, 11111111,…, 1 ^{2 ⁿ} ,… é uma codificação de um número natural n , K (1 ^{2 ⁿ} ) não pode ser o (log n ). No entanto, quando n = 2 ^m , obviamente K (1 ^{2 ⁿ} ) = K (1 ^{2 ^{2 ^m}} ) = O (log m ) = O (log log n ). Portanto, a sequência K (1), K (11), K (1111), K (11111111),…, K (1 ^{2 ⁿ} ),… não pode aumentar levemente monotonicamente, o que significa que existe uma stringx na forma 1 ^{2 ⁿ} tal que K ( xx ) <K ( x ).

Tsuyoshi Ito
fonte

@Tsuyoshi, Existe uma string incompressível

tal que

x

$x$

K (x x) < K (x)

$K(xx)\lt K(x)$

Mohammad Al-Turkistany

Penso que

e K (1 ^ {2 ^ n}) = Ω (log n) se contradizem. O que ele quis dizer é: Se

então

K (1^{2^{2^{m}}}) = O (\log m)

$K(1^{2^{2^m}})=O(\log m)$

f (n) = o (\log n)

$f(n)=o(\log n)$

. Caso contrário, a prova parece boa.

K (1^{2^{n}}) \neq O (f (n))

$K(1^{2^n})\neq O(f(n))$

Sune Jakobsen

Isso parece funcionar. Na verdade, acho que isso fornece uma sequência infinita de tais strings. No entanto, estou entendendo mal algo, ou a declaração da regra da cadeia para a Complexidade Kolmogorov que aparece na wikipedia ( en.wikipedia.org/wiki/Chain_rule_for_Kolmogorov_complexity ) está incorreta. Inicialmente, pensei que a definição da wikipedia poderia não se aplicar aqui, pois é necessário saber onde X termina e Y começa, enquanto aqui parece não ser necessário, mas quando Y = X você pode adicioná-lo à descrição em O (1) dizendo "dividir no meio".

Abel Molina

@Une: A notação Ω (⋅) tem várias definições ligeiramente diferentes. “K (1 ^ 2 ^ n) = log (log n)” na minha resposta significa “limsup K (1 ^ 2 ^ n) / log n> 0” e não contradiz “K (1 ^ 2 ^ 2 ^ m) = O (log m). ”Editei a resposta para esclarecer esse ponto. Veja também Que definição de taxa de crescimento assintótica devemos ensinar?

Tsuyoshi Ito

@ turkistany and all: Note que é sempre verdade que K (xx)> K (x) -c para alguma constante, pensei que isso deveria ser apontado. Isso também significa que precisamos de uma definição muito precisa de incompressível, se quisermos estudar esta questão. Eu acho que a resposta é novamente sim, mas não tenho uma prova.

Domotorp

Sim. A complexidade de Kolomogorov na prática depende do seu modelo. Máquina de Turing, programa Java, programa C ++, ... se houver uma idiossincrasia no seu modelo que permita que isso aconteça em um conjunto finito de entradas, não há problema.

A melhor pergunta é quanto desse comportamento você consegue e ainda tem o modelo como universal.

Chad Brewbaker
fonte

Penso que uma pergunta melhor é: Esse x existe para todos os modelos? Não sei o que é um "modelo" formalmente, mas parece que a resposta do Tsuyoshis funciona para todas as linguagens de programação razoáveis.

Sune Jakobsen

Você pode atribuir

algo maior para

e ainda ter um modelo universal.

0

$0$

x x

$xx$

x

$x$

Kaveh

@Tsuyoshi:

Não entendi bem sua prova.

Suponha que escolhemos uma Máquina de Turing padrão como "linguagem de descrição", definindo como o número de estados da menor TM que começa com uma fita vazia e pára após imprimir o $K(s)$ sequência nela. $s$

Será que você provou que podemos construir um que "imprime" a corda na fita e é construído com menos estados de que "imprime" o string ? $TM_{ss}$ $ss = 1111...1 = 1^{2^{n+1}}$ $TM_{s}$ $s = 1^{2^n}$

Sua prova pode ser aplicada à complexidade de Kolmogorov nas TMs?

ESTÁ BEM! I GOT IT ... quando do pode ser "alimentado" com um novo "loop interno" (nós adicionamos alguns estados, mas podemos remover muitos estados que em são necessários para " contando " ) ... Obrigado! $n+1 = 2^{m}$ $TM_{ss}$ $TM_{s}$ $n$

(desculpe, mas não sei como postar isso como comentário)

Marzio De Biasi
fonte

Para escrever um comentário em um post feito por alguém que não seja você que não é uma resposta à sua pergunta, você precisa de ponto de reputação pelo menos 50.

Tsuyoshi Ito