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 "halting" for deterministic Turing machines?

  • 1
    $\begingroup$ Some definitions of Turing machines (check your book!) state that accepting states can't have movements. Trouble is that if there are $N$ texts definining Turing machines, they have $N + 1$ subtly different definitions (can/can not write blanks, can/can not move from an accepting state, tape start but no end/tape infinite in both directions, basic model is deterministic or nondeterministic, ...). It doesn't really matter, as they are all (easily, check your text) proven equivalent. $\endgroup$ – vonbrand Jul 20 at 17:46

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.

| cite | improve this answer | |
  • $\begingroup$ That makes sense and it's what I thought! But for some reason we seem to have defined it differently. We defined $\delta$ as a function and not a partial function. For nondeterministic Turing machines we defined $\textrm{range}(\delta) = \mathcal{P}(Z \times \Gamma \times \{L, R, N\})$, so that for nondeterministic machines, $\emptyset$ instead of undefined stands for no transition. Under the definition I gave, am I correct that halting is not required and that input is accepted if we keep looping in $z \in E$ or even leave $z$ and halt in $z' \not\in E$, as long as we entered $z$ once? $\endgroup$ – Niki Jul 19 at 18: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.