7
$\begingroup$

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as the sequence of state-symbol pairs that ensue in the computation. call the $i$th ensuing state $s'_i$ and the $i$th ensuing symbol $a'_i$.

then the run sequence is the sequence $[(s'_1,a'_1),(s_2,a'_2),(s'_3,a'_3),...]$. or equivalently of composite symbol-pairs $[s'_1a'_1,s'_2a'_2,s'_3a'_3,...]$. if the computation terminates after $z$ steps then $i\leq z$. (note the run sequence is also defined for sequences that do not terminate, in that case its an infinitely long sequence but a (long?) finite initial subsequence alone can be considered.)

now consider large run sequences for large inputs and a large $z$. ie consider the question for recursive machines only.

question: what can be said about the compressibility of the Turing machine run sequence?

"compressible" means: is there an algorithm that can be used in the sense of data compression.

my current suspicion (without proof so far) is that if the machine is recursive and runs in some time $O(f(m))$ or (space $O(h(m))$ resp.) where $f(m)$ is some "std" function of input length $m$ say logarithmic, polynomial, exponential etc. then the run sequence is indeed compressible in some sense.

does anyone know a similar formulation of this problem that can be found in the literature or is studied somewhere? thx!

motivation: a possible useful formulation for understanding separations between complexity classes. think this problem might help bridge relationships between time and space complexity separations, tradeoffs etc.

$\endgroup$
7
  • 12
    $\begingroup$ Doesn't a description of the turing machine and its input constitute a compression of the run sequence? $\endgroup$
    – Will Sawin
    Jan 22, 2012 at 0:22
  • $\begingroup$ excellent point. so maybe consider a "blind" sequence such that one is given only the sequence and not the TM that generated it. in other words the general idea is to consider the run sequence alone as input to a general data compression program. $\endgroup$
    – vzn
    Jan 22, 2012 at 0:38
  • 1
    $\begingroup$ Do you really mean just (state,symbol)-pairs, or perhaps (state,symbol,movement)-triples, where movement can be "left" or "right"? If you mean the latter, then the input sequence (as far as it has been considered) and the Turing machine description (as far as it is relevant to the computation) can be computed from the run sequence. $\endgroup$
    – Goldstern
    Jan 22, 2012 at 12:25
  • $\begingroup$ interesting point. determining the TM from the run sequence is not possible in the sense that if we want to study the problem in general case ie over (input,run-sequence) pairs, it seems we might find a TM that is consistent with those pairs but cannot determine the TM in general that will also be consistent with new (input,run-sequence) pairs. one simplification of the problem is that for a fixed TM we know any state and symbol input will always be one of either L(eft) or R(ight) direction & it cant switch. $\endgroup$
    – vzn
    Jan 22, 2012 at 16:02
  • $\begingroup$ unfortunately the two comments so far are going in different directions/angles of a solution I hadnt considered & am thinking I might have to reformulate the problem to avoid those angles but Im not immediately sure how to do that. $\endgroup$
    – vzn
    Jan 22, 2012 at 16:04

1 Answer 1

4
$\begingroup$

A run sequence $r = [s'_1a'_1,s'_2a'_2,s'_3a'_3,...]$, of a Turing machine $M$ on input $x$ is a highly compressible string:

$$K(r) = K(\langle M, x, z \rangle) + c \leq |\langle M \rangle| + | x | + \log z + c' $$

where $z$ is the number of steps of the run sequence.

$\endgroup$
4
  • $\begingroup$ This is a slightly corrected version of Will Sawin's comment under the question. Will proposed "a description of the Turing machine and its input" as a compression. Vor correctly points out that, when the run sequence is shorter than the whole run of the machine, then the desired length $z$ must also be included in the compression. $\endgroup$ Apr 30, 2013 at 13:02
  • $\begingroup$ @AndreasBlass: indeed it's not too different from Sawin's idea :( ... there are also other variants (consider only states, include head directions, 0->1 1->0 transitions, crossing sections, ecc. ecc.); but obviously they all lead to the same highly compressible property. $\endgroup$
    – Vor
    Apr 30, 2013 at 15:03
  • $\begingroup$ this is the $K$ from Kolmogorov complexity? think it should be defined $\endgroup$
    – vzn
    May 1, 2013 at 4:32
  • $\begingroup$ @vzn: yes, you can look at this short introduction by Lance Fortnow $\endgroup$
    – Vor
    May 1, 2013 at 15:03

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.