PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
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 $\delta$ is a relation, not a function. Hence, for any particular state and symbol, there may be multiple possible legal moves.

If $S\in\Gamma^+$ we say $T$ accepts $S$ if, when $S$ is the input, there is some finite sequence of legal moves such that $\delta$ 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 $F$ . If $T$ does not accept $S$ then it rejects $S$ .

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 $T$ accepts $S$ if there is any string $c(S)$ such that, when $c(S)$ is placed on the guess tape, $T$ accepts $S$ . We call $c(S)$ a certificate for $S$ , and otherwise that it rejects $S$ . 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 | get metadata)

View style:

See Also: Turing machine

Also defines:  certificate
Log in to rate this entry.
(view current ratings)

Cross-references: equivalent, complexity classes, generates, string, one-way, element, final state, sequence, finite sequence, multiple, state, function, relation, deterministic Turing machine
There are 6 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 7261 times total.

Classification:
AMS MSC68Q05 (Computer science :: Theory of computing :: Models of computation )

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)