2
$\begingroup$

Is there an algorithm which, given a string $s$, generates a sequence of $|s|$ strings, such that it can be proven in some axiomatic system $S$, that the Kolmogorov complexity of each successive term is smaller than the preceeding one?

We further impose a constraint that the terms of the strings themselves, do not decrease in length monotonically.

$\endgroup$
5
  • 4
    $\begingroup$ That would allow you to produce an $x_n$ with $K(x_n)>n$, say, on input $n$, which only needs $\log n$ bits to encode, and this plainly contradicts the definition of Kolmogorov complexity. $\endgroup$ Apr 23, 2017 at 19:13
  • $\begingroup$ Such a sequence should in fact have (provably) $K(x_n) <n + c $ for some additive const c based upon the choice of description language and the algorithm. Am I missing something? $\endgroup$
    – ARi
    Apr 23, 2017 at 19:30
  • $\begingroup$ Given $n$, I compute the $n$ numbers your hypothetical algorithm produces and then take the one with the largest complexity and call it $x_n$. $\endgroup$ Apr 23, 2017 at 19:32
  • 1
    $\begingroup$ That is correct. $\endgroup$ Apr 23, 2017 at 19:40
  • $\begingroup$ @ChristianRemling I see your point now, please see the edits. $\endgroup$
    – ARi
    Apr 29, 2017 at 7:45

1 Answer 1

1
$\begingroup$

Suppose there is such an algorithm.

Let $x_n$ be the first string outputted on input $$s=00\cdots 0=0^n.$$ Then $x_n$ has complexity at most $\log_2 n+C$ since I just described it in terms of $n$. On the other hand, the complexity is at least $n$ by assumption...

which is a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.