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.
| Identifer | oai:union.ndltd.org:unibo.it/oai:amsdottorato.cib.unibo.it:6723 |
| Date | 15 September 2014 |
| Creators | Zuppiroli, Sara <1979> |
| Contributors | Dal Lago, Ugo |
| Publisher | Alma Mater Studiorum - Università di Bologna |
| Source Sets | Università di Bologna |
| Language | English |
| Detected Language | English |
| Type | Doctoral Thesis, PeerReviewed |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0016 seconds