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.



compression of a Turing machine run sequence
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.


