0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I get the idea, but I have one question. Why do we want to reject the input if the machine falls off to the left? Because for a singly infinite machine on the left end, if the transition calls for left shift, it can't move left, so it stays put. The machine doesn't necessarily reject the input. $\endgroup$ – user30874 Apr 21 '15 at 1:52
  • $\begingroup$ @user30874, that is another possibility. There are several equivalent definitions of TMs that do different things when you hit the left end, so you can substitute that behaviour in instead of rejecting (in this construction you can do that by adding a transition which moves the head right when it sees #, but doesn't change state, to every state. $\endgroup$ – Luke Mathieson Apr 21 '15 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.