0
$\begingroup$

what do the tape contents of Turing machine look like after halting? Are there empty symbols after the qaccept or reject?

$\endgroup$
1
  • 3
    $\begingroup$ The tape contents is completely arbitrary — the tape is left as is when the Turing machine halts. The states $q_{\mathrm{accept}},q_{\mathrm{reject}}$ that you mention do not appear on the tape, so your question doesn't make much sense to me. $\endgroup$ Apr 22 at 13:56
1
$\begingroup$

The tape contains whatever the Turing machine wants it to. There's no rule that says it has to have certain contents. It must have a finite number of symbols, and all the spaces outside of a finite region must be blank.

$\endgroup$
4
  • $\begingroup$ I am not an expert at this. But if TM is solving a Decision Problem, then I think it okay if tape contents are arbitrary. But for function problems, the TM's tape contents might represent the optimal function output. Am I making sense? $\endgroup$ Sep 22 at 8:47
  • $\begingroup$ @InuyashaYagami Yes, they should, if the TM is solving a function problem. If it's solving a decision problem then it should also halt with a yes or no output on the tape. $\endgroup$
    – user253751
    Sep 22 at 8:55
  • $\begingroup$ For decision problem, TM do not need to output yes or no on the tape. It can simply be in qaccept or qreject state right? $\endgroup$ Sep 22 at 9:26
  • $\begingroup$ @InuyashaYagami Sure... that is equivalent, because we can edit the TM so it writes a 1 in qaccept state and writes a 0 in qreject state and then goes to a final state. Likewise if we have a TM that writes 1 or 0 and then halts, we can edit it so it goes to an accept or reject state depending on whether the thing it wrote was a 1 or a 0 $\endgroup$
    – user253751
    Sep 22 at 9:45

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.