5
$\begingroup$

I am pretty new to Turing Machines and am trying to figure something out. So let's say I have a tape with input 

0 0 1 0 0 1

The language is twice as many 0's than 1's. So first time through, I will mark an X on the first 1 I find. Then when I am heading back to the start of the tape, how do I know when to stop? Can you "run" off the left hand side of the tape?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Exactly what definition of Turing machines are you using? Some authors have the tape be infinite in both directions; some have it infinite only to the right; some authors have it infinite only to the right with a special marker for the left end; some authors probably do something else. The answer to your question would be different in all of these cases. $\endgroup$ – David Richerby Apr 3 '16 at 17:42
  • $\begingroup$ Well in my book it says "If M( the machine) ever tries to move its head to the left off the left-hand end of the top, the head stays in the same place for that move, even though the transition function indicates L." $\endgroup$ – bob afro Apr 3 '16 at 18:34
4
$\begingroup$

for above example before you start your tape is like this ($e$ means empty and right side of $>$ is block of tape that you are reading it)

e>001001e

as you said you should first mark $X$ on the first $1$ and it become like this

e00>X001e

now you should clear two zeros because the number of zeros is twice of the number of ones. you can clear the first two zero of the tape. go to the beginning of the tape like this (when you read $e$ it means you are at the beginning of tape and go one step to the right so that marker be over the first symbol of tape)

e>00X001e

now you can mark two zeros with $X$ or $Y$ it does't matter but for readability it's better to mark it with another symbol 

eY>YX001e

now go back to the beginning of tape

e>YYX001e

now it's like a for loop you should do this until there is no $1$ on the tape. when you got end of the tape while searching for $1$ it means that you ran out of ones. you should check two cases

  1. is number of ones less than twice of zeros
  2. is number of ones greater than twice of zeros

if the first case happens while you are searching for zeros you cant find two of them and you got to the end of tape like below

e>00010111e

become

eYYYXYXY1>e

so in this case you should reject the string.

and checking the second case is in the last step when you ran out of ones you should check that is there any zeros one the tape right now. if you found any zero you should reject.

remember never write empty over $0$ or $1$ because when you reach empty it means you are at the end or the beginning of the tape.

based on definition of Turing Machine you can run off the left hand side or not. there are Turing Machines that their tapes are infinite at the right side and finite at the left side so you can run off at the left side. but standard Turing Machine is infinite at both site so you can run off at the left hand side.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you so much. This helped me understand it soooooooo much better now. Seriously, thanks for taking the time to explain it. $\endgroup$ – bob afro Apr 3 '16 at 5:03
  • $\begingroup$ your welcome @bobafro $\endgroup$ – Karo Apr 3 '16 at 5:04

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.