# Why do we reject turing machines that use space less than the log of the length of the input?

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

• Arora has a coauthor. Jul 20, 2016 at 6:40
• @YuvalFilmus, I've fixed that. Thanks.
– FNH
Jul 20, 2016 at 20:12

## 1 Answer

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.)

• So the motivation is that we only investigate TMs obtained by compilation of from RAM-model programs? Because there are plenty of languages a TM can decide with zero additional memory. Jul 20, 2016 at 6:55
• @Raphael No, we just don't want to focus on cases where the exact definition of the model could be very important. There are enough interesting things to say without having to worry whether some general reduction can be carried out in sublogarithmic space. Jul 20, 2016 at 7:13
• If you want to study regular languages you don't need complexity theory. Jul 20, 2016 at 7:14