Single-tape Turing Machines with write-protected input recognize only Regular Languages

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.

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
w

StackExchange Computer Science Q#22082, answer score: 13