Ph.D. Preliminary Oral Exam: Andrei Migunov

Andrei Migunov
Friday, November 5, 2021 - 1:00pm
Event Type: 

Randomness, Dimension, and Analog Computation

Analog computation is sometimes regarded as an archaic form of computation that was superseded by digital computation and the Turing model. However, analog computation never really disappeared, and the associated ideas have been preserved and revived in many ways. Claude Shannon's general purpose analog computer (GPAC) was initially conceived as a model of Bush's differential analyzer (Shannon, 1941). The GPAC model has been studied and revised since then, and a version of the GPAC has recently (Pouly, 2018) been shown to admit a universal element (universal for the class of all continuous functions). Moreover, chemical reaction networks (CRNs)-- another model of computation, which is equivalent to the GPAC -- have been shown to be Turing universal. This talk will discuss an analog analogue of the classical theory of randomness for infinite binary sequences (motivated by CRN computation), a means of measuring information content in analog computation (motivated by GPACs), as well as a new (but classical) characterization of a well-known refinement of randomness known as algorithmic dimension. This talk will then take a detour into the philosophy of science by way of the ideas of Paul Feyerabend and Evald Ilyenkov.

Committee: Jack Lutz (major professor), Pavan Aduri, Gianfranco Ciardo, James Lathrop, Andrew Miner, and Arthur Smith

Join on Zoom: Or, go to and enter meeting ID: 992 8182 6250  Join from dial-in phone line: Dial: +1 646 876 9923 or +1 301 715 8592 Meeting ID: 992 8182 6250