HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
expanduniversalexecutedbitstringswhenturinghalttheymostmachine

Problem

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

Solution

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) loop; that's not a problem.
It's easy so see that for T all expand.

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

Code Snippets

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

Context

StackExchange Computer Science Q#80570, answer score: 4

Revisions (0)

No revisions yet.