The following is a quote from Sipser's "Introduction to the theory of computation"

A Turing machine $M$ accepts input $w$ if a sequence of configurations $C_{1}, C_{1}, \ldots , C_{k}$ exists, where

  1. $C_{1}$ is the start configuration of $M$ on input $w$,
  2. Each $C_{i}$ yields $C_{i+1}$ , and
  3. $C_{k}$ is an accepting configuration.

The "if a sequence of configurations $C_{1}, C_{1}, \ldots , C_{k}$ exists" is a bit confusing. This is a deterministic TM, so there is only one sequence of configurations for a given machine and word, right? For instance, wouldn't the following do as a definition?

A Turing machine $M$ accepts input $w$ if the state in the final configuration in $M$'s run on $w$ is an accepting state

Obviously, one has to formally define first what the run of a machine on a given word means.


1 Answer 1


There are two reasons to use this kind of definition:

  1. It is a formal way to define the run of the machine.
  2. It generalizes to the nondeterministic setting.

In the deterministic setting, an equivalent definition would be:

Define a (possibly finite) sequence $C_1,C_2,\ldots$ as follows:

  1. $C_1$ is the start configuration of $M$ on input $w$,
  2. For $i \geq 1$, $C_{i+1}$ is the unique configuration yielded by $C_i$, if such a configuration exists.

The machine $M$ accepts the input $w$ if the sequence is finite, and the last configuration is accepting.

This is not dramatically better than the quoted definition, and it doesn't generalize to the nondeterministic setting. It is a matter of taste which of the two to prefer.

  • $\begingroup$ Not better in terms of compactness, but more intuitive and unambiguous ("The sequence" as opposed to "A sequence"). Anyway, thanks for clarifying. $\endgroup$ Commented Jul 19, 2018 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.