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
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 $ \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?)

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

Article copyright: © Copyright 1973 American Mathematical Society