Computation on Topological Algebras: Analog and Digital Paradigms

我的长期研究目标是发展一种广义的计算理论，结合数字、模拟和混合模型。这项工作是理论上的，但在构建具有模拟和数字组件混合网络的“智能系统”方面具有实际应用。******背景：数字计算***计算模型主要存在两种范式：数字和模拟。这两种形式处理无限数据，通常是实数，源自测量。在数字计算中，数据用符号表示。在模拟计算中，数据用可测量的物理量表示。在混合计算中，这两个过程是结合在一起的。******我过去的研究涉及将经典（数字）可计算性理论推广到***实数，以及度量和拓扑代数。******已经研究了许多数字计算模型，例如Grzegzorczyk和Lacombe， ***Weihrauch和跟踪可计算性（Malcev, Tucker, Stoltenberg-Hansen）。约翰·塔克（John Tucker）、我本人和我们的学生（以及其他人）已经证明了其中许多的等价性。******以上大部分都涉及到数字计算模型。我们转向模拟计算。******背景：模拟计算***现代理论始于Shannon的GPAC（“通用模拟计算机”），***由Pour-El， Moore, Costa, Bournez， Graca等人开发。GPAC具有对实数（表示***物理量）执行基本运算的模块，通过通道连接实数流（表示时间t的函数）。香农用一个代数微分方程组证明了GPAC的可计算性等价于***的可定义性。*******这篇论文[TZ07]对我们后来的工作产生了重大影响。在这本书中，塔克和我为具有连续实数流的模拟网络开发了一个不动点语义。******我的博士生Diogo Pocas扩展了Shannon的GPAC，包括***(1)一个额外的空间变量x与偏微分模块；而***(2)为“限位过程”模块。我们称这种gpac为“多元”。******长期目标***发展一个系统的计算理论，结合数字，模拟和***混合模型。*******短期目标***(1)尽管在各种数字模型中已经证明了许多等效性，但在比较模拟模型和数字模型的优势方面仍有许多工作要做，例如***找到一个与跟踪可计算性等效的多变量GPAC版本。******(2)利用(1)的结果，建立一个广义的丘奇-图灵论题，适用于模拟系统和数字系统。******影响***鉴于越来越重要和无处不在的“智能系统”，结合***混合网络与模拟和数字组件，需要一个系统的

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