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:
the TM keeps computing for ever, without the head ever coming coming
back on the input part of the tape;
the TM reaches an (a) accepting or (b) stops in a non-accepting state;
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
