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).