# 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

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.

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.

• Not better in terms of compactness, but more intuitive and unambiguous ("The sequence" as opposed to "A sequence"). Anyway, thanks for clarifying. – H.Rappeport Jul 19 '18 at 16:24