Do most bitstrings expand if they halt when executed by a Universal Turing machine?

Question

According to the counting argument, most bitstrings are incompressible or only slightly compressible. However, the counting argument does not work in the opposite direction, since there are an infinite number of bitstrings that are longer. So, the counting argument does not tell us whether most bitstrings will or will not expand when run on a universal Turing machine and halt.

Is it known whether most halting bitstrings will expand?

By 'expand' I mean that a bitstring $b_1$ generates a bitstring $b_2$ when run on a universal Turing machine, \begin{align*} \mathcal{U}(b_1)=b_2, \end{align*} such that the length of $b_2$ is greater than $b_1$ \begin{align*} \ell(b_2) > \ell(b_1). \end{align*}

Answer 1

Both can happen.

The counting argument applies to all TMs that always halt.

In the partial world, you can construct Turing machines for both extreme cases (and everything in between) like so. Assume $T$ is a Turing machine. Construct

T<(x) = if |T(x)| < |x| then return T(x) else loop

and

T>(x) = if |T(x)| > |x| then return T(x) else loop

Note that if T(x) loops, both T<(x) and T>(x) loop; that's not a problem. It's easy so see that for T<, all halting inputs contract, and for T> all expand.

Rice's theorem immediately shows that these expansion/contraction properties (and related ones) are undecidable, by the way.

Answer 2

Well, ... several (different!) scenarios:

I assume that U is a (fixed) UTM, you give it a string s = (TM,input), U(s) = TM(input) = either a finite output "f" or else DIS, the TM does not halt. Additional difficulty: "DIS" vs. "f requires enormous time" can not be resolved by just looking while waiting (in many cases).

Your question then might be: How often do we have |s| < |f| (expansion), how often is |s| >= |f| in the non-DIS cases.

1A. "Often" as a counter is void: Both cases appear (countably) infinitely often,namely:

Large s, short f: just stop the (short) TM, regardless of the (arbitrarily large) input, put f = empty word;

Short s, large f: TM consists of $(i)$ copy input to output to make for infinitely many cases, then $(ii)$ run BusyBeaver(7), producing a lot more output, in general run BB(7+log(log(|s|))).

1B. "Often" as a measure is more useful: Count each case with measure $2^{-|s|}$ ($s$ should be self-delimiting), throw away those DIS cases.

Compare $\mu(\le) = \sum_{U(s)\ stops, |f| \le|s|} 2^{-s}$ with $\mu(>) = \sum_{U(s)\ stops, |f| > |s|} 2^{-s}$.

My feeling is that a considerable fraction of machines just produces nothing or a short output, for any, even quite large, input, so probably $\mu(\le) > \mu(<)$ (no proof yet).

This might actually be decidable in finite time: If the difference between the two measures is larger than the measure of the unchecked cases, we are done.

2A/B. You include DIS in one of the cases (since nothing definite happens, the output is neither larger nor shorter than the input, a very large current tape contents might be blanked out later).

I guess that the side with DIS wins. Again, this might be (even easier) decidable by knowledge of finitely many cases.

3. You separate output and working tape and count DIS cases according to the actual output (which will not be allowed to shrink ... but still might grow). Very unclear situation for the $\mu(\le)$ part, while a DIS with current output longer than $|s|$ certainly goes into $\mu(>)$.

Summarizing:

Interesting question,

potential of completely answering it with finite effort (unlike, e.g. the halting probability $\Omega$ in all its precision);

I do not know this answer.

Answer 3

There are a finite number of bitstrings with a length less than the output, but an infinite number with greater length. Therefore, it is much more likely a halting bitstring will produce a shorter bitstring than a longer bitstring.