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:
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)