patternMinor
Do most bitstrings expand if they halt when executed by a Universal Turing machine?
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*}
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
and
Note that if
It's easy so see that for
Rice's theorem immediately shows that these expansion/contraction properties (and related ones) are undecidable, by the way.
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 loopand
T>(x) = if |T(x)| > |x| then return T(x) else loopNote 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 loopT>(x) = if |T(x)| > |x| then return T(x) else loopContext
StackExchange Computer Science Q#80570, answer score: 4
Revisions (0)
No revisions yet.