Probabilistic Recursion Theory and Implicit Computational Complexity

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.
Documenti full-text disponibili:
Documento PDF (English) - Richiede un lettore di PDF come Xpdf o Adobe Acrobat Reader
Download (763kB) | Anteprima


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.

Tipologia del documento
Tesi di dottorato
Zuppiroli, Sara
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Settore disciplinare
Settore concorsuale
Parole chiave
Probabilistic Recursion Theory, Implicit Computational Complexity, Probabilistic Turing Machine
Data di discussione
15 Settembre 2014

Altri metadati

Statistica sui download

Gestione del documento: Visualizza la tesi