0
$\begingroup$

enter image description here

So I'm lost on this one. We're given a turing machine and an initial tape. Tape is infinitely long in both ways, but all the blanks are taken out. The head is the leftmost nonblank. So the question is: If the Turing machine halts on this input, then give the output sequence; if it does not halt, then answer “does not halt” and why.

Following the turing machine it seems to halt after q1 since is the only operation.

Edit: and, if a state has only one operation such as does that mean it automatically should halt?

$\endgroup$
  • $\begingroup$ If all the blanks are taken out, how can there be a leftmost nonblank? $\endgroup$ – Tom Zych Dec 8 '18 at 16:36
  • 1
    $\begingroup$ I'm not sure. It's what the excercise said. To be exact: "The arrow indicates the initial position of the read/write head: the leftmost nonblank symbol. If the Turing machine halts on this input, then give the output sequence; if it does not halt, then answer “does not halt”. In either case, stating your answer is sufficient; you do not have to justify your answer" $\endgroup$ – iiiiiiiiiiiiiiiiiiiiiiiiiiiiii Dec 8 '18 at 16:51
  • 1
    $\begingroup$ You’d probably better explain the notation they’re using; it doesn’t make sense to me. Everyone makes up their own Turing machine notation, there’s no standard. $\endgroup$ – Tom Zych Dec 8 '18 at 17:01
  • $\begingroup$ so the "intial tape" could be 0 | _ | 1 | _ | _ | 1 .. etc. You don't know because they took the blanks out. The turing machine: <current state>, <written state>, <move R/L>. The box is a blank. For that matter, it does not make sense to me either. I tried to search for more explanation but it as you said, everyone has a different notation $\endgroup$ – iiiiiiiiiiiiiiiiiiiiiiiiiiiiii Dec 8 '18 at 17:05
  • $\begingroup$ I’m sorry but this seems like an unanswerable question to me. The machine definition doesn’t make sense without a notation definition. The stuff about the blanks being taken out doesn’t make much sense. If you were given this for a course, I’d go back to the instructor and ask them to clarify it. $\endgroup$ – Tom Zych Dec 8 '18 at 18:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.