Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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

DOI: http://dx.doi.org/10.1090/S0002-9947-1973-0322920-7
PII: S 0002-9947(1973)0322920-7
Article copyright: © Copyright 1973 American Mathematical Society