2
$\begingroup$

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 ?

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

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).
$\endgroup$
2
  • $\begingroup$ @hopingGI_in_P That is a completely unrelated question, not a comment. $\endgroup$
    – chi
    Mar 24 '17 at 9:24
  • $\begingroup$ All languages decidable in constant time are regular. $\endgroup$ Mar 24 '17 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy