Probabilistic Recursion Theory and Implicit Computational Complexity
Zuppiroli, Sara <1979>
Subject
INF/01 Informatica
Description
In this thesis we provide a characterization of
probabilistic computation in itself, from a recursion-theoretical
perspective, without reducing it to deterministic computation.
More specifically, we show that probabilistic computable functions, i.e., those functions which
are computed by Probabilistic Turing Machines (PTM), can be characterized by a natural generalization of Kleene's partial recursive functions which includes, among initial functions,
one that returns identity or successor with probability 1/2. We then prove
the equi-expressivity of the obtained algebra and the class of
functions computed by PTMs.
In the the second part of the thesis we
investigate the relations existing between our recursion-theoretical framework
and sub-recursive classes, in the spirit of Implicit Computational Complexity. More precisely,
endowing predicative recurrence with a random base function is proved
to lead to a characterization of polynomial-time computable
probabilistic functions.
Zuppiroli, Sara (2014) Probabilistic Recursion Theory and Implicit Computational Complexity, [Dissertation thesis], Alma Mater Studiorum Università di Bologna. Dottorato di ricerca in Informatica , 25 Ciclo. DOI 10.6092/unibo/amsdottorato/6723.