paperbot · PL 论文追踪

全部论文 待读 收藏

P2 “Upon This Quote I Will Build My Church Thesis”

基于此 quote,我将建立我的丘奇论题
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 2/10 · 论文属于类型论与形式语义基础研究,核心是 MLTT 扩展中的内部丘奇论题及其元理论,虽与形式化验证/PL 有工具层面的间接关联,但并未涉及用户关注的静态分析、LLM/Agent 改进验证、浮点程序分析或贝叶斯程序分析。引用 5 inbox
Pierre-Marie Pédrot
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:通过带 quote 算子的 MLTT 扩展,正面证明内部丘奇论题与依赖类型理论兼容,并建立其元理论。

内部丘奇论题(CT)断言任意函数 f : N → N 都可关联到某个图灵完备语言中的具体代码来计算它。CT 在较简单系统中的兼容性早已知道,但与依赖类型理论的兼容性此前仍是开放问题。本文给出肯定回答:定义“MLTT”,即在 MLTT 上加入 quote 算子的类型理论,并在此理论中可导出 CT。作者进一步用标准逻辑关系模型证明该理论一致、强规范化并具有典范性。所有结果均已在 Coq 中机器化验证。

问题
内部丘奇论题(CT)与依赖类型理论的兼容性此前仍是一个开放问题。
方法
本文定义带 quote 算子的 MLTT 扩展“MLTT”,使 CT 在该理论中可导出,并使用标准逻辑关系模型进行元理论证明。
评估
作者证明该理论一致、强规范化且具有典范性,并在 Coq 中机器化验证了全部结果。
原文摘要(Abstract)

The internal Church thesis (CT) is a logical principle stating that one can associate to any function f : N → N a concrete code, in some Turing-complete language, that computes f. While the compatibility of CT in simpler systems has been long known, its compatibility with dependent type theory is still an open question. In this paper, we answer this question positively. We define "MLTT", a type theory extending MLTT with quote operators in which CT is derivable. We furthermore prove that "MLTT" is consistent, strongly normalizing and enjoys canonicity using a rather standard logical relation model. All the results in this paper have been mechanized in Coq1.

链接与引用

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

BibTeX
@inproceedings{Pedrot24,
  title = {“Upon This Quote I Will Build My Church Thesis”},
  author = {Pierre-Marie Pédrot},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662070}
}