[Solved]: What does sublinear space mean for Turing machines?

Problem Detail: 

The problem of deciding whether an input is a palindrome or not has been proved to require $\Omega(\log n)$ space on a Turing machine. However, even storing the input takes space $n$ so doesn't that mean that all Turing machines require space $\Omega(n)$?

Of course, there's no contradiction here, since any function that uses at least linear space also uses at least logarithmic space. But writing $\Omega(\log n)$ does suggest that it's possible for a Turing machine to use less than linear space – after all, why would people spend all that time proving $\Omega(\log n)$ if that was exactly the same thing what seems to be a trivial $\Omega(n)$ bound? So what does it mean for a Turing machine to use less than linear space?

Asked By : jsguy

Answered By : Yuval Filmus

When dealing with restricted space, we use the following model. The Turing machine has three tapes: a read-only input tape, a read-write work tape, and a write-only output tape. We only measure space consumption on the work tape. For palindromes, with space $O(\log n)$ on the work tape we can implement FOR loops that go over the input, comparing matching characters on both ends. Each index takes $O(\log n)$ space to store.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30112