Commonality of minimal Kolmogorov structure functions 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.
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 &lt; \liminf_{n\rightarrow\infty} \mu(n) &lt; 1$$

Proof. First we show that $\liminf_{n\rightarrow\infty} \mu(n) &lt; 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) &lt; 1$.

Next we show that $\liminf_{n\rightarrow\infty} \mu(n) &gt; 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 &gt; 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| &lt; |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$:


at most $2^{n-k}$ have $K(B) \le n-k$ (by the standard counting argument), and
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,


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