一句话:扩展 GPAC,加入极限模块与流通道,使其能捕获 gamma 和 zeta 等非微分代数函数。
自然物理过程多由常微分或偏微分方程建模,模拟可计算性关注是否存在有效求解方式。Shannon 的通用模拟计算机(GPAC)是经典模拟计算模型,其能力由微分代数函数刻画,包含常微分方程初值问题的解,但缺少连续计算中期望的逼近性,不能生成非微分代数函数。本文扩展数据类型,令通道携带一般完备度量空间 X(如 C(R,R))上的信息;在原来的常数、加法、乘法、积分模块上加入连续或离散极限模块,定义 L-GPAC。该框架将模拟系统规格表述为连续数据流上算子的固定点。作者研究这些模拟系统及相关算子,并展示 gamma 函数、zeta 函数等经典不可生成函数可由 L-GPAC 捕获。
Most of the physical processes arising in nature are modeled by either ordinary or partial differential equations. From the point of view of analog computability, the existence of an effective way to obtain solutions of these systems is essential. A pioneering model of analog computation is the General Purpose Analog Computer (GPAC), introduced by Shannon as a model of the Differential Analyzer and improved by Pour-El, Lipshitz and Rubel, Costa and Gra\c{c}a and others. Its power is known to be characterized by the class of differentially algebraic functions, which includes the solutions of initial value problems for ordinary differential equations. We address one of the limitations of this model, concerning the notion of approximability, a desirable property in computation over continuous spaces that is however absent in the GPAC. In particular, the Shannon GPAC cannot be used to generate non-differentially algebraic functions which can be approximately computed in other models of computation. We extend the class of data types using networks with channels which carry information on a general complete metric space $X$; for example $X=C(R,R)$, the class of continuous functions of one real (spatial) variable. We consider the original modules in Shannon's construction (constants, adders, multipliers, integrators) and we add \emph{(continuous or discrete) limit} modules which have one input and one output. We then define an L-GPAC to be a network built with $X$-stream channels and the above-mentioned modules. This leads us to a framework in which the specifications of such analog systems are given by fixed points of certain operators on continuous data streams. We study these analog systems and their associated operators, and show how some classically non-generable functions, such as the gamma function and the zeta function, can be captured with the L-GPAC.