Definition
A nondeterministic Turing machine can be formally defined as a 6-tuple, where
- is a finite set of states
- is a finite set of symbols (the tape alphabet)
- is the initial state
- is the blank symbol
- is the set of accepting states
- is a relation on states and symbols called the transition relation.
The difference with a standard (deterministic) Turing machine is that for those, the transition relation is a function (the transition function).
Configurations and the yields relation on configurations, which describes the possible actions of the Turing machine given any possible contents of the tape, are as for standard Turing machines, except that the yields relation is no longer single-valued. The notion of string acceptance is unchanged: a non-deterministic Turing machine accepts a string if, when the machine is started on the configuration in which the tape head is on the first character of the string (if any), and the tape is all blank otherwise, at least one of the machine's possible computations from that configuration puts the machine into a state in . (If the machine is deterministic, the possible computations are the prefixes of a single, possibly infinite, path.)
Read more about this topic: Non-deterministic Turing Machine
Famous quotes containing the word definition:
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)