Probabilistic recursive functions
HTML articles powered by AMS MathViewer
- by Irwin Mann PDF
- Trans. Amer. Math. Soc. 177 (1973), 447-467 Request permission
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
- Alonzo Church, An Unsolvable Problem of Elementary Number Theory, Amer. J. Math. 58 (1936), no. 2, 345–363. MR 1507159, DOI 10.2307/2371045
- 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
- 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
- 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
- Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- John Myhill, Criteria of constructibility for real numbers, J. Symbolic Logic 18 (1953), 7–10. MR 54549, DOI 10.2307/2266321
- H. G. Rice, Recursive real numbers, Proc. Amer. Math. Soc. 5 (1954), 784–791. MR 63328, DOI 10.1090/S0002-9939-1954-0063328-5
- Raphael M. Robinson, Arithmetical definability of field elements, J. Symbolic Logic 16 (1951), 125–126. MR 42357, DOI 10.2307/2266685
- Ernst Specker, Nicht konstruktiv beweisbare Sätze der Analysis, J. Symbolic Logic 14 (1949), 145–158 (German). MR 31447, DOI 10.2307/2267043
Additional Information
- © Copyright 1973 American Mathematical Society
- 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