11
$\begingroup$

Here is the problem:

Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages.

My idea is to prove that this particular TM is equivalent to a DFA.

Using this TM to simulate DFA is very straightforward.

However, when I want to use this DFA to simulate TM, I encounter the problem. For the TM transition $\delta(q,a)=(q',a,R)$, DFA can simulate definitely by reading tape to the right and doing the same state transition.

For $\delta(q,a)=(q',a,L)$, I cannot figure out how to use this DFA or NFA to simulate the left move because the DFA only reads to left and has no stack or something to store.

Should I consider another way? Could anyone give me some hints? Thanks.

$\endgroup$
  • 2
    $\begingroup$ First you should be careful about the logic/meaning of your sentences. Your title implies that you only have to prove that any language recognized by the xxx Turing machine is regular. You do not have to prove the converse: that any regular language is recognized by such a machine (even though that is obvious). So your 4th paragraph "Using ..." is irrelevant for the question as stated. Then, in the fifth, you use "this DFA", apparently referring to the the DFA of the previous paragraph, which no longer has anything to do with the problem at hand. You have a TM, and must find a DFA yet unknown. $\endgroup$ – babou Feb 27 '14 at 8:03
  • 3
    $\begingroup$ A hint: You might want to look up the notion of "crossing sequences". Also, you might want to try to prove that it is equivalent to a NFA (with a larger state set). As a warmup, imagine that the TM's head goes right 10 steps, then left 3 steps, then always right from there on -- could you build a NFA to simulate the set of inputs that can be recognized by such a TM along such a head movement? $\endgroup$ – D.W. Feb 27 '14 at 8:05
  • 1
    $\begingroup$ @babou Allowing to write outside the input area does not give all RE in my view. This is because I haven't found a way to build the transition function that allows copying the input to the blank area outside the original input area. If that is possible to do without EVER writing to the original input area, then clearly one can work on the right side of the input just like a regular TM giving us all RE languages. $\endgroup$ – InformedA Dec 15 '14 at 3:21
  • 1
    $\begingroup$ @D.W. I do not understand how "crossing sequences" by themselves will solve this problem. Actually, I did not use them directly, but only through using the equivalence of 2NFA and NFA, But this equivalence is only part of the proof. BTW, since you seem to know the problem, would you know where it comes from, as I cannot find references on the Internet. The result actually surprised me, and I wonder why it does not seem to interest anyone. $\endgroup$ – babou Dec 17 '14 at 18:36
  • 1
    $\begingroup$ @D.W. Did you just think this was a rehash of the equivalence of standard FSA and 2-ways FSA, or do you know the origin of this problem: TM that do not write on their input. I am wondering why no one answered it in 9 months, and why it was asked by an apparently novice student. $\endgroup$ – babou Dec 19 '14 at 1:46
10
$\begingroup$

Introduction

I thought there might be an error in the original statement of the question, and the OP was no longer around to ask. So I assumed that the tape was read-only everywhere, and wrote a first proof based on that assumption, motivated by the fact that the TM has full Turing power outside the input part of the tape if it can write it, which induces the false belief that it can recognize any RE language.

However, that is not the case: the restriction on writing on the input part of the tape implies that only finite information can be extracted from the input, limited by the number of states on entry and exit of that part of the tape (combined with side of entry and exit). InstructedA is to be credited for remarking in a comment that there is a problem with recognizing any RE language, since it is not possible to make a copy of the input without EVER writing to the original input area,

Hence I wrote a second proof that assumes that only the input section of the tape is read-only, the rest being read-write allowed.

I am keeping both proofs here, as the first did help me find the solution, even though it is not necessary to understand the second proof, is more complex, and is subsumed by the second proof. It can be skipped. However, the weaker proof has the advantage of being constructive (to obtain a FSA equivalent to the Turing Machine), while the more general result is not constructive.

However I am giving first the last and more powerful result. I am a bit surprised that I was not able to find this result, even without proof, elsewhere on the net, or by asking some competent users, and any reference to published work would be welcome.

Contents:

  • Turing machines that do not overwrite input accept only regular languages. This proof is not constructive.

  • Turing machines with read-only tapes accept only regular languages. It may be skipped as subsumed by previous proof, but it uses a different approach, which has the advantage of being constructive.

Turing machines that do not overwrite input accept only regular languages

We recall that, while the TM does not overwrite its input, and is thus read only on its input, the TM can read and write on the rest of the tape. The proof relies on the fact that the observational behavior of the TM over an unlnown input can produce only a finite number of different cases. Hence, though the TM has full Turing power just by relying on the rest of its tape, its information on the input, which can be any string in $\Sigma^*$, is finite, so it can compute only on a finite number of different cases. This gives a different view of the finite character of regular languages, behavioral rather than structural.

We assume that the TM accepts when it enters an accept state.

Proof.

We define an input restricted computations (IRC) as a (read-only) computation of the TM such that the TM head stays on the input part of the tape, except possibly for the last transition that may move it to a cell immediately at the left or the right of the input area.

A left input restricted computations is an IRC that starts on the leftmost symbol of the input. A right input restricted computations is an IRC that starts on the rightmost symbol of the input.

We first prove that, for left input restricted computations that start in state $p$, the following languages are regular:

  • the language $K_{Lp\to Lq}$ of input strings such that there is a left input restricted computation, starting in state $p$, that ends on the first cell left of the leftmost input symbol in state $q$;

  • the language $K_{Lp\to Rq}$ of input strings such that there is a left input restricted computation, starting in state $p$, that ends on the first cell right of the rightmost input symbol in state $q$;

  • the language $A_{Lp}$ of input strings such that there is a left input restricted computation, starting in state $p$, that reaches an accept state.

And similarly, for right input restricted computations starting in state $p$, the following similarly defined languages are regular: $K_{Rp\to Lq}$, $K_{Rp\to Rq}$, and $A_{Rp}$.

The 6 proofs rely on the fact that two-ways non-deterministic finite state automata (2NFA) recognize regular sets (see Hopcroft+Ullman 1979, pp 36-41, and execise 2.18 page 51). A 2NFA works like a read-only TM on a tape limited to its input, starting initially from the leftmost symbol, and accepting by moving beyond the right end in an accepting state.

In each of the 6 cases, the proof is done by building a 2NFA that mimics the input restricted computations, but with some extra transitions to make sure it can start from the leftmost cell and accept the language by exiting from the rightmost end in an accepting state. For the $K_{??\to ??}$ languages, the original accepting state of the TM are changed into states leading to a halting non-accepting computation. In two cases, it may be necessary to add an extra cell with a new guard symbol on the left to detect TM computations that would terminate on the left end, so as to make them terminate on the right end.

These languages are defined for all combinations of states $p$ and $q$ of the original Turing machine. They represent all that can be observed (hence known and computed on) of the input by the TM.

If $k$ is the number of states, we thus define $4k^2$ languages $K_{??\to ??}$ and $2k$ languages $A_{??}$, hence a total of $4k^2+2k$ languages. Actually, some of these languages can be equal.

These are the only possible input restricted computations of the TM starting on one end of the input. Hence the computations induced by each input string (outside the input section of the tape) are characterised by the set of such languages the input belongs or does not belong to, hence by an intersection of each of these $4k^2+2k$ languages or its complement in $\Sigma^*$. All these intersections are finite intersections of r$4k^2+2k$ regular languages, or their complement which are also regular, and are therefore regular.

As a consequence, the set of these intersections defines a partition $\mathcal P$ of $\Sigma^*$ into at most $2^{4k^2+2k}$ regular languages (at most because some initial languages may be equal, and some intersections may be too). All strings belonging to the same equivalence class can produce exactly the same behavior, as seen from the ends of the input. This implies that they cannot be distinguished for computation of the Turing Machine, if you abstract away what happens in the read-only input area.

If we take two strings $u$ and $v$ in the same equivalence class of $\mathcal P$ , we can prove, by induction on the number of times the input area is entered, that for any accepting computation of the TM on $u$, there is an accepting TM computation on $v$ that is identical everywhere outside the input area. Hence, either all strings of an equivalence class are accepted, or none is. As a consequence, the language accepted by the TM is a union of equivalence classes of $\mathcal P$. Hence it is a finite union of regular languages, and thus it is a regular language.

To be very complete, we skipped the case of the empty input string. In this case, we just have a normal TM, that can read or write anywhere. If it reaches an accepting state, the empty string is in the language, else it is not. But that has little effect on the fact that the language recognized is regular.

Of course, it is not decidable whether an equivalence class is or is not in the language (the same holds for the empty string). This is a non constructive proof.

QED

Turing machines with read-only tapes accept only regular languages

This is subsumed by the previous result. It is kept as it uses a different approach, probably less elegant, and helped me in finding the previous proof by understanding what matters. But it can well be skipped by readers. However, one advantage of this proof is that it is a constructive proof producing a FSA accepting the language. A sketch of a similar proof is given by Hendrik Jan in his answer to a previous similar question, which assumes the whole tape was read-only.

I assume that the blank symbol that is on the unused part of the tape is never part of the input. This symbol is noted here $\Box$. The TM is supposed to accept when it reaches an accepting state.

The first step of the proof is to show that the head need not ever leave the input area of the tape. We thus analyze what happen when the head moves off the rightmost input symbol. The analysis when moving off the leftmost one is identical.

If we consider that the head has moved on the first blank cell on the right of the input, the TM being in state $q$, we have to understand what can happen. There are actually three cases, that may be simultaneously possible when the TM is non-deterministic:

  1. the TM keeps computing for ever, without the head ever coming coming back on the input part of the tape;

  2. the TM reaches an (a) accepting or (b) stops in a non-accepting state;

  3. the TM head ultimately comes back on the rightmost cell of the input, the finite control being in state $r$.

So we have to analyze the behavior of the TM finite control, when computing on a blank half-tape, starting in state $q$ on the leftmost cell of a blank half-tape, infinite towards the right.

Since the TM does not write, and reads only the blank symbol $\Box$, all the finite control can do is move left or right, and configurations are differentiated only by the position of the head, i.e. by an integer. The tape can be replaced by a counter, starting at $1$, that is incremented when the head moves right and decremented when it moves left, provided we consider only transitions that require the blank symbol on the tape. If the counter goes down to $0$, that correspond to a case of the head coming back on the rightmost input symbol.

A first remark is that we can ignore computations that do not terminate (case 1) or that terminate with rejection (case 2.b) since termination with acceptance is the only relevant case for accepting a string. So we only want to know whether the counter can go down to $0$, and in what state, or whether the computation can reach an accepting state.

We represent the relevant part of the finite state control by a directed graph where the vertices are the states of the TM, and where the edges are the blank transitions, with a weight +1 or -1 depending on whether the head is supposed to move right or left.

We define $A_R$ the set of state $q$ from which an accepting state can be reached with a positive weighted path.

We also compute the set $E_R$ of all pairs $(q,r)$ of states such that there is a path of weight $-1$ from $q$ to $r$, but no prefix of that path has a negative weight.

Then we modify the finite state control of the TM as follow (ignoring now all transitions on blank symbol $\Box$):

We create a new accepting state $q_A$ with no transitions.

For every transition $p,a\mapsto R,q$ you add a transition $p,a\mapsto R,q_A$ if $q\in A_R$ (i.e. an acceptance is possible if you are on the rightmost symbol).

For every transition $p,a\mapsto R,q$, and every pair $(q,r)\in E_R$ you add a dummy-transition $p,a\mapsto S,r$, where $S$ indicates that the head should not move. Since this is not an allowed move with most automata formalizations, these dummy states can be eliminated by transitive closure afterwards.

Once this is completed, we proceed to remove the dummy transitions. For every tape symbol $a$, we build the set $F_a=\{(p,r)\mid \text{ there is a dummy transition } p,a\mapsto S,r\}$, and we consider the transitive closure $F_a^*$ of the relation defined by $F_a$. Then, for every transition $r,a\mapsto L,s$ of the original TM, and every pair $(p,r)\in F_a^*$, we add a new transition $p,a\mapsto L,s$. Then all dummy transitions can be removed.

We proceed similarly for the moves of the head left of the input part of the tape, thus reversing left and right, and exchanging $+1$ and $-1$ in the graph weights.

Once this has been done, we remove completely all transitions on blank cells, since the corresponding computation are short-circuited by the new transitions. And we now have a new TM with a head that stays on the input all the time, except when accepting with state $q_A$, and still recognizes the original language.

We now have to do a few cosmetic changes, so as to make this TM behave exactly like a two-ways NDA (acceptance is only by exiting the input on the right into an eccpting state). Then we can rely on the on the know equivalence between 2-NDA and FSA (see for example Hopcroft+Ullman 1979, page 40) to obtain the proof that the language is regular.

QED

$\endgroup$
0
$\begingroup$

Moving left or right is not a problem, since two way finite automata recognizes exactty the regular languages (this is not obvious). However if your TM can write outside the portion of the tape of the input word, I think you can use this part of the tape to recognize in regular languages. Maybe I don't clearly understand the question.

$\endgroup$
  • $\begingroup$ This does not really look like an answer. BTW The above comment from D.W. about "crossing sequences" is exactly on topic: they are used to show that 2DFA (2way det FA) recognize regular sets. Here the only proble is that the TM can wander on the blank parts of the tape. If you can prevent that, then you are left with a 2DFA or a 2NFA. I think you can reduce a TM to another TM that does not wander on the blank, using also "crossing sequences". $\endgroup$ – babou Nov 14 '14 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.