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:
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)
“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)
“One definition of man is “an intelligence served by organs.””
—Ralph Waldo Emerson (1803–1882)