3
$\begingroup$

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.

Improve this question
$\endgroup$
16
  • $\begingroup$ For each $s_1$, is the sequence $s_1$, $s_2, \ldots$, supposed to be infinite? $\endgroup$
    – daniello
    Commented May 7, 2017 at 15:38
  • 1
    $\begingroup$ @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$ $\endgroup$
    – ARi
    Commented May 7, 2017 at 15:42
  • 2
    $\begingroup$ I suggest adding $\ldots s_\ell$ to the description of the sequence for clarity. $\endgroup$
    – daniello
    Commented May 7, 2017 at 15:47
  • 7
    $\begingroup$ 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. $\endgroup$
    – Mikhail Rudoy
    Commented May 7, 2017 at 21:36
  • 1
    $\begingroup$ @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. $\endgroup$
    – Marzio De Biasi
    Commented May 16, 2017 at 12:13

0

Reset to default

Your Answer

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