Computability by Probabilistic Turing Machines

Open Access
Publisher Website
Google Scholar
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.

This publication has 6 references indexed in Scilit: