<p>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 :</p>

<blockquote>
  <ul>
  <li><p>It can be proved in some axiomtic system $S$ that:           $\forall j&gt; i; K(s_j) \ngtr K(s_i)$;                                                        K(s) being the Kolmogorov complexity of string
  $s$. </p>
  
  <p>ie <strong>complexity of terms in the sequence does not increase.</strong></p></li>
  <li><p>For any given $ s_1 , \not\exists $ Algorithm B  such that $ |A| &gt;|B| $ and given $m,n$: B can decide "$|s_m|&gt;|s_n|$" </p>
  
  <p>ie <strong>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</strong>.</p></li>
  </ul>
</blockquote>

CC BY-SA 3.0
2017-05-07T15:38:22.537Z
For each $s_1$, is the sequence $s_1$, $s_2, \ldots$, supposed to be infinite?
daniello
CC BY-SA 3.0
2017-05-07T15:42:35.597Z
@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
CC BY-SA 3.0
2017-05-07T15:47:19.707Z
I suggest adding $\ldots s_\ell$ to the description of the sequence for clarity.
daniello
CC BY-SA 3.0
2017-05-07T21:36:45.127Z
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
CC BY-SA 3.0
2017-05-08T13:34:39.843Z
@MikhailRudoy Of course, but if I were  to be pedantic, Id say that the constraints stated; presuppose atleast a two element list.
ARi
CC BY-SA 3.0
2017-05-08T17:57:46.970Z
FWIW there is an $A$ that works for all but *finitely many* $s_1$.  Given $s_1$, let $A$ output the sequence $s_1, s_1, \ldots, s_1, \epsilon, \epsilon, \ldots$ with $s_1$ copies of $s_1$ (here $\epsilon$ is, say, the empty string, and we interpret $s_1$ as a positive integer).  Then the decision problem that $B$ must solve for $s_1$ is distinct from the decision problem that $B$ must solve for any $s_1' \ne s_1$. There are only finitely many TM's with size less than $A$, so only finitely many $s_1$'s have the $B$ that you don't want to exist for $s_1$.
Neal Young
CC BY-SA 3.0
2017-05-08T18:33:55.140Z
For any $A$ which outputs $\phi(s_1)$ copies of $s_1$   |$A$|>|$\phi$|
ARi
CC BY-SA 3.0
2017-05-08T18:37:08.617Z
Hence we can have |$A$>|$B$|>|$\phi$|
ARi
CC BY-SA 3.0
2017-05-08T19:00:56.723Z
Okay, I think you need to state your problem more carefully.  As it stands, the answer is certainly no.  Take $s_1$ to be the string of minimum $K$-complexity.  Then the decision problem for that $s_1$ is trivial, and can be answered by $B$ with only one state (a reject state).  So $A$ would have to be at most the size of this $B$.  In standard TM encoding schemes, this will mean $A$ has to have only one state, so can't do what you ask.
Neal Young
CC BY-SA 3.0
2017-05-08T19:10:21.270Z
Lets consider this. A chosen description language where c is the length of  shortest program whih outputs a string. if there a k progrms of this length which do output k different strings and if $s_1$ is indeed one of those strings the sequence will be confined to thses strings only and depending upon k these strings may not be of the same length. @NealYoung
ARi
CC BY-SA 3.0
2017-05-08T19:12:46.203Z
and even other wise we can state the decision problem as $s_m <,s_n$ without changing the problem much. ie  the k strings need only be different while being of the same length.
ARi
CC BY-SA 3.0
2017-05-11T12:32:55.980Z
It is not clear to me what is the exact input of the *decision* algorithm $B$ ?  ($s_1$?, $s_1, s_2, ...$?, $A$?, $m,n$?) ? How can it calculate and decide $|s_m|$, $|s_n|$ if it is not feeded with $A$ itself ? And it is not clear what you mean with $A$ on input $s_1$ "produces a sequence" $s_1,s_2,...$: do you mean write $s_2, s_3,...$ on the tape? Should it halt? What is the required length of the $s_i$ sequence?
Marzio De Biasi
CC BY-SA 3.0
2017-05-11T14:30:06.813Z
@MarzioDeBiasi 1. $A(s_1) = s_1,s_2.....$ 2. I make no suppositions regarding the length of the sequence or weather it is finite.3.  For a given $A$ and $s_1$ there **does not exist any** $B$ with program length less than $A$ such that $\forall |s_m|>|s_n|;B(m,n) =1$ and 0 otherwise. Is this (esp the 3rd pt) OK.
ARi
CC BY-SA 3.0
2017-05-11T15:25:00.940Z
It surely exists an algorithm $A$ that leaves $s_1$ untouched and appends a sequence of $(,11)^z$ to it where $z$ is an incompressible (binary) string and then continues appending $,0$ forever ($s_1,11,11,...,11,0,0,...$). Clearly if such $B$ exists and is smaller enough than $A$  then we can build a program $P$ that is smaller than $K(z)$ and simulates $B$ on $(2,3),(2,4),...,$; as soon as its value switches from $0$ to $1$ (at $(2,z+2)$) it outputs $z$ ... in other words we have a more succinct representation of the uncompressible $z$. Note that KC constants should be taken into account.
Marzio De Biasi
CC BY-SA 3.0
2017-05-16T11:22:00.867Z
@MarzioDeBiasi   Can  a  program $P$ can have any  knowledge of string  $z$ if |$P$ |< $K(z)$ ?
ARi
CC BY-SA 3.0
2017-05-16T12:13:30.730Z
@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
<ds.algorithms><reference-request><computability><kolmogorov-complexity>
A sequence wherein the Kolmogorov complexity of the terms does not increase
ARi
# A sequence wherein the Kolmogorov complexity of the terms does not increase

(Asked by: username_0 on 2017-05-07)

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**.

**Tags:** ds.algorithms, reference-request, computability, kolmogorov-complexity
> **Comments:**
> **username_1**: For each $s_1$, is the sequence $s_1$, $s_2, \ldots$, supposed to be infinite?  
> **username_0**: @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$  
> **username_1**: I suggest adding $\ldots s_\ell$ to the description of the sequence for clarity.  
> **username_2**: 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.  
> **username_0**: @MikhailRudoy Of course, but if I were  to be pedantic, Id say that the constraints stated; presuppose atleast a two element list.  
> **username_3**: FWIW there is an $A$ that works for all but *finitely many* $s_1$.  Given $s_1$, let $A$ output the sequence $s_1, s_1, \ldots, s_1, \epsilon, \epsilon, \ldots$ with $s_1$ copies of $s_1$ (here $\epsilon$ is, say, the empty string, and we interpret $s_1$ as a positive integer).  Then the decision problem that $B$ must solve for $s_1$ is distinct from the decision problem that $B$ must solve for any $s_1' \ne s_1$. There are only finitely many TM's with size less than $A$, so only finitely many $s_1$'s have the $B$ that you don't want to exist for $s_1$.  
> **username_0**: For any $A$ which outputs $\phi(s_1)$ copies of $s_1$   |$A$|>|$\phi$|  
> **username_0**: Hence we can have |$A$>|$B$|>|$\phi$|  
> **username_3**: Okay, I think you need to state your problem more carefully.  As it stands, the answer is certainly no.  Take $s_1$ to be the string of minimum $K$-complexity.  Then the decision problem for that $s_1$ is trivial, and can be answered by $B$ with only one state (a reject state).  So $A$ would have to be at most the size of this $B$.  In standard TM encoding schemes, this will mean $A$ has to have only one state, so can't do what you ask.  
> **username_0**: Lets consider this. A chosen description language where c is the length of  shortest program whih outputs a string. if there a k progrms of this length which do output k different strings and if $s_1$ is indeed one of those strings the sequence will be confined to thses strings only and depending upon k these strings may not be of the same length. @NealYoung  
> **username_0**: and even other wise we can state the decision problem as $s_m <,s_n$ without changing the problem much. ie  the k strings need only be different while being of the same length.  
> **username_4**: It is not clear to me what is the exact input of the *decision* algorithm $B$ ?  ($s_1$?, $s_1, s_2, ...$?, $A$?, $m,n$?) ? How can it calculate and decide $|s_m|$, $|s_n|$ if it is not feeded with $A$ itself ? And it is not clear what you mean with $A$ on input $s_1$ "produces a sequence" $s_1,s_2,...$: do you mean write $s_2, s_3,...$ on the tape? Should it halt? What is the required length of the $s_i$ sequence?  
> **username_0**: @MarzioDeBiasi 1. $A(s_1) = s_1,s_2.....$ 2. I make no suppositions regarding the length of the sequence or weather it is finite.3.  For a given $A$ and $s_1$ there **does not exist any** $B$ with program length less than $A$ such that $\forall |s_m|>|s_n|;B(m,n) =1$ and 0 otherwise. Is this (esp the 3rd pt) OK.  
> **username_4**: It surely exists an algorithm $A$ that leaves $s_1$ untouched and appends a sequence of $(,11)^z$ to it where $z$ is an incompressible (binary) string and then continues appending $,0$ forever ($s_1,11,11,...,11,0,0,...$). Clearly if such $B$ exists and is smaller enough than $A$  then we can build a program $P$ that is smaller than $K(z)$ and simulates $B$ on $(2,3),(2,4),...,$; as soon as its value switches from $0$ to $1$ (at $(2,z+2)$) it outputs $z$ ... in other words we have a more succinct representation of the uncompressible $z$. Note that KC constants should be taken into account.  
> **username_0**: @MarzioDeBiasi   Can  a  program $P$ can have any  knowledge of string  $z$ if |$P$ |< $K(z)$ ?  
> **username_4**: @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.  

---

## 0 answers

