# 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. Jul 19 '18 at 16:24