Computability by probabilistic Turing machines

Santos, Eugene S.

doi:10.1090/S0002-9947-1971-0281555-3

Computability by probabilistic Turing machines
HTML articles powered by AMS MathViewer

by Eugene S. Santos

Trans. Amer. Math. Soc. 159 (1971), 165-184

DOI: https://doi.org/10.1090/S0002-9947-1971-0281555-3

PDF | Request permission

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

J. W. Carlyle, Reduced forms for stochastic sequential machines, J. Math. Anal. Appl. 7 (1963), 167–175. MR 180460, DOI 10.1016/0022-247X(63)90045-3
Kai Lai Chung, Markov chains with stationary transition probabilities, Die Grundlehren der mathematischen Wissenschaften, Band 104, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1960. MR 0116388, DOI 10.1007/978-3-642-49686-8
Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0124208
William Feller, An Introduction to Probability Theory and Its Applications. Vol. I, John Wiley & Sons, Inc., New York, N.Y., 1950. MR 0038583
Paul R. Halmos, Measure Theory, D. Van Nostrand Co., Inc., New York, N. Y., 1950. MR 0033869, DOI 10.1007/978-1-4684-9440-2
K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro, Computability by probabilistic machines, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, N.J., 1956, pp. 183–212. MR 0079550
Marvin L. Minsky, Computation: finite and infinite machines, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0356580

Probabilistic automata

6

Eugene S. Santos, Probabilistic Turing machines and computability, Proc. Amer. Math. Soc. 22 (1969), 704–710. MR 249221, DOI 10.1090/S0002-9939-1969-0249221-4

Some definitional suggestions for automata theory

1

On computable numbers, with an application to the entscheidungs problem

42

Introduction to mathematical probability

Vladeta Vučković, Basic theorems on Turing algorithms, Publ. Inst. Math. (Beograd) (N.S.) 1(15) (1961), 31–65 (1962). MR 204289
L. A. Zadeh, Fuzzy sets, Information and Control 8 (1965), 338–353. MR 219427, DOI 10.1016/S0019-9958(65)90241-X