Definition of a TM accepting a word

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

• $C_{1}$ is the start configuration of $M$ on input $w$,

• Each $C_{i}$ yields $C_{i+1}$ , and

• $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.

There are two reasons to use this kind of definition:

• It is a formal way to define the run of the machine.

• 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:

• $C_1$ is the start configuration of $M$ on input $w$,

• 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.

StackExchange Computer Science Q#95419, answer score: 3