Probabilistic recursive functions
Trans. Amer. Math. Soc. 177 (1973), 447-467
Primary 60B99; Secondary 02F27, 65C05
Full-text PDF Free Access
Similar Articles |
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 -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 -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.
Church, An Unsolvable Problem of Elementary Number Theory,
Amer. J. Math. 58 (1936), no. 2, 345–363. MR
Davis, Computability and unsolvability, McGraw-Hill Series in
Information Processing and Computers, McGraw-Hill Book Co., Inc., New
York-Toronto-London, 1958. MR 0124208
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
R. Halmos, Measure Theory, D. Van Nostrand Company, Inc., New
York, N. Y., 1950. MR 0033869
Cole Kleene, Introduction to metamathematics, D. Van Nostrand
Co., Inc., New York, N. Y., 1952. MR 0051790
Myhill, Criteria of constructibility for real numbers, J.
Symbolic Logic 18 (1953), 7–10. MR 0054549
G. Rice, Recursive real numbers, Proc. Amer. Math. Soc. 5 (1954), 784–791. MR 0063328
M. Robinson, Arithmetical definability of field elements, J.
Symbolic Logic 16 (1951), 125–126. MR 0042357
Specker, Nicht konstruktiv beweisbare Sätze der Analysis,
J. Symbolic Logic 14 (1949), 145–158 (German). MR 0031447
- Alonzo Church, An unsolvable problem of elementary number theory, Amer. J. Math. 58 (1936), 345-363. MR 1507159
- Martin Davis, Computability and unsolvability, McGraw-Hill, New York, 1958. MR 23 #A1525. MR 0124208 (23:A1525)
- 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)
- P. R. Halmos, Measure theory, Van Nostrand, Princeton, N. J., 1950. MR 11, 504. MR 0033869 (11:504d)
- S. C. Kleene, Introduction to metamathematics, Van Nostrand, Princeton, N. J., 1952. MR 14, 525. MR 0051790 (14:525m)
- J. R. Myhill, Criteria of constructability for real numbers, J. Symbolic Logic 18 (1953), 7-10. MR 14, 938. MR 0054549 (14:938e)
- H. G. Rice, Recursive real numbers, Proc. Amer. Math. Soc. 5 (1954), 784-791. MR 16, 104. MR 0063328 (16:104a)
- Raphael Robinson, (review) Rósza Peter, Rekursive Functionen, J. Symbolic Logic 16 (1951), 182. MR 0042357 (13:97f)
- Ernst Specker, Nicht Konstructive Beweisbare Sätze Der Analysis, J. Symbolic Logic 14 (1949), 145-158. MR 11, 151. MR 0031447 (11:151g)
Retrieve articles in Transactions of the American Mathematical Society
Retrieve articles in all journals
© Copyright 1973
American Mathematical Society