0
$\begingroup$

I am currently making a 2 tape turing machine for a language that has a binary palindrome (ex: L = {x is over {0,1} | x is a palindrome }. I can assume that the tape is only infinite in one way (the right side). and when using 2 tapes, the first one contains the input, the other is empty, and both heads start at the beginning of the tape.

So, my process has been:

  1. transfer all of the letters from tape1 to tape2 (ex: 0,0,R | U,0,R would keep the symbol 0 on tape1 and move it to the right while changing the empty symbol on tape2 to 0 and moving it right as well).
  2. Reverse tape1's head to the start again. However, I'm not sure how to do this if the tape is not infinite on both sides. I've been stumped on this part for a while and am unsure of how to continue.
Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ One-way tape(s) Turing Machine are often modeled assuming that there is a special unwritable symbol at the beginning of the tape ('#') and the head is initially placed at its right. In the transition table you can specify the behavior when the heads are on the '#' (a move to the left of '#' will leave the head where it is). This is in my opinion the best way to interpret it (but all models are clearly equivalent). $\endgroup$
    – Vor
    Apr 19 at 10:12

1 Answer 1

Reset to default
0
$\begingroup$

You can actually simply assume that the Turing Machine will not move passed the leftmost symbol on the tape if the tape is infinite only on the right. So, you can just say that it will move its head to the left until you reach leftmost cell of the tape. See for example, Sipser's description in Introduction to the Theory of Computation:

If $M$ ever tries to move its head to the left off the left-hand end of the tape, the head stays in the same place for that move, even though the transition function indicates L.

Here $M$ is the Turing Machine and L indicates moving the head to the left.

In case you don't want this you can begin by shifting the contents of the tape one position to the right and put some kind of delimiter as the leftmost symbol. You can use a blank if in case you do not want to increase the number of tape symbols.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "it will move its head to the left until you reach leftmost cell of the tape": this is not specific enough. What will it do on a move left operation in that case? Will it be a no-op? In any case, it seems much more practical to assume a special symbol to mark the start of the tape. $\endgroup$
    – reinierpost
    Apr 19 at 11:23
  • 1
    $\begingroup$ @reinierpost, this is similar to how a reference like Sipser's book described such Turing Machine. To quote the book "If M ever tries to move its head to the left off the left-hand end of the tape, the head stays in the same place for that move, even though the transition function indicates L." (where M is the Turing Machine and L indicated moving its head to the left. $\endgroup$
    – Russel
    Apr 19 at 12:58
  • $\begingroup$ another possibility is if you can increase the number of symbols but don't want to shift the contents, you can also add symbols for 0-at-left-end, 1-at-left-end, etc and the first step can overwrite the the first symbol with the -at-left-end version $\endgroup$
    – user253751
    Apr 19 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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