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

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

• – xskxzr Sep 27 '19 at 11:14

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.

• I think this type of proof no longer works when the (on-line) Turing Machine is allowed to write on the blank tape, not used by the input. But the accepted language is still regular. However I could not find references to this result, and that surprised me, as it has interesting aspects. I give a proof in an answer to a similar question, but explicitly allowing to write on the blank part of the tape. – babou Dec 21 '14 at 17:25
• Is this wikipedia definition (a read-only TM is a 2DFA) accepted by some people, or is it just an error? For one thing, it should be 2 FSA, since a TM may be non-deterministic. And then, I thought 2FSA were limited to input string, with no extra tape? – babou Dec 21 '14 at 17:43
• @babou Personally I would prefer a definition with two endmarkers, to avoid walking off the input. The Wikipedia definition seems to have only one marker to indicate the tape is only infinite in one direction? Yes, 2FSA only have one tape. But I think that is the type of TM they refer to, having only a single tape with input, no separate working tape. (Such a separate tape is needed to define logarithmic space complexity I believe, but that is not an issue here.) – Hendrik Jan Dec 26 '14 at 13:37
• @babou Your first comment, on rewriting the blanks is interesting. My intuition did not want to believe your result, but then I realized it is impossible to copy the input to the blank part without being able to mark the input. Confusing and interesting! Sorry, I do not know references either. – Hendrik Jan Dec 26 '14 at 13:41
• Actually I started with the same intuition. It is the insistance of InstructedA saying he could not copy the input that made me think again, and then I realized it was not possible to do so, because only finite information can be extracted, limited by the number of states. Actually, I have to modify my answer to give him/her credit for that. – babou Dec 26 '14 at 15:18

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

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.