Computation on Topological Algebras: Analog and Digital Paradigms

点击翻译按钮获取中文摘要

My long-term research goal is to develop a generalized theory of computation, ***incorporating digital, analog and hybrid models. This work is theoretical, but has ***practical applications in the construction of "smart systems" with hybrid networks***of analog and digital components.******Background: Digital computation***Computation models exist in two main paradigms: digital and analog. Both forms process ***infinite data, typically real numbers, originating from measurements.***In digital computation, the data are represented symbolically. ***In analog computation, the data are represented by physical quantities which can be measured. ***In hybrid computation, both processes are combined.******My past research involved the generalization of classical (digital) computability theory to the ***real numbers, and to metric and topological algebras. ******Many models of digital computation have been studied, e.g. those of Grzegzorczyk and Lacombe, ***Weihrauch, and tracking computability (Malcev, Tucker, Stoltenberg-Hansen). The equivalence of many ***of these has been proved by (among others) John Tucker, myself and our students. ******Most of the above has involved digital computation models. We turn to analog computation.******Background: Analog computation***The modern theory begins with Shannon's GPAC ("General Purpose Analog Computer"),***as developed by Pour-El, Moore, Costa, Bournez, Graca and others.***The GPAC has modules for performing elementary operations on real numbers (representing***physical quantities), connected by channels for streams of real numbers ***(representing functions of time t). Shannon proved GPAC computability to be equivalent to ***definability by a system of algebraic differential equations.*******The paper [TZ07] was seminal for our later work. In it Tucker and I developed a ***fixed point semantics for analog networks with continuous streams of reals.******My PhD student Diogo Pocas extended Shannon's GPAC by including ***(1) an extra space variable x with a partial differential module; and ***(2) a "limiting process" module. We call such GPACs "multivariate".******Long term goal***Developing a systematic theory of computation, incorporating digital, analog and ***hybrid models.*******Short term goals ***(1) Although many equivalences have been proved among various digital models,***much remains to be done in comparing strengths of analog and digital models, e.g***finding a version of the multivariate GPAC equivalent to tracking computability.******(2) Use the results in (1) to formulate a Generalized Church-Turing Thesis, applicable***to analog as well as digital systems.******Impact***Given the increasing importance and ubiquity of "smart systems", incorporating***hybrid networks with analog and digital components, the necessity for a systematic