Commonality of minimal Kolmogorov structure functions
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$.