10
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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)...".) $\endgroup$ – Raphael Sep 18 '14 at 18:04
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Why do we need to convert the index to a binary format? I thought Turing machines were abstract models of computation, so then why should they convert decimal numbers to their binary representations? $\endgroup$ – jsguy Sep 18 '14 at 18:41
  • 4
    $\begingroup$ @jsguy Why do you assume that numbers are in decimal? But, sure, decimal would work fine, too. It still takes $O(\log n)$ digits. $\endgroup$ – David Richerby Sep 18 '14 at 18:52
  • $\begingroup$ @DavidRicherby, can't a tape cell hold a number that has more than one digits? $\endgroup$ – jsguy Sep 18 '14 at 18:56
  • 4
    $\begingroup$ @jsguy Refresh the definition of Turing machines. A tape cell holds a single symbol from the alphabet. $\endgroup$ – David Richerby Sep 18 '14 at 18:57
  • $\begingroup$ @DavidRicherby, thanks I think it makes sense to me now! $\endgroup$ – jsguy Sep 18 '14 at 19:02

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.