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?

  • $\begingroup$ 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. $\endgroup$ – Dave Clarke Nov 2 '10 at 21:36
  • $\begingroup$ 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 ? $\endgroup$ – M. Alaggan Nov 2 '10 at 22:12
  • $\begingroup$ Do you mean "constant number of passes ... across the scratch tape" instead of "..._input_"? $\endgroup$ – Warren Schudy Nov 2 '10 at 22:30
  • $\begingroup$ think this problem compression of a TM run sequence is related $\endgroup$ – vzn May 5 '12 at 22:15

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.

  • $\begingroup$ 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. $\endgroup$ – vzn May 6 '12 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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