Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
11  
Doesn't a description of the turing machine and its input constitute a compression of the run sequence? –  Will Sawin Jan 22 '12 at 0:22
    
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. –  vzn Jan 22 '12 at 0:38
1  
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. –  Goldstern Jan 22 '12 at 12:25
    
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. –  vzn Jan 22 '12 at 16:02
    
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. –  vzn Jan 22 '12 at 16:04

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  Andreas Blass Apr 30 '13 at 13:02
    
@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. –  Vor Apr 30 '13 at 15:03
    
this is the $K$ from Kolmogorov complexity? think it should be defined –  vzn May 1 '13 at 4:32
    
@vzn: yes, you can look at this short introduction by Lance Fortnow –  Vor May 1 '13 at 15:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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