# What does sublinear space mean for Turing machines?

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?

• Afaik, space complexity usually considers additional memory for exactly this reason. (Note that your question is ill-posed; you want to ask "how to achieve O(log n)...".)
– Raphael
Sep 18 '14 at 18:04

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.
• @jsguy Why do you assume that numbers are in decimal? But, sure, decimal would work fine, too. It still takes $O(\log n)$ digits. Sep 18 '14 at 18:52