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 -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.

**[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)**

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