PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
random Turing machine (Definition)

A random Turing machine is defined the same way as a non-deterministic 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 non-deterministic 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 $ \operatorname{Prob}_T(x)$ be the probability that $ T$ halts in an accepting state when the input is $ x$.

A positive one-sided error machine is said to accept $ x$ if $ \operatorname{Prob}_T(x)\geq\frac{1}{2}$ and to reject $ x$ if $ \operatorname{Prob}_T(x)=0$. A negative one-sided error machine accepts $ x$ if $ \operatorname{Prob}_T(x)=1$ and rejects $ x$ if $ \operatorname{Prob}_T(x)\leq\frac{1}{2}$. So a single run of a positive one-sided error machine never misleadingly accepts but may misleadingly reject, while a single run of a negative one-sided error machine never misleadingly rejects.

The definition of a positive one-sided error machine is stricter than the definition of a non-deterministic machine, since a non-deterministic machine rejects when there is no certificate and accepts when there is at least one, while a positive one-sided error machine requires that half of all possible guess inputs be certificates.

A two-sided error machine accepts $ x$ if $ \operatorname{Prob}_T(x)\geq\frac{2}{3}$ and rejects $ x$ if $ \operatorname{Prob}_T(x)\leq\frac{1}{3}$.

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 $ x$ if $ \operatorname{Prob}_T(x)>\frac{1}{2}$ and rejects $ x$ if $ \operatorname{Prob}_T(x)<\frac{1}{2}$.

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 $ x$ 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) one-sided 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 Church-Turing 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.



"random Turing machine" is owned by Henry.
(view preamble)

View style:

Also defines:  one sided error, two sided error, one-sided error, two-sided error, minimal error

Cross-references: types, point, functions, Turing machine, in other words, sequence, addition, complexity classes, certificate, negative, positive, state, right, multiple, non-deterministic Turing machine
There is 1 reference to this entry.

This is version 2 of random Turing machine, born on 2002-09-06, modified 2005-05-02.
Object id is 3430, canonical name is RandomTuringMachine.
Accessed 4854 times total.

Classification:
AMS MSC68Q10 (Computer science :: Theory of computing :: Modes of computation )

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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