paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A direct computational interpretation of second-order arithmetic via update recursion

通过 update recursion 对二阶算术的直接计算解释
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 2/10 · 该论文属于证明论与类型系统基础工作,讨论二阶算术的计算解释(bar recursion、update recursion、多态λ演算),与用户画像的核心方向(LLM/Agent 用于静态分析或形式化验证、浮点程序分析、贝叶斯程序分析)几乎没有直接交集。仅在“形式化验证/定理证明”这一宽泛领域有边缘关联,不涉及 LLM、工程落地或问题驱动的分析工具。引用 3 inbox
Valentin Blot
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:用 update recursion 直接解释二阶算术的二阶消去,弥合 bar recursion 与多态 λ 演算两条计算解释路径。

二阶算术有两种计算解释路径:Spector 的 bar recursion 解释选择公理的负翻译,结合排中律负翻译后可解释概括公理模式的负翻译,并通过实例化全称量化集合得到二阶消去;Girard 的多态 λ 演算则用多态类型直接解释二阶消去。本文旨在弥合二者差距,提出用 update recursion(bar recursion 的变体)直接解释二阶消去,从而给出二阶算术的直接计算解释,并建立其与既有两条路径的联系。工作以证明论与类型论的理论构造和元定理证明为主,摘要未涉及实验评估。

问题
如何直接解释二阶算术中的二阶消去,并弥合 bar recursion 与多态 λ 演算两种计算解释之间的差距。
方法
引入 update recursion(bar recursion 的变体)直接解释二阶消去,给出二阶算术的直接计算解释,并关联既有解释。
评估
以证明论/类型论的理论构造与元定理证明进行论证;摘要未涉及实验或形式化实现评估。
原文摘要(Abstract)

Second-order arithmetic has two kinds of computational interpretations: via Spector’s bar recursion of via Girard’s polymorphic lambda-calculus. Bar recursion interprets the negative translation of the axiom of choice which, combined with an interpretation of the negative translation of the excluded middle, gives a computational interpretation of the negative translation of the axiom scheme of comprehension. It is then possible to instantiate universally quantified sets with arbitrary formulas (second-order elimination). On the other hand, polymorphic lambda-calculus interprets directly second-order elimination by means of polymorphic types. The present work aims at bridging the gap between these two interpretations by interpreting directly second-order elimination through update recursion, which is a variant of bar recursion.

链接与引用

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

BibTeX
@inproceedings{Blot22,
  title = {A direct computational interpretation of second-order arithmetic via update recursion},
  author = {Valentin Blot},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3532458}
}