This thesis presents new domain-theoretic models for randomized algorithms. A randomized algorithm can use random bits from an oracle to control its computation. The possible random bits form a binary tree, where each random choice of a bit is a branching of the tree. The randomized algorithm then determines what the output should be for each branch. This idea forms the basis of our random choice functors. However, the functor only provides one half of the model. We must also show how multiple randomized algorithms can be combined or composed. This is where the monadic structure comes into play. If we wish to join multiple randomized algorithms to form one resulting algorithm, then we can run each algorithm in parallel, using the same random bits for each. Monads are used to add a computational effect to an existing semantic model. In order to work with models of the lambda calculus, it is important to work in a Cartesian closed category of domains, due to Lambek's theorem and Scott's corollary. Our first random choice monad is shown to be an endofunctor of the Cartesian closed category BCD. If we wish to add multiple computational effects, then we can compose monads as long as the monads enjoy a distributive law. It is shown that in the category BCD, our first random choice monad enjoys a distributive law with the lower powerdomain for nondeterminism. Two variations of the random choice monad are then given. The first variation has a distributive law with the convex powerdomain in the categories RB and FS, while the second variation has a distributive law with the upper powerdomain in BCD. We use the random choice monads to develop a new programming language, Randomized PCF. This extends the language PCF by adding in random choice, allowing for the programming of randomized algorithms. A full operational semantics is given for Randomized PCF, and a random choice monad is used to give it a mathematical model (denotational semantics). Finally, an implementation of Randomized PCF is developed, and the Miller-Rabin algorithm is implemented in Randomized PCF. / Tyler Barker
| Identifer | oai:union.ndltd.org:TULANE/oai:http://digitallibrary.tulane.edu/:tulane_51500 |
| Date | January 2016 |
| Contributors | Barker, Tyler (author), Mislove, Michael (Thesis advisor), School of Science & Engineering Mathematics (Degree granting institution) |
| Source Sets | Tulane University |
| Detected Language | English |
| Type | Text |
| Format | electronic |
| Rights | Embargo |
Page generated in 0.0021 seconds