# Do we need to read the input completely in Turing machine?

This question is motivated from the question $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$. I am wondering, how is it possible to decide a language without reading the entire input. I have seen the similar situation in space complexity ( L and NL ,where we define new model of computation).

My model of computation is Turing machine (for e.g. see lecture note on Turing machine)

My question : Do we need to read the input completely in Turing machine ?

• My answer would be a simple "No." if only stackexchange allowed such short answers. Mar 24 '17 at 20:08

There is no such requirement. A Turing machine which decides a language can do whatever it wants as long as it always halts; the language it decides is the set of words which it accepts.

There are many languages which don't require reading the entire input:

• The empty language.
• The complete language.
• The language of all words starting with 0.
• The language of words of length 2.

Here is a more non-trivial example:

• Given a language $L$, define the language $$X(L) = \{ 0^\ell 1 w x : |w|=\ell \text{ and } w \in L \}.$$ The language $X(L)$ can be decided by a Turing machine which doesn't always read the entire input. Moreover, generally speaking $L$ and $X(L)$ have roughly the same complexity (though $X(L)$ requires the ability to count).
• @hopingGI_in_P That is a completely unrelated question, not a comment.
– chi
Mar 24 '17 at 9:24
• All languages decidable in constant time are regular. Mar 24 '17 at 9:29