Probabilistic recursive functions

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.