I try to understand something:
At Turing machine we have two stats: $q_{accept}$ and $q_{reject}$.

Now, if machine $M$ runs on word $w$ (I hope I write it right...) and the final configuration is: $C(w,q_t,\varepsilon )$,
and $q_t =Q-\{q_{accept},q_{reject}\}$.

Of course $M$ don't accept $w$ and don't reject $w$, but my question is:
We can say that $M$ Stops on $w$?

I try to look for an answer but I didn't found...

Thank you!


No, Turing machine are defined in a different way than finite-automata: they don't "stop" at the end of the input, they stop whenever they reach a final state $q\in F$. Usually, there are two final states, $q_{acc},q_{rej}$ – if the machine transitions to one of these final states it stops; but until then, it keeps running.

Therefore, $\delta(q,\cdot)$ must be defined for any $q\in Q\setminus F$ and and letter the head points on. This will tell us how the machine behaves when in the state $q_t$ (using your symbol, assuming it is not a final state; see below if it is).

regarding halting without accepting/rejecting: the answer is yes. If, say, $F=\{q_{acc},q_{rej}, q_{inconclusive}\}$, and the machine reached the third final state, we can say it neither accepted nor rejected, but it halts indeed since it reached a final state in $F$. Of course, $F$ can be as large as $Q$. It may make sense for computing other task than yes/no decision problems.

  • $\begingroup$ What is the "$\cdot$" symbol means? Thank you!! $\endgroup$ – Yoar Apr 14 '16 at 21:04
  • 1
    $\begingroup$ @Yoar I meant $\delta(q,b)$ for any state $q\in Q$ and any letter in the tape's alphabet $b\in \Gamma$. Just the standard definition of the transition function. $\endgroup$ – Ran G. Apr 14 '16 at 21:16

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.