0
$\begingroup$

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?

$\endgroup$
2
  • $\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
    Commented Dec 3, 2015 at 19:29
  • $\begingroup$ cs.stackexchange.com/q/7412/755 $\endgroup$
    – D.W.
    Commented Apr 19, 2017 at 22:20

1 Answer 1

-1
$\begingroup$

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

$\endgroup$
8
  • 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
    Commented Dec 4, 2015 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
    Commented Dec 5, 2015 at 22:37
  • 1
    $\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
    Commented Dec 6, 2015 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
    Commented Dec 6, 2015 at 23:34
  • 1
    $\begingroup$ This argument is incomplete. While it shows how you can get rid of the working tape, it doesn't deal with the fact that the head can move both backwards and forwards. It also doesn't deal with the fact that the tape has infinitely many blank symbols. In a DFA, the automaton can only move forward in the input tape. A complete argument would need to rewrite the Turing Machine so that its head only moves in the forward direction and stops after it reads a blank. $\endgroup$
    – wlad
    Commented Dec 21, 2017 at 20:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .