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)

 
 

 

Probabilistic recursive functions


Author: Irwin Mann
Journal: Trans. Amer. Math. Soc. 177 (1973), 447-467
MSC: Primary 60B99; Secondary 02F27, 65C05
DOI: https://doi.org/10.1090/S0002-9947-1973-0322920-7
MathSciNet review: 0322920
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The underlying question considered in this paper is whether or not the purposeful introduction of random elements, effectively governed by a probability distribution, into a calculation may lead to constructions of number-theoretic functions that are not available by deterministic means. A methodology for treating this question is developed, using an effective mapping of the space of infinite sequences over a finite alphabet into itself. The distribution characterizing the random elements, under the mapping, induces a new distribution. The property of a distribution being recursive is defined. The fundamental theorem states that recursive distributions induce only recursive distributions. A function calculated by any probabilistic means is called $ \psi $-calculable. For a class of such calculations, these functions are recursive. Relative to Church's thesis, this leads to an extension of that thesis: Every $ \psi $-effectively calculable function is recursive. In further development, a partial order on distributions is defined through the concept of ``inducing.'' It is seen that a recursive atom-free distribution induces any recursive distribution. Also, there exist distributions that induce, but are not induced by, any recursive distribution. Some open questions are mentioned.


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

  • [1] Alonzo Church, An unsolvable problem of elementary number theory, Amer. J. Math. 58 (1936), 345-363. MR 1507159
  • [2] Martin Davis, Computability and unsolvability, McGraw-Hill, New York, 1958. MR 23 #A1525. MR 0124208 (23:A1525)
  • [3] 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)
  • [4] P. R. Halmos, Measure theory, Van Nostrand, Princeton, N. J., 1950. MR 11, 504. MR 0033869 (11:504d)
  • [5] S. C. Kleene, Introduction to metamathematics, Van Nostrand, Princeton, N. J., 1952. MR 14, 525. MR 0051790 (14:525m)
  • [6] J. R. Myhill, Criteria of constructability for real numbers, J. Symbolic Logic 18 (1953), 7-10. MR 14, 938. MR 0054549 (14:938e)
  • [7] H. G. Rice, Recursive real numbers, Proc. Amer. Math. Soc. 5 (1954), 784-791. MR 16, 104. MR 0063328 (16:104a)
  • [8] Raphael Robinson, (review) Rósza Peter, Rekursive Functionen, J. Symbolic Logic 16 (1951), 182. MR 0042357 (13:97f)
  • [9] Ernst Specker, Nicht Konstructive Beweisbare Sätze Der Analysis, J. Symbolic Logic 14 (1949), 145-158. MR 11, 151. MR 0031447 (11:151g)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 60B99, 02F27, 65C05

Retrieve articles in all journals with MSC: 60B99, 02F27, 65C05


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1973-0322920-7
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society