paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Approximability in the GPAC

GPAC 中的可逼近性
LMCS vol.Volume 15, Issue 32019匹配度 1/10 · 该论文研究模拟计算模型 GPAC 的可近似性与极限模块,属于可计算性/形式语义理论,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接交集。仅“形式语义/理论形式化”这一点与用户对理论形式化的偏好有微弱关联。引用 0 inbox
Diogo Poças, Jeffery Zucker
crossref: 2026-09-10

AI 速览

一句话:扩展 GPAC,加入极限模块与流通道,使其能捕获 gamma 和 zeta 等非微分代数函数。

自然物理过程多由常微分或偏微分方程建模,模拟可计算性关注是否存在有效求解方式。Shannon 的通用模拟计算机(GPAC)是经典模拟计算模型,其能力由微分代数函数刻画,包含常微分方程初值问题的解,但缺少连续计算中期望的逼近性,不能生成非微分代数函数。本文扩展数据类型,令通道携带一般完备度量空间 X(如 C(R,R))上的信息;在原来的常数、加法、乘法、积分模块上加入连续或离散极限模块,定义 L-GPAC。该框架将模拟系统规格表述为连续数据流上算子的固定点。作者研究这些模拟系统及相关算子,并展示 gamma 函数、zeta 函数等经典不可生成函数可由 L-GPAC 捕获。

问题
GPAC 缺少可逼近性,无法生成非微分代数但可被其他计算模型近似计算的函数。
方法
用携带 X 上信息的流通道和连续或离散极限模块扩展 GPAC,定义 L-GPAC,并以连续数据流上算子的固定点刻画模拟系统。
评估
通过理论分析与示例表明 gamma 函数、zeta 函数等经典非 GPAC 可生成函数可在 L-GPAC 中捕获;摘要未涉及实验评估。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot761,
  title = {Approximability in the GPAC},
  author = {Diogo Poças and Jeffery Zucker},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 3},
  year = {2019},
  doi = {10.23638/lmcs-15(3:24)2019}
}