paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Computation by infinite descent made explicit

显式化的无穷递降计算
LMCS vol.Volume 22, Issue 22026匹配度 1/10 · 该论文属于纯证明论与范畴论基础研究,虽涉及形式化验证,但未与LLM/Agent、静态分析、浮点或贝叶斯程序分析交叉,与用户当前研究问题几乎无关。引用 0 inbox
Sebastian Enqvist
crossref: 2026-09-10

AI 速览

一句话:提出显式标注序数变量的非良基证明系统,证明有效证明可计算,并导出规范化与范畴模型。

本文研究带归纳与余归纳定义的直觉主义逻辑的计算内容。作者提出一种非良基证明系统,其语法用显式序数变量标注不动点公式,并给出可计算性概念,证明所有有效证明都是可计算的。由此得到有限公式证明的规范化结果;特别地,特定形式序列的每个证明都表示自然数上的唯一函数。最后,作者从证明系统导出范畴模型,并说明最小与最大不动点公式分别对应初代数与终余代数。

问题
如何为带归纳与余归纳定义的直觉主义逻辑建立具有计算内容的非良基证明系统,并刻画有效证明的可计算性与规范化。
方法
采用带显式序数变量标注不动点公式的非良基证明语法,定义可计算性,并由证明系统构造范畴模型。
评估
以理论证明进行评估:证明有效证明可计算,得到有限公式规范化定理及特定序列证明表示自然数唯一函数的结果,并验证不动点公式对应初代数与终余代数。
原文摘要(Abstract)

We introduce a non-wellfounded proof system for intuitionistic logic extended with inductive and co-inductive definitions, based on a syntax in which fixpoint formulas are annotated with explicit variables for ordinals. We explore the computational content of this system, in particular we introduce a notion of computability and show that every valid proof is computable. As a consequence, we obtain a normalization result for proofs of what we call finitary formulas. A special case of this result is that every proof of a sequent of the appropriate form represents a unique function on natural numbers. Finally, we derive a categorical model from the proof system and show that least and greatest fixpoint formulas correspond to initial algebras and final coalgebras respectively.

链接与引用

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

BibTeX
@article{Enqvist26,
  title = {Computation by infinite descent made explicit},
  author = {Sebastian Enqvist},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 22, Issue 2},
  year = {2026},
  doi = {10.46298/lmcs-22(2:32)2026}
}