Computation on Topological Algebras: Analog and Digital Paradigms

我的长期研究目标是开发一种通用的计算理论，*包括数字、模拟和混合模型。这项工作是理论上的，但在构建具有模拟和数字组件混合网络的“智能系统”方面具有*实际应用*。*背景：数字计算*计算模型存在两种主要范式：数字和模拟。这两种形式都处理*来自测量的无限数据，通常是实数。*在数字计算中，数据用符号表示。*在模拟计算中，数据用可以测量的物理量来表示。在混合计算中，这两个过程是结合在一起的。我过去的研究涉及将经典的(数字)可计算性理论推广到*实数，以及度量和拓扑代数。*已经研究了许多数字计算模型，例如Grzegzorczyk和Lacombe的模型，*Wehrauch的模型和跟踪可计算性的模型(Malcev，Tucker，Stoltenberg-Hansen)。约翰·塔克、我自己和我们的学生已经证明了其中许多*的等价性。*以上大部分都涉及数字计算模型。我们转向模拟计算。*背景：模拟计算*现代理论始于香农的GPAC(通用模拟计算机)，*由Pour-El、Moore、Costa、Bournez、Graca和其他人开发。*GPAC具有对实数(表示*物理量)执行基本运算的模块，通过用于实数流*(表示时间t的函数)的通道连接。Shannon通过一个代数微分方程组证明了GPAC可计算性等价于*可定义性。*论文[TZ07]为我们以后的工作奠定了基础。在这本书中，Tucker和我为具有连续实数流的模拟网络开发了一个*定点语义。*我的博士生Diogo Pocas扩展了Shannon的GPAC，包括*(1)一个额外的空间变量x和一个偏微分模块；以及*(2)一个“限制进程”模块。我们称这样的GPAC为“多元”。*长期目标*发展一套系统的计算理论，包括数字、模拟和*混合模型。*短期目标*虽然各种数字模型之间已证明了许多等价性，但在比较模拟和数字模型的优点方面仍有许多工作要做，例如*找到一个等同于跟踪可计算性的多变量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