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.

Improve this question
$\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$ Commented 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$ Commented 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$ Commented Apr 23, 2017 at 19:32
  • 1
    $\begingroup$ That is correct. $\endgroup$ Commented Apr 23, 2017 at 19:40
  • $\begingroup$ @ChristianRemling I see your point now, please see the edits. $\endgroup$ Commented Apr 29, 2017 at 7:45

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.