paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Primitive Recursive Dependent Type Theory

原始递归依赖类型论
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 1/10 · 该论文属于纯类型论/形式语义研究,讨论 Martin-Löf 类型论的原始递归子理论,未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心方向。虽然与形式化验证的基础理论有一定距离上的关联,但不在研究画像的主线上。引用 1 inbox
Ulrik Torben Buchholtz, Johannes Schipp von Branitz
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:通过限制 Martin-Löf 类型论的自然数消去与宇宙,构造 Tpr 理论,使可定义函数均为原始递归。

本文研究如何在依赖类型论中刻画原始递归可定义性。作者把 Martin-Löf 类型论中自然数类型的消去原则限制到不含 Π-类型的宇宙,并定义子理论 Tpr:两个宇宙 U0 : U1,所有归纳类型有穷,且 U0 不含 Π-类型。论文证明 Tpr 可靠,使所有 N → N 可定义函数都是原始递归;证明依赖 Tpr 的 canonicity,并用 synthetic Tait computability 得出。作者还讨论向 univalent 类型论和其他可计算性概念的扩展。

问题
如何在依赖类型论中限制可定义函数的计算能力,使其恰好对应原始递归函数,并将原始递归性推广到一般类型?
方法
定义 MLTT 的子理论 Tpr:两个宇宙 U0 : U1,所有归纳类型有穷,且 U0 不含 Π-类型;通过限制自然数消去原则,并使用 synthetic Tait computability 证明 canonicity 与可靠性。
评估
以理论证明方式证明 Tpr 的 soundness,得出所有 N → N 可定义函数均为原始递归;并讨论向 univalent 类型论和其他可计算性概念的扩展。
原文摘要(Abstract)

We show that restricting the elimination principle of the natural numbers type in Martin-Löf Type Theory (MLTT) to a universe of types not containing ####II-types ensures that all definable functions are primitive recursive. This extends the concept of primitive recursiveness to general types. We discuss extensions to univalent type theories and other notions of computability. We are inspired by earlier work by Martin Hofmann [18], work on Joyal's arithmetic universes [27], and Hugo Herbelin and Ludovic Patey's sketched Calculus of Primitive Recursive Constructions [16]. We define a theory Tpr that is a subtheory of MLTT with two universes U0 : U1, such that all inductive types are finitary and U0 is restricted to not contain ####II-types: [EQUATION] We prove soundness such that all functions N → N are primitive recursive. The proof requires that Tpr satisfies canonicity, which we easily prove using synthetic Tait computability [36].

链接与引用

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

BibTeX
@inproceedings{BuchholtzB24,
  title = {Primitive Recursive Dependent Type Theory},
  author = {Ulrik Torben Buchholtz and Johannes Schipp von Branitz},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662136}
}