Read-only Turing machine recognizes only regular languages? 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?
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).
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).