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.



Generating an arbitrarily long sequence with decreasing Kolmogorov complexity of terms
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.


