@article{doi:10.1137/0206049,
    Abstract = {A probabilistic Turing machine is a Turing machine with the ability to make decisions based on the outcomes of unbiased coin tosses. The partial function computed by a probabilistic machine is defined by assigning to each input the output which occurs with probability greater than \$\frac{1}{2}\$. With this definition, only partial recursive functions are probabilistically computable. The run time and tape of probabilistic machines are defined. A palindrome-like language is described that can be recognized faster by one-tape probabilistic Turing machines than by one-tape deterministic Turing machines. It is shown that every nondeterministic machine can be simulated in the same space by a probabilistic machine with small error probability. Several classes of languages recognized probabilistically in polynomial time are defined and compared with \$NP\$.},
    Author = {Gill, John},
    EPrint = {https://doi.org/10.1137/0206049},
    File = {Computational Complexity of Probabilistic Turing Machines - gill1977.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {4},
    Pages = {675--695},
    Title = {Computational Complexity of Probabilistic Turing Machines},
    URL = {https://doi.org/10.1137/0206049},
    Volume = {6},
    Year = {1977},
    bdsk-url-1 = {https://doi.org/10.1137/0206049},
    date-added = {2023-09-16 10:04:00 +0200},
    date-modified = {2023-09-16 10:04:21 +0200},
    doi = {10.1137/0206049}
}

@article{doi:10.1137/0206049, Abstract = {A probabilistic Turing machine is a Turing machine with the ability to make decisions based on the outcomes of unbiased coin tosses. The partial function computed by a probabilistic machine is defined by assigning to each input the output which occurs with probability greater than \$\frac{1}{2}\$. With this definition, only partial recursive functions are probabilistically computable. The run time and tape of probabilistic machines are defined. A palindrome-like language is described that can be recognized faster by one-tape probabilistic Turing machines than by one-tape deterministic Turing machines. It is shown that every nondeterministic machine can be simulated in the same space by a probabilistic machine with small error probability. Several classes of languages recognized probabilistically in polynomial time are defined and compared with \$NP\$.}, Author = {Gill, John}, EPrint = {https://doi.org/10.1137/0206049}, File = {Computational Complexity of Probabilistic Turing Machines - gill1977.pdf}, Journal = {SIAM Journal on Computing}, Number = {4}, Pages = {675--695}, Title = {Computational Complexity of Probabilistic Turing Machines}, URL = {https://doi.org/10.1137/0206049}, Volume = {6}, Year = {1977}, bdsk-url-1 = {https://doi.org/10.1137/0206049}, date-added = {2023-09-16 10:04:00 +0200}, date-modified = {2023-09-16 10:04:21 +0200}, doi = {10.1137/0206049} }