|
|
|
|
non-deterministic Turing machine
|
(Definition)
|
|
|
The definition of a non-deterministic Turing machine is the same as the definition of a deterministic Turing machine except that is a relation, not a function. Hence, for any particular state and symbol, there may be multiple possible legal moves.
If
we say accepts if, when is the input, there is some finite sequence of legal moves such that is undefined on the state and symbol pair which results from the last move in the sequence and such that the final state is an element of . If does not accept then it rejects .
An alternative definition of a non-deterministic Turing machine is as a deterministic Turing machine with an extra one-way, read-only tape, the guess tape. Then we say accepts if there is any string such that, when is placed on the guess tape, accepts . We call a certificate for , and otherwise that it rejects . In some cases the guess tape is allowed to be two-way; this generates different time and space complexity classes than the one-way case (the one-way case is equivalent to the original
definition).
|
"non-deterministic Turing machine" is owned by Henry.
|
|
(view preamble)
Cross-references: equivalent, complexity classes, generates, string, one-way, final state, sequence, finite sequence, multiple, state, function, relation, deterministic Turing machine
There are 3 references to this entry.
This is version 3 of non-deterministic Turing machine, born on 2002-09-03, modified 2002-09-06.
Object id is 3416, canonical name is NonDeterministicTuringMachine.
Accessed 5871 times total.
Classification:
| AMS MSC: | 68Q05 (Computer science :: Theory of computing :: Models of computation ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|