paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Computability Beyond Church-Turing via Choice Sequences

通过选择序列超越 Church-Turing 可计算性
LICS Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science2018匹配度 2/10 · 该论文属于构造性类型论与形式语义,虽与形式化验证有间接关联,但不涉及用户核心关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析。引用 9 inbox
Mark Bickford, Liron Cohen, Robert L. Constable, Vincent Rahli
crossref: 2026-09-12

AI 速览

一句话:提出扩展 Nuprl 类型论的新类型论 BITT,用 Beth 式语义嵌入自由选择序列并验证其关键公理。

经典可计算性由 Church-Turing 论题刻画,而 Brouwer 提出的自由选择序列允许非律则的、逐步自由选择且非确定地扩展的无穷序列,从而超出该框架。为在构造性类型论中容纳此类对象,本文提出 BITT——Nuprl 类型论的扩展。为支持选择序列不断演化且非确定的性质,BITT 对底层类型论作了重要修改:利用底层库作为状态存储已作出的选择,以保证后续选择与既有选择一致;同时采用 Beth 式语义刻画其动态性。作者形式定义 BITT,并用它解释和验证支配选择序列的基本公理,为完全直觉主义的 Nuprl 奠定基础。

问题
如何在构造性类型论中形式化 Brouwer 的自由选择序列,从而刻画超越 Church-Turing 的非律则可计算性。
方法
提出并形式定义 BITT,扩展 Nuprl 类型论,以底层库作为状态存储选择,并采用 Beth 式语义处理选择序列的动态、非确定演化。
评估
通过形式化解释和验证选择序列的关键公理,展示 BITT 的合理性,并作为完全直觉主义 Nuprl 的基础。
原文摘要(Abstract)

Church-Turing computability was extended by Brouwer who considered non-lawlike computability in the form of free choice sequences. Those are essentially unbounded sequences whose elements are chosen freely, i.e. not subject to any law. In this work we develop a new type theory BITT, which is an extension of the type theory of the Nuprl proof assistant, that embeds the notion of choice sequences. Supporting the evolving, non-deterministic nature of these objects required major modifications to the underlying type theory. Even though the construction of a choice sequence is non-deterministic, once certain choices were made, they must remain consistent. To ensure this, BITT uses the underlying library as state and store choices as they are created. Another salient feature of BITT is that it uses a Beth-like semantics to account for the dynamic nature of choice sequences. We formally define BITT and use it to interpret and validate essential axioms governing choice sequences. These results provide a foundation for a fully intuitionistic version of Nuprl.

链接与引用

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

BibTeX
@inproceedings{paperbot4321,
  title = {Computability Beyond Church-Turing via Choice Sequences},
  author = {Mark Bickford and Liron Cohen and Robert L. Constable and Vincent Rahli},
  booktitle = {LICS},
  year = {2018},
  doi = {10.1145/3209108.3209200}
}