RandomTuringMachine 2002-09-06 13:49:16 2005-05-02 14:47:47 Definition one sided error two sided error one-sided error two-sided error minimal error % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here %\PMlinkescapeword{theory} 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 \emph{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 \emph{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 \emph{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 \emph{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.