A random Turing machine is defined the same way as a nondeterministic Turing machine, but with different rules governing when it accepts or rejects. Whenever there are multiple legal moves, instead of always guessing right, a random machine selects one of the possible moves at random.
As with nondeterministic machines, this can also be viewed as a deterministic machine with an extra input, which corresponds to the random selections.
There are several different ways of defining what it means for a random Turing machine to accept or reject an input. Let
be the probability that halts in an accepting state when the input is .
A positive onesided error machine is said to accept if
and to reject if
. A negative onesided error machine accepts if
and rejects if
. So a single run of a positive onesided error machine never misleadingly accepts but may misleadingly reject, while a single run of a negative onesided error machine never misleadingly rejects.
The definition of a positive onesided error machine is stricter than the definition of a nondeterministic machine, since a nondeterministic machine rejects when there is no certificate and accepts when there is at least one, while a positive onesided error machine requires that half of all possible guess inputs be certificates.
A twosided error machine accepts if
and rejects if
.
The constants in any of the definitions above can be adjusted, although this will affect the time and space complexity classes.
A minimal error machine accepts if
and rejects if
.
One additional variant defines, in addition to accepting states, rejecting states. Such a machine is called zero error if on at least half of all inputs it halts in either an accepting or a rejecting state. It accepts if there is any sequence of guesses which causes it to end in an accepting state, and rejects if there is any sequence of guesses which causes it to end in a rejecting state. In other words, such a machine is never wrong when it provides an answer, but does not produce a decisive answer on all input. The machine can
emulate a positive (resp. negative) onesided error machine by accepting (resp. rejecting) when the result is indecisive.
It is a testament to the robustness of the definition of the Turing machine (and the ChurchTuring thesis) that each of these definitions computes the same functions as a standard Turing machine. The point of defining all these types of machines is that some are more efficient than others, and therefore they define different time and space complexity classes.
