Randomness and dimension in computational learning and analog computation
Date
2022-08
Authors
Migunov, Andrei Nikolai
Major Professor
Advisor
Lutz, Jack H
Aduri, Pavan
Miner, Andrew
Lathrop, James
Ciardo, Gianfranco
Smith, Arthur
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract
In this thesis, we study the notion of algorithmic randomness and its refinement, algorithmic dimension, in the contexts of learning theory and analog computation. Zaffora Blando (2021) recently characterized algorithmic randomness in terms of computable learning functions. We extend this work to characterize the Hausdorff and computable dimensions in terms of learning functions, and we give an upper bound on the algorithmic dimension. Having worked with randomness and dimension in the traditional setting, we move on to study randomness in the analog framework. We discuss a specific form of analog computation known as stochastic chemical reaction networks (SCRNs) and review the theory of randomness due to Huang et al. (2019) that obtains for this class of analog computers. We use these tools to discuss randomness properties of sequences of real numbers that represent the sojourn times between chemical system state transitions. Finally, we discuss an analog version of the classical randomized complexity class BPP.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
dissertation