Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Computability by probabilistic Turing machines

Author: Eugene S. Santos
Journal: Trans. Amer. Math. Soc. 159 (1971), 165-184
MSC: Primary 94.45
MathSciNet review: 0281555
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In the present paper, the definition of probabilistic Turing machines is extended to allow the introduction of relative computability. Relative computable functions, predicates and sets are discussed and their operations investigated. It is shown that, despite the fact that randomness is involved, most of the conventional results hold in the probabilistic case. Various classes of ordinary functions characterizable by computable random functions are introduced, and their relations are examined. Perhaps somewhat unexpectedly, it is shown that, in some sense, probabilistic Turing machines are capable of computing any given function. Finally, a necessary and sufficient condition for an ordinary function to be partially recursive is established via computable probabilistic Turing machines.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 94.45

Retrieve articles in all journals with MSC: 94.45

Additional Information

Keywords: Probabilistic Turing machines, Turing machines, probabilistically computable functions, partially recursive functions, computable random functions, computable random sets, computable random predicates
Article copyright: © Copyright 1971 American Mathematical Society