Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.

According to wiki : A read-only Turing machine or Two-way deterministic finite-state automaton (2DFA) is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape. The machine in its bare form is equivalent to a Deterministic finite automaton in computational power, and therefore can only parse a regular language.

Can you explain in for formal way, please?

  • $\begingroup$ Describe a mapping between the two formalisms. E.g. describe how you would convert a 2DFA into a DFA and vice versa. $\endgroup$ – Witiko Dec 3 '15 at 19:29
  • $\begingroup$ cs.stackexchange.com/q/7412/755 $\endgroup$ – D.W. Apr 19 '17 at 22:20

If your machine can not modify the input tape and only has a working tape of fixed finite size, the amount of information that can be stored by the machine is finite (cardinality of the work tape's alphabet to the power of cells on the tape), hence you could do without the working tape by simply increasing the number of internal states of the machine, so this is then just a finite state automaton (with a large set of states).

  • 1
    $\begingroup$ The amount of information that can be stored by linear bounded automaton is also finite, yet it can accept languages which aren't regular. Your argument must, in some way, use the fact that the machine cannot overwrite contents of the tape. $\endgroup$ – Wojowu Dec 4 '15 at 21:44
  • $\begingroup$ This question is not about Turing machines with linearly bounded tape but with fixed work tape. The condition that the input tape is read only, means that you can not modify the input, i.e. this tape can not be used to store additional information during the computation. $\endgroup$ – MHS Dec 5 '15 at 22:37
  • $\begingroup$ My point is that your argument seems to work just as well with linearly bounded automata, so that your argument would prove that they only accept regular languages, which is simply wrong. $\endgroup$ – Wojowu Dec 6 '15 at 13:21
  • $\begingroup$ No because in the linearly bounded Turing machine case, the work tape has the length of the input tape (i.e. the input tape can be used to work on) and thus is not uniformly bounded in length. $\endgroup$ – MHS Dec 6 '15 at 23:34
  • $\begingroup$ What isn't uniformly bounded in length? And what does "uniformly" mean here? $\endgroup$ – Wojowu Dec 7 '15 at 5:24

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.