Turing machine with read only part and finite tape

Question

Given a Turing machine whose input part is read only , and in addition to the input part has a finite tape of length K, prove that this is equivalent to a DFA.

I tried to find some bound for the number of configurations that the machine has and convert these configurations to states in a DFA , thus simulating the Turing machine described above. But I couldn't find such bound, since the input part of the machine is unbounded.

Any hint or help will be appreciated!!

Answer 1

Since the working tape is finite that tape will have only finitely many possible configurations, so we can throw the working tape away and instead consider its configuration to be part of the state.

What we then have is a fully read-only, but still bidirectional Turing machine, and we're asked to show that such machines have the same power as read-only machines that can move only towards the right (that is, DFAs).

However, by having sufficiently many states, we can simulate the execution of the bidirectional machine in a single forward pass. All we need to remember at each square we get to is:

• Which state is the first state the bidirectional machine will reach this square in?
• For each state $s$, if the bidirectional machine moves left from this square and into state $s$, which state will it next reach this square in? Or will it perhaps accept before it gets back to this square, or diverge without getting back to this square?

There are only $S(S+2)^S$ many different sets of answers to these questions, which is finitely many. And for each set of answers, combined with an input symbol, we can once and for all (that is, while generating our DFA) compute what will be the corresponding set of answers for the next square.

(The final sentence of the above paragraph of course demands an explicit proof, the details of which I will leave to the OP to puzzle out).