I find this, but I can't complete it, is there any other solution for it?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Related: Single-tape Turing Machines with write-protected input recognize only Regular Languages $\endgroup$– xskxzrCommented Sep 27, 2019 at 11:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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.
answered Dec 16, 2012 at 0:08
-
$\begingroup$ 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. $\endgroup$– babouCommented Dec 21, 2014 at 17:25
-
$\begingroup$ 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? $\endgroup$– babouCommented Dec 21, 2014 at 17:43
-
$\begingroup$ @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.) $\endgroup$ Commented Dec 26, 2014 at 13:37
-
$\begingroup$ @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. $\endgroup$ Commented Dec 26, 2014 at 13:41
-
$\begingroup$ 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. $\endgroup$– babouCommented Dec 26, 2014 at 15:18
$\begingroup$
$\endgroup$
1
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.
[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).
-
$\begingroup$ Your last answer is seems intuitively obvious. But the problem can be more subtle. If you have a one-tape Turing Machine (i.e. the input is given on the work-tape), where the input part of the tape is write protected, but the machine can do any computation it cares on the initially blank part of the tape, and store there whatever it cares to store, it will still recognize only regular languages. $\endgroup$– babouCommented Dec 21, 2014 at 17:40