Later we will reconsider the effect of nondeterminism in practical situations,
so we need to add some comments. As always, nondeterminism can be seen as a
choice between alternatives. This can be visualized as a decision tree (Figure
10.15).
Figure 10.14
Figure 10.15
The width of such a configuration tree depends on the branching factor, that
is, the number of options available on each move. If k denotes the maximum
branching, then
is the maximum number of configurations that can exist after n moves.
For later purposes, it is necessary to elaborate on the definition of language
acceptance and also include the membership issue.
Definition 10.3
A nondeterministic Turing machine M is said to accept a language L if, for
all w ∈ L, at least one of the possible configurations accepts w. There may be
branches that lead to nonaccepting configurations, while some may put the
machine into an infinite loop. But these are irrelevant for acceptance.