Probabilistic Recursion Theory and Implicit Computational Complexity
Ugo Dal Lago, Sara Zuppiroli, Maurizio Gabbrielli · Scientific Annals of Computer Science · 2014
We show that probabilistic computable functions, i.e., those functions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural generalization of Church and Kleene's partial recursive functions.The obtained algebra, following Leivant, can be restricted so as to capture the notion of a polytime sampleable distribution, a key concept in average-case complexity and cryptography.