Probabilistic recursive functions

Author:
Irwin Mann

Journal:
Trans. Amer. Math. Soc. **177** (1973), 447-467

MSC:
Primary 60B99; Secondary 02F27, 65C05

MathSciNet review:
0322920

Full-text PDF Free Access

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), no. 2, 345–363. MR**1507159**, 10.2307/2371045**[2]**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****[3]**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****[4]**Paul R. Halmos,*Measure Theory*, D. Van Nostrand Company, Inc., New York, N. Y., 1950. MR**0033869****[5]**Stephen Cole Kleene,*Introduction to metamathematics*, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR**0051790****[6]**John Myhill,*Criteria of constructibility for real numbers*, J. Symbolic Logic**18**(1953), 7–10. MR**0054549****[7]**H. G. Rice,*Recursive real numbers*, Proc. Amer. Math. Soc.**5**(1954), 784–791. MR**0063328**, 10.1090/S0002-9939-1954-0063328-5**[8]**Raphael M. Robinson,*Arithmetical definability of field elements*, J. Symbolic Logic**16**(1951), 125–126. MR**0042357****[9]**Ernst Specker,*Nicht konstruktiv beweisbare Sätze der Analysis*, J. Symbolic Logic**14**(1949), 145–158 (German). MR**0031447**

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:
http://dx.doi.org/10.1090/S0002-9947-1973-0322920-7

Article copyright:
© Copyright 1973
American Mathematical Society