Confusion about definition of languages accepted by Turing Machine, very basic question I'm studying for an upcoming exam and my book gives the following definition:
Let $M$ be a Turing machine, then the accepted language $T(M)$ of $M$ is defined as $T(M) = \{x \in \Sigma^* \mid z_0 x \vdash^* \alpha z \beta; \alpha, \beta \in \Gamma^*; z \in E\}$.
As a side note, $\vdash$ denotes the transition from one configuration of the TM to the next, and the $^*$ denotes an arbitrary number of applications of this relation.
What I'm confused about is that under this definition of acceptance, I only have to enter the end state once and even if I leave it, the word would be accepted, or I could loop in this end state. In push down automata or regular automata, we do not have this problem as we move through the word sequentially from beginning to very end, especially in push down automata where the stack is separated from the input word.
Now I read in most other definitions, additionally to ending up in an end state, the Turing machine must also halt, meaning that it must end in a state that has no transitions. Although I'm not sure what this would mean for deterministic Turing machines as they have to have transitions for all configurations of the machine.
To wrap it up:
Question 1: Is halting required? Is it a useful property for accepting languages or is there a reason the definition was given as is?
Question 2: How would you define &quot;halting&quot; for deterministic Turing machines?
Even in a deterministic Turing machine, the transition function $\delta$ may be a partial function i.e. there can be pairs of states and tape symbols for which the transition function is not defined. If the Turing machine is in state $z$ and reads symbol $\alpha$ and $\delta(z,\alpha)$ is not defined then it halts. Usually the accepting states $E$ are implemented by creating states for which the transition function is undefined for all inputs i.e. the Turing machine will always halt once it enters a state $z \in E$, regardless of the symbol it reads from the tape. You may also have other halting states, but if the machine halts in a state $z \notin E$ then it has rejected the input string.