Computability by probabilistic Turing machines
HTML articles powered by AMS MathViewer
- by Eugene S. Santos PDF
- Trans. Amer. Math. Soc. 159 (1971), 165-184 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 M. O. Rabin, Probabilistic automata, Information and Control 6 (1963), 230-245.
- 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 D. Scott, Some definitional suggestions for automata theory, J. Comput. System Sci. 1 (1967), 187-212. A. M. Turing, On computable numbers, with an application to the entscheidungs problem, Proc. London Math. Soc. (2) 42 (1936), 230-265. J. V. Uspensky, Introduction to mathematical probability, McGraw-Hill, New York, 1937.
- 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
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 159 (1971), 165-184
- MSC: Primary 94.45
- DOI: https://doi.org/10.1090/S0002-9947-1971-0281555-3
- MathSciNet review: 0281555