[Solved]: How does a turing machine with doubly infinite tape simulate a normal-taped turing machine?

Problem Detail: 

The intuition is that on any input, we can write a symbol like $\#$ on the left that tells the machine to not move past this symbol. However, I'm running into problems trying to show this using the formal definition of a turing machine. It's not simple using the usual 7-tuple definition. Any help would be appreciated.

Asked By : user30874

Answered By : Luke Mathieson

Given the doubly infinite machine $M = (Q,\Gamma,\sqcup,\Sigma,\delta,q_{0},F)$ where:

• $Q$ is the set of states,
• $\Gamma$ is the tape alphabet,
• $\sqcup \in \Gamma$ is the blank symbol,
• $\Sigma \subseteq \Gamma\setminus\{\sqcup\}$ is the input alphabet,
• $\delta: Q\setminus F\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\}$ is the transitions function (there are various common modifications to $\delta$ which you can add in if you wish),
• $q_{0} \in Q$ is the start state, and
• $F$ is the set of final states,

we can simulate a singly infinite Turing machine with the following modifications to $M$:

• add a new symbol $\#$ to $\Gamma$ which will mark the "left-hand end" of the simulated tape,
• add the new states $k_{0}$, $k_{1}$ and $r$ to $Q$,
• make $k_{0}$ the new start state,
• add the following transitions:
  • $(k_{0}, x) \mapsto (k_{1},x,L)$ for every $x \in \Gamma$
  • $(k_{1}, \sqcup) \mapsto (q_{0}, \#, R)$
  • $(q_{i}, \#) \mapsto (r, \#, L)$
• make $r$ a reject state in whatever way you're handling reject states.

This new machine starts (as suggested in the question) by writing a new, special, end-of-tape symbol just to the left of the input. Then if it ever sees that symbol again, it rejects (it has "fallen off the tape").

A similar technique can be used to prevent a singly infinite TM from falling off the left-hand end of the tape, so you can also encode that into the machine, and it would work similarly.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41625