<p>I think it can be compressed to linear space.</p>

<p>I assume the machine $M$ has one tape. Initially the first $n$ cells contain the input, which is followed by $2^O(n)$ zeroes. $M$ is oblivious and always makes $k$ passes through the tape (from left end to right and back), and then accepts or rejects. Let $p_i$ denote the state the machine enters after reading the $n$-th cell on $i$-th pass during the left-right phase, and let $q_i$ denote the state the machine enters after reading the $n+1$-th cell on $i$-th pass during the right-left phase. Note that $q_1$ is a function of $p_1$ alone, and generally $q_i$ depends only on the sequence $p_1, p_2, \dots, p_i$ (this sequence has length at most $k$, which is fixed). Therefore we can always compute the state $q_i$ without actually continuing the pass through the extra scratch space - the transitions can be hardcoded into the description of the machine.</p>

CC BY-SA 3.0
2012-05-06T18:51:47.743Z
this answer assumes M is oblivious which is possibly a special case of the above question. seems, the general question remains open. it appears to me the larger question is deep & related to open complexity class separations eg P=?NP, ie a fully detailed answer would likely lead to new complexity class separations, possibly some of the hardest ones.
vzn
CC BY-SA 2.5
2010-11-02T23:57:28.187Z
2010-11-02T23:57:28.187Z
Karolina Sołtys
<p>So an idea I've had bouncing around for a while goes like this: suppose we have some TM that runs in possibly exponential time, and thus can use possibly exponential space.  But let's say that it doesn't use its available space very often: say, it's oblivious and makes a constant number of passes back and forth across the input.</p>

<p>It seems to me that such a machine can have its space usage improved, but I'm not sure of any relevant results.  Can we simulate such a machine in some smaller space bound (ideally polynomial or close to it...), if we allow the simulator to use that smaller amount of space however it wants?  Anyone know of such a result?</p>

CC BY-SA 3.0
2012-05-05T22:15:10.383Z
think this problem [compression of a TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence) is related
vzn
CC BY-SA 2.5
2010-11-02T21:36:55.383Z
You can always reduce the amount of space required by increasing the size of the alphabet, but this will only be a constant reduction. Turing machines of course can be optimized, but not automatically, in general.
Dave Clarke
CC BY-SA 2.5
2010-11-02T22:12:27.327Z
Increasing the size of the alphabet does increase the number of bits needed to store each symbol (the entropy). So is it a real reduction in space from information theoretic point of view or does that reduction ignore this side ?
Mohammad Alaggan
CC BY-SA 2.5
2010-11-02T22:30:56.803Z
Do you mean "constant number of passes ... across the _scratch tape_" instead of "..._input_"?
Warren Schudy
<cc.complexity-theory><space-bounded>
compressing rarely used space
ahh
# compressing rarely used space

(Asked by: username_0 on 2010-11-02)

So an idea I've had bouncing around for a while goes like this: suppose we have some TM that runs in possibly exponential time, and thus can use possibly exponential space. But let's say that it doesn't use its available space very often: say, it's oblivious and makes a constant number of passes back and forth across the input.

It seems to me that such a machine can have its space usage improved, but I'm not sure of any relevant results. Can we simulate such a machine in some smaller space bound (ideally polynomial or close to it...), if we allow the simulator to use that smaller amount of space however it wants? Anyone know of such a result?

**Tags:** cc.complexity-theory, space-bounded

> **Comments:**
> **username_2**: You can always reduce the amount of space required by increasing the size of the alphabet, but this will only be a constant reduction. Turing machines of course can be optimized, but not automatically, in general.  
> **username_3**: Increasing the size of the alphabet does increase the number of bits needed to store each symbol (the entropy). So is it a real reduction in space from information theoretic point of view or does that reduction ignore this side ?  
> **username_4**: Do you mean "constant number of passes ... across the _scratch tape_" instead of "..._input_"?  
> **username_1**: think this problem [compression of a TM run sequence](http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence) is related  

---

## 1 answers

### Answer by username_5 on 2010-11-02. Score: 9 | Accepted answer

I think it can be compressed to linear space.

I assume the machine $M$ has one tape. Initially the first $n$ cells contain the input, which is followed by $2^O(n)$ zeroes. $M$ is oblivious and always makes $k$ passes through the tape (from left end to right and back), and then accepts or rejects. Let $p\_i$ denote the state the machine enters after reading the $n$-th cell on $i$-th pass during the left-right phase, and let $q\_i$ denote the state the machine enters after reading the $n+1$-th cell on $i$-th pass during the right-left phase. Note that $q\_1$ is a function of $p\_1$ alone, and generally $q\_i$ depends only on the sequence $p\_1, p\_2, \dots, p\_i$ (this sequence has length at most $k$, which is fixed). Therefore we can always compute the state $q\_i$ without actually continuing the pass through the extra scratch space - the transitions can be hardcoded into the description of the machine.

> **Comments:**
> **username_1**: this answer assumes M is oblivious which is possibly a special case of the above question. seems, the general question remains open. it appears to me the larger question is deep & related to open complexity class separations eg P=?NP, ie a fully detailed answer would likely lead to new complexity class separations, possibly some of the hardest ones.  

---

