How can I prove that the language of a read-only Turing machines is regular?

Question

I find this, but I can't complete it, is there any other solution for it?

Answer 1

According to wikipedia, a read-only Turing (rTM) machine is a two-way finite automaton (2FSA). Two-way finite automata accept regular languages, and we are done.

Unfortunately, it is not that simple.

A Turing machine is allowed to wander into the area of the tape that consists of blank cells. This a 2FSA cannot do, usually it has end-of-tape markers. (Turing machines in general do not have these markers, otherwise they would be equivalent to linear-bounded automata.) Now a simulation of a rTM machine by a 2FSA is straightforward for the written part of the tape. For the blank parts we need transitions to code that the machine leaves to the right in state $q$, making a computation on blanks, returning in the rightmost cell in state $q'$. These are fixed by the machine, and do not depend on the actual input. Similarly for the left part (is the tape is two-sided infinite). Then there are accepting transitions that recognize that the rTM walks off the tape, does not return, but halts (and accepts). Non-halting non-returning excursions in the blank part can be ignored, they do not add to the accepted language.

Answer 2

Just hearing the question makes me think of two aspects:

• Why class of automata from Regular Language(RL) is called finite automata.

The class of automata for Regular Language(RL) is Finite Automata(FA). The automata is called finite because of finite memory available in term of states. So can construct Finite Automata for a language for which to process any string in language it requires to stored finite(Bounded) information only at any instance.
e.g Fan-Switch example with ON-OFF state we can say which state is in FAN(running or off). But we can't tell how many time switch has been ON-OFF.

Because there is only Finite state in any automata, memory in-term of states can be finite. We can only read input string w and switch state to memorized what type has been come like even or odd, or dived by two, But can not count information as required in aⁿbⁿ for n >0.

• How to enhance capability of Finite automata?

The next is, if we can have only finite memory in form of states, how can we improve automata, and build a new class of automata that is more capable then Finite Automata. Obvious answer is add external memory.

In PDA memory is attached in restricted from called stack (where push and pop operation are allowed). We can store information in stack while processing input string w. that can be read later as required.

[ANSWER]

In Turing Machine memory is much flexible than PDA, like a Random Access Memory. We can read-write any memory location at any instance while processing a language input string w. Hence Turing Machine is much capable then FA because we can store information and read from any where in memory.
But think if we don't store information in memory then how can we keep track of unbounded information in form of state. This become again incapable to processes languages that required to stored unbounded information while processing strings in language.
In this way A READ ONLY only TURING MACHINE that doesn't write(store) information in memory is just a kind of Finite Automata. (external memory not used).