World's most popular travel blog for travel bloggers.

[Solved]: Why do we reject turing machines that use space less than the log of the length of the input?

, , No Comments
Problem Detail: 

In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that

We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the machine to at least be able to remember the index of the cell of the input tape that is currently reading.

What does that exactly mean? I don't see the point, what does "remembering the index of the cell currently read by the head of the input-tape" mean? Any clarifications?

Note that we does not count the movements of the input-tape into our space considerations so we only count for the work-tape

Asked By : Maths Lover

Answered By : Yuval Filmus

Consider any program in high-level language that has a loop going over all items:

for i from 1 to n     do something end for 

Implementing this loop takes $O(\log n)$ work space, since the variable $i$ takes $O(\log n)$ bits to store. If you're not allowed to use even that much memory, then you have to be very careful when implementing any non-trivial algorithm, if it is possible at all; for instance, any results will be highly dependent on the exact definition of the model of computation.

Arora and Barak don't want to focus on such issues, so they just assume that you are given at least logarithmic space. There are enough interesting things to say without having to worry whether some general reduction can be carried out in sublogarithmic space. (And if you want to study regular languages -- languages that can be recognized with constant space -- you don't need complexity theory.)

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback