3
$\begingroup$

A typical $B$ is difficult to define precisely. Intuitively, it is the sort of bitstring that will be generated most of the time by randomly drawing 0s and 1s. However, the concept can be clarified by examining properties. A property $p$ applies to typical $B$s if the proportion of $B$s having that property is greater than or equal to 0.5, \begin{align*} \frac{|\{B: p(B)\}|}{|\{B\}|} \geq 0.5. \end{align*}

For instance, a typical $B$ has the property that $K(B) = \ell(B)$. In other words, a typical $B$ is not compressible.

Is the minimal Kolomgorov structure function (MKSS) a typical bitstring in some TM encoding? In other words, is there some TM encoding such that a bitstring generated by randomly drawing 0s and 1s likely to be a MKSS?

I think the answer is no, because incompressible bitstrings do not have a nontrivial MKSS, and most bitstrings are incompressible.

$\endgroup$
  • 2
    $\begingroup$ The minimal KSS is not defined in the Wikipedia entry you linked to. Do you have in mind the same definition you have in your previous post? And by saying a typical string has a property, do you again mean "with probability $1-o(1)$, as $n\rightarrow\infty$, a random string of length $n$ has the property"? $\endgroup$ – Neal Young Jul 11 '18 at 12:46
  • $\begingroup$ There's a technical problem in the def'n of typical and minimal in your previous post that you'll need to clear up to get an answer. Let $p_n$ be the probability that a random $n$-bit string $B$ has $|B| = K(B)$. You say there (and need here) that $p_n\rightarrow 1$ for large $n$. But it's false. For any encoded TM $P$, let $P'$ be obtained by adding a useless state to $P$, so $P'$ does not have minimal description length and $|P'| = |P|+c$ for constant $c$. So $1-p_{n+c} \ge p_n/c'$ for constant $c'$. So it cannot be that $p_n\rightarrow 1$... $\endgroup$ – Neal Young Jul 11 '18 at 13:06
  • $\begingroup$ @NealYoung Yes, I have in mind the definition here: en.wikipedia.org/wiki/… $\endgroup$ – yters Jul 11 '18 at 14:08
  • $\begingroup$ @NealYoung I'm confused by your comment. First you mention compressibility, then you mention minimal description length. It sounds like you are saying a typical bitstring is not guaranteed to have a minimal description length, which I believe is consistent with what I am saying here. However, I think you are making the same sort of argument as in the previous post that the typical is not incompressible, by taking a long compressible bitstring and adding random stuff to it. So, I probably need to change my definition of typicality to be $p_n > 0.5$. $\endgroup$ – yters Jul 11 '18 at 14:11
  • 1
    $\begingroup$ Yeah I am saying that, by the definitions in the previous post, it is not the case that a typical string is incompressible. And any MKSS must be (essentially) incompressible, so it follows that it cannot be that a typical string is an MKSS. I added an answer below with a more detailed argument. $\endgroup$ – Neal Young Jul 11 '18 at 14:40
2
$\begingroup$

Lemma 1 below shows that with a standard TM encoding, the fraction of strings that are MKSSs is bounded away from both 0 and 1. This answered a question posed in the original post.

Lemma 2 shows that there is a (non-standard) encoding in which almost all strings are MKSSs. This answers the question in the current post affirmatively.

Lemma 3 shows that there is a (non-standard) encoding in which almost no strings are MKSSs.


Let $\mu(n)$ be the probability that a random string of length $n$ or less is a minimal Kolmogorov structure function, as defined in your previous post.

Lemma 1. For any conventional TM encoding scheme, $$0 < \liminf_{n\rightarrow\infty} \mu(n) < 1$$

Proof. First we show that $\liminf_{n\rightarrow\infty} \mu(n) < 1$. For any string $B$, let $P^*_B$ be an MKSS for $B$. Define $P'_B$ to be the TM obtained from $P^*_B$ by adding a useless state. Then $|P'_B| \le |P^*_B|+c$ for some fixed constant $c$, and $P'_B$ is not an MKSS. It follows that, for every $n$, for every string of size at most $n$ that is an MKSS, there is a string of size at most $n+c$ that is not an MKSS. Hence, among the strings of length at most $n+c$, the number that are not an MKSS is at least the number of strings of length at most $n$ that are an MKSS. It follows that $1-\mu(n+c) \ge \mu(n)/c'$ for $c'\approx 2^c$. It follows that $\liminf_{n\rightarrow\infty} \mu(n) \le 1-1/(c'+1) < 1$.

Next we show that $\liminf_{n\rightarrow\infty} \mu(n) > 0$. For any string $B$, we have that $P^*_B$ is an MKSS, and $$|P^*_B| \le K(B) \le |B| + c_1$$ for some fixed constant $c_1$. So, for every $n$, the number of strings of length at most $n+c_1$ that are an MKSS is at least the number of strings of length at most $n$. It follows that $\mu(n+c_1) \ge 1/c_2$ where $c_2\approx 2^{c_2}$. It follows that $\liminf_{n\rightarrow\infty} \mu(n) \ge 1/c_2 > 0$. $~~\Box$


Next we show that using non-standard TM encoding schemes we can make almost all strings MKSSs. Fix arbitrarily large constant $k\ge 0$. Given a binary string $B$, if $B=1^kM$ ($k$ ones followed by some string $M$) then $B$ encodes the TM whose standard encoding is $M$. Otherwise, $B$ encodes a TM that outputs $B$. (This is a TM encoding scheme in the sense that there is a computable function mapping standard encodings to equivalent non-standard encodings, and vice versa.)

Lemma 2. For this TM encoding scheme, for any $n$, if $B$ is a random string of length at most $n$, then $B$ is an MKSS with probability at least $1-O(1/2^k)$.

Proof. Let $K'(B)$ and $P'_B$ denote the Kolmogorov complexity and MKSS of $B$ with respect to this non-standard TM encoding scheme. Let $K(B)$ denote the Kolmogorov complexity of $B$ with respect to the standard TM encoding scheme. Say that a string $B$ is good if $B$ isn't of the form $1^k M$ for some $M$, and $K(B) \ge |B|-k$.

Consider any good string $B$. Since $B$ isn't of the form $1^kM$, one (non-standard) encoding of a TM that outputs $B$ is $B$ itself. Further, any other encoding, say $P$ (with this encoding scheme), of a TM that outputs $B$ must be of the form $1^k M$, where $M$ is the standard encoding of a TM that outputs $B$. Any such encoding $P$ has length at least $K(B)+k \ge |B|$. Hence, $K'(B) = |B|$.

$B$ has an encoding (namely $B$) of size $K'(B)$ that outputs a set of size 1 containing $B$, so the MKSS $P'_B$ for $B$ has size $|P'_B| \le |B|$.

Now, fix any $n$, and consider any length-$n$ good string $B$ such that $B$ is not an MKSS. Hence, $|P'_B| < |B|=n$ and $P'_B = 1^k M$ for some standard encoding $M$ such that, on input $n$, $M$ outputs a set $S_B$ containing $B$ such that $$k+|M| +\log|S_B| = |P'_B| + \log |S_B| \le K'(B) = |B| = n.$$ It follows that $|M|+\log|S_B| \le n - k$.

Now, composing $M$ and the index of $B$ in $S_B$, there exists a TM with standard encoding $M'$ that, on input $n$, outputs $B$, and such that $$|M'| = |M| + \log |S_B| + O(1) \le n-k+O(1).$$

Since $M'$ uniquely determines $B$ (among strings of length $n$), it follows that there are at most $2^{n-k+O(1)}$ good length-$n$ strings that are not MKSS's.

Now, among all $2^n$ length-$n$ strings $B$:

  1. at most $2^{n-k}$ have $K(B) \le n-k$ (by the standard counting argument), and

  2. at most $2^{n-k}$ have the form $1^k M$ for some $M$.

So, at least $2^n - 2^{n-k + 1}$ are good, and, among those,

  1. at most $2^{n-k+O(1)}$ are not MKSS's (as shown above).

It follows that, for every $n$, among all $2^n$ length-$n$ strings, at least $$2^n - O(2^{n-k+O(1)}) = 2^n(1-O(1/2^k))$$ are MKSS's. Hence, among all strings of length at most $n$, at least a fraction $1-O(1/2^k)$ are MKSS's. $~~\Box$


Just for fun, here is another non-standard encoding scheme in which almost all strings are not MKSS's. Use the encoding scheme from Lemma 2, but augment it to make the empty string encode a TM that, on input $n$, outputs all strings of length $n$.

Lemma 3. With this modified encoding scheme, the probability that a random string of length $n$ or less is an MKSS is $O(1/2^k)$.

Proof. Following the proof above, among the strings of length $n$ or less, the fraction that are good is at least $1-O(1/2^k)$. To finish we show that no good string is an MKSS. For any good string $B$, we have $K'(B)=|B|$. The empty string $M$ encodes a TM that, on input $n=|B|$, outputs a set $S_B$ of size $2^n$ containing $B$. Hence $|M| + \log |S_B| = 0 + n = |B| = K'(B)$. Hence, the empty string is the MKSS for (any good) $B$, and $B$ is not an MKSS. $~~\Box$.

$\endgroup$
  • $\begingroup$ I changed the definition of typicality. $\endgroup$ – yters Jul 11 '18 at 15:26
  • 2
    $\begingroup$ With that definition it is likely to be dependent on the TM encoding scheme, isn't it? For example, in a standard TM encoding scheme, the answer would be no, because fewer than half the strings of a given length are valid TM encodings, and so fewer than half can be an MKSS. Maybe the question becomes, is there a TM encoding scheme such that the answer to your question is "yes"? A positive answer would require an encoding scheme tailored to MKSS's, because otherwise most strings won't encode TM's that could be an MKSS. Can you find a more robust way to pose your question? $\endgroup$ – Neal Young Jul 11 '18 at 16:15
  • $\begingroup$ I updated the question to request a TM encoding such that MKSS's are typical. $\endgroup$ – yters Jul 11 '18 at 22:16
  • $\begingroup$ I updated the answer to answer that case too. $\endgroup$ – Neal Young Jul 12 '18 at 21:44
  • 1
    $\begingroup$ Thanks. It does make me wonder in what way MKSS's are meaningful, as their basic properties seem to be encoding-dependent. $\endgroup$ – Neal Young Jul 13 '18 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.