Probabilistic Recursion Theory and Implicit Computational Complexity (Long Version)

Ugo Dal Lago, Sara Zuppiroli

We show that probabilistic computable functions, i.e., those functions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural gen…