Randomness and Dimension in Computational Learning and Analog Computation
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. We then 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), which obtains for this class of analog computers. We use these tools to investigate randomness properties of sequences of real numbers, which represent the sojourn times between chemical system state transitions. Finally, we discuss an analog version of the classical randomized complexity class BPP.
Committee: Jack Lutz (major professor), Pavan Aduri, Gianfranco Ciardo, James Lathrop, Andrew Miner and Arthur Smith
Join on Zoom: Please click this URL to start or join. https://iastate.zoom.us/j/96262150333
Or, go to https://iastate.zoom.us/join and enter meeting ID: 962 6215 0333