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*}

  • 2
    $\begingroup$ It's not quite clear to me what you mean with "bitstrings expand when run on a TM and halt". $\endgroup$
    – adrianN
    Aug 29, 2017 at 4:51
  • $\begingroup$ @adrianN The edit helps, doesn't it? $\endgroup$
    – Raphael
    Sep 2, 2017 at 8:26

3 Answers 3


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


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.


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.

  1. 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(>)$.


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.

  • 2
    $\begingroup$ That's a lot of words for saying "I have no idea". o.o $\endgroup$
    – Raphael
    Sep 2, 2017 at 12:20

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.

  • 1
    $\begingroup$ This statement is false in general, as my answer shows. That is to say, I'm sure you can find a random model for which it is true ("X is more likely than Y") but you should specify what you have in mind. $\endgroup$
    – Raphael
    Sep 4, 2017 at 15:03
  • $\begingroup$ I'm unclear why being able to construct a TM for a particular purpose invalidates the statement. If we pick a universal TM without reference to a particular output, then for any output, it will only map a finite number of shorter inputs to that output, but it will map an infinite number of longer inputs to that output. If we restrict the TM to only halt with shorter inputs, then it is no longer a UTM as it can no longer compute everything a UTM can. $\endgroup$
    – yters
    Sep 4, 2017 at 18:20
  • 2
    $\begingroup$ Neither your question nor your answer mention that they are about universal TMs. Even so, note that I construct partially computable functions for the extreme cases, which means that any UTM has infinitely many (!) indices for each of them, and myriads of other, similar functions. There are so many infinite quantities here that there is no simple conclusion about what is "more likely". You'll need a random model to make such a statement. $\endgroup$
    – Raphael
    Sep 4, 2017 at 18:40

Your Answer

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

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