Computation on Topological Algebras: Analog and Digital Paradigms

拓扑代数计算：模拟和数字范式

• 批准号: RGPIN-2019-07063
• 负责人: Zucker, Jeffery
• 金额: $ 2.48万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=739287
• 关键词: Computation; Topological; Algebras; Analog; Digital

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 theory of such systems is clear.  Such systems offer Canadian industry an agenda for high-tech developments.  The design of such complex systems requires a good theoretical framework, which this project aims to offer.

我的长期研究目标是发展一种通用的计算理论，包括数字、模拟和混合模型。这项工作是理论性的，但在模拟和数字组件混合网络的“智能系统”的构建中具有实际应用。背景资料：数字计算计算模型有两种主要范式：数字和模拟。这两种形式都处理源自测量的无限数据，通常是真实的数字。在数字计算中，数据用符号表示。 在模拟计算中，数据由可测量的物理量表示。 在混合计算中，这两个过程被结合在一起。我过去的研究涉及经典（数字）可计算性理论的推广到真实的数字，度量和拓扑代数。 人们已经研究了许多数字计算模型，例如Grzegzorczyk和拉科姆贝、Weihrauch和跟踪可计算性（Malcev、Tucker、Stoltenberg-Hansen）的模型，其中许多模型的等价性已经被John Tucker、我和我们的学生证明。 上面的大部分都涉及到数字计算模型，我们转向模拟计算。背景资料：模拟计算现代理论始于香农的GPAC（“通用模拟计算机”），由Pour-El，摩尔，Costa，Bournez，Graca和其他人开发。GPAC具有用于对真实的数（表示物理量）执行初等运算的模块，这些模块由真实的数流（表示时间t的函数）的通道连接。 该文件[TZ 07]是开创性的我们后来的工作。在它塔克和我开发了一个不动点语义模拟网络连续流的reals。我的博士生Diogo Pocas扩展了Shannon的GPAC，包括（1）一个额外的空间变量x和一个偏微分模块;（2）一个“极限过程”模块。我们称这样的GPAC为“多变量”。长期目标发展系统的计算理论，包括数字，模拟和混合模型。 短期目标（1）虽然已经证明了各种数字模型之间的许多等价性，但在比较模拟和数字模型的优势方面还有很多工作要做，例如找到一个与跟踪可计算性等价的多变量GPAC版本。(2)使用（1）中的结果来公式化一个广义丘奇-图灵命题，它既适用于模拟系统，也适用于数字系统。影响鉴于“智能系统”的日益重要性和普遍性，将模拟和数字组件纳入混合网络，此类系统的系统理论的必要性是显而易见的。此类系统为加拿大工业提供了高科技发展议程。设计如此复杂的系统需要一个良好的理论框架，而本项目旨在提供这一框架。