Estou procurando uma prova de que a complexidade de Kolmogorov é incontestável usando uma redução de outro problema incontestável. A prova comum é uma formalização do paradoxo de Berry, e não uma redução, mas deve haver uma prova reduzindo algo como o Problema da Parada ou o Problema da Correspondência de Post.
computability
reductions
kolmogorov-complexity
Krishna Chikkala
fonte
fonte
Esta foi uma pergunta divertida de se pensar. Conforme descrito na outra resposta e nos comentários abaixo, há uma redução de Turing do problema de Halting para computar a complexidade de Kolmogorov, mas notavelmente não existe uma redução de tantas, pelo menos para uma definição de 'computação da complexidade de Kolmogorov'.
Vamos definir formalmente o que estamos falando. Deixe denotar o idioma padrão de TM que parada quando é dada uma descrição de si mesmos como entrada. Vamos K O denotam { ⟨ x , k ⟩ | x tem Kolmogorov complexidade exatamente k } .HALT KO {⟨x,k⟩∣x has Kolmogorov complexity exactly k}
Suponha que por alguma redução de muitos. Seja f : { 0 , 1 } ∗ → { 0 , 1 } ∗ denotar a função que essa redução calcula. Considere a imagem de H A L T sob f , que eu denotarei f ( H A L T ) .HALT≤KO f:{0,1}∗→{0,1}∗ HALT f f(HALT)
Nota é composto por cordas da forma ⟨ x , k ⟩ onde x tem complexidade de Kolmogorov exactamente k . Eu afirmo que os ks que ocorrem em f ( H A L T ) são ilimitados, pois há apenas um número finito de cadeias com a complexidade de Kolmogorov exatamente k , e f ( H A L T ) é infinito.f(HALT) ⟨x,k⟩ x k k f(HALT) k f(HALT)
Como é recursivamente enumerável (também conhecido como Turing-reconhecível em alguns livros), segue-se que f ( H A L T ) é recursivamente enumerável. Combinado com o fato de que os k 's são ilimitada, podemos enumerar f ( H A L T ) até encontrarmos algum ⟨ x , k ⟩ com k tão grande como nós queremos; ou seja, não existe uma TM M que na entrada do K produz algum elemento ⟨ x , k ⟩HALT f(HALT) k f(HALT) ⟨x,k⟩ k M k .⟨x,k⟩∈f(HALT)
Escreva um novo TM que faça o seguinte: primeiro, calcule | M ′ | usando o teorema da recursão de Kleene. Consulta M com entrada | M ′ | + 1 para obter ⟨ x , | M ′ | + 1 ⟩ ∈ f ( H A G T ) . Saída x .M′ |M′| M |M′|+1 ⟨x,|M′|+1⟩∈f(HALT) x
Claramente, a saída de M ′ é uma string com complexidade de Kolmogorov, no máximo | M ′ | mas ⟨ x , | M ′ | + 1 ⟩ ∈ f ( H A G T ) o que é uma contradição.x M′ |M′| ⟨x,|M′|+1⟩∈f(HALT)
Eu acredito que você também pode substituir no problema "complexidade Kolmogorov exatamente " por "complexidade Kolmogorov pelo menos k " por pequenas alterações.k k
fonte