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 Gammasetminus{sqcup}$ is the input alphabet,
- $delta: Qsetminus FtimesGammarightarrow QtimesGammatimes{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
