# A sequence wherein the Kolmogorov complexity of the terms does not increase

I am looking for an algorithm $A$ - which for any non-null input string $s_1$ produces a sequence $s_1, s_2...$ such that :

• It can be proved in some axiomtic system $S$ that: $\forall j> i; K(s_j) \ngtr K(s_i)$; K(s) being the Kolmogorov complexity of string $s$.

ie complexity of terms in the sequence does not increase.

• For any given $s_1 , \not\exists$ Algorithm B such that $|A| >|B|$ and given $m,n$: B can decide "$|s_m|>|s_n|$"

ie There does not exist any algorithm B with program length less than A which can decide, given any two indices, which one the terms at those indices is smaller.

• For each $s_1$, is the sequence $s_1$, $s_2, \ldots$, supposed to be infinite? – daniello May 7 '17 at 15:38
• @daniello An infinite sequence doesnt seem possible... since for the given $s_1$ There will be only finite no of descriptions with length not greater than the length of the shortest description of $s_1$ – ARi May 7 '17 at 15:42
• I suggest adding $\ldots s_\ell$ to the description of the sequence for clarity. – daniello May 7 '17 at 15:47
• Here's a silly answer. Let's say we formalize your problem in terms of Turing machines. Then the TM which immediately halts regardless of input (aka the smallest possible TM) is an $A$ satisfying your requirements. On input $s_1$, it outputs the list $s_1$ with just one element (and this list does not have increasing K-complexity). Also, no smaller TM can decide given two indices which $s_i$ is smaller simply because there is no smaller TM. – Mikhail Rudoy May 7 '17 at 21:36
• @ARi: claerly no; but in my example above I suppose that $|A| = K(z) + c_1$ ($c_1$ small, just enough to implement the write of $(,11)^z$). And then then existence of $|B| \leq |A| - c_2$ leads to a contraddiction; note that $c_1, c_2$ are independent of $z$ (and $K(z)$) that can be arbitrarily larger; but as in many "reasoning/proofs" about Kolmogorov complexity, you cannot get rid of those constants. – Marzio De Biasi May 16 '17 at 12:13