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?)

  • [1] J. W. Carlyle, Reduced forms for stochastic sequential machines, J. Math. Anal. Appl. 7 (1963), 167-175. MR 31 #4695. MR 0180460 (31:4695)
  • [2] K. L. Chung, Markov chains with stationary transition probabilities, Die Grundlehren der math. Wissenschaften, Band 104, Springer-Verlag, Berlin, 1960. MR 22 #7176. MR 0116388 (22:7176)
  • [3] M. Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill, New York, 1958. MR 23 #A1525. MR 0124208 (23:A1525)
  • [4] W. Feller, An introduction to probability theory and its applications. Vol. 1, Wiley, New York, 1950. MR 12, 424. MR 0038583 (12:424a)
  • [5] P. R. Halmos, Measure theory, Van Nostrand, Princeton, N. J., 1950. MR 11, 504. MR 0033869 (11:504d)
  • [6] K. de Leeuw, E. F. Moore, C. E. Shannon and N. Shapiro, Computability by probabilistic machines, Automata Studies, Ann of Math. Studies, no. 34, Princeton Univ. Press, Princeton, N. J., 1956, pp. 183-212. MR 18, 104. MR 0079550 (18:104a)
  • [7] M. Minsky, Computation: Finite and infinite machines, Prentice-Hall, Englewood Cliffs, N. J., 1967. MR 0356580 (50:9050)
  • [8] M. O. Rabin, Probabilistic automata, Information and Control 6 (1963), 230-245.
  • [9] E. S. Santos, Probabilistic Turing machines and computability, Proc. Amer. Math. Soc. 22 (1969), 704-710. MR 40 #2468. MR 0249221 (40:2468)
  • [10] D. Scott, Some definitional suggestions for automata theory, J. Comput. System Sci. 1 (1967), 187-212.
  • [11] A. M. Turing, On computable numbers, with an application to the entscheidungs problem, Proc. London Math. Soc. (2) 42 (1936), 230-265.
  • [12] J. V. Uspensky, Introduction to mathematical probability, McGraw-Hill, New York, 1937.
  • [13] V. Vukovic, Basic theorems on Turing algorithms, Publ. Inst. Math. 1 (15) (1961), 31-65. MR 0204289 (34:4133)
  • [14] L. A. Zadeh, Fuzzy sets, Information and Control 8 (1965), 338-353. MR 36 #2509. MR 0219427 (36:2509)

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

American Mathematical Society