paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Stateful Realizers for Nonstandard Analysis

非标准分析的有状态 realizer
LMCS vol.Volume 19, Issue 22023匹配度 1/10 · 论文属于数理逻辑与非标准分析的可实现性语义研究,核心是带状态λ-演算的realizer构造,与用户关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析均无直接关联;仅在形式语义/形式化验证的理论背景上有极弱交集。引用 0 inbox
Bruno Dinis, Étienne Miquey
crossref: 2026-09-10

AI 速览

一句话:为半直觉主义非标准算术提出带状态 λ-演算的可实现性解释,并给出 Idealization 与 LLPO 的非平凡 realizer。

本文为(半)直觉主义框架下的非标准算术提出新的可实现性解释。作者聚焦用超幂构造非标准模型的 Lightstone–Robinson 方法,将 λ-演算扩展为带整数状态记忆单元的计算系统:该状态指示当前计算位于超幂 M^N 的哪一切片。在此设定下,论文考察可获得的非标准原则及其计算内容,给出 Idealization 和非标准版 LLPO 的非平凡 realizer。最后讨论如何对超幂乘积作商,以模拟 Lightstone–Robinson 构造,把可实现性解释与非标准模型语义联系起来。

问题
如何为(半)直觉主义非标准算术/分析给出可实现性解释,并刻画非标准原则的计算内容。
方法
将 λ-演算扩展为含整数状态记忆单元的计算系统,用状态标记超幂 M^N 的计算切片,构造非标准原则的 realizer,并讨论商构造。
评估
以构造性证明/形式构造方式给出 Idealization 与非标准 LLPO 的非平凡 realizer,并讨论商化如何对应 Lightstone–Robinson 构造。
原文摘要(Abstract)

In this paper we propose a new approach to realizability interpretations for nonstandard arithmetic. We deal with nonstandard analysis in the context of (semi)intuitionistic realizability, focusing on the Lightstone-Robinson construction of a model for nonstandard analysis through an ultrapower. In particular, we consider an extension of the $\lambda$-calculus with a memory cell, that contains an integer (the state), in order to indicate in which slice of the ultrapower $\cal{M}^{\mathbb{N}}$ the computation is being done. We pay attention to the nonstandard principles (and their computational content) obtainable in this setting. In particular, we give non-trivial realizers to Idealization and a non-standard version of the LLPO principle. We then discuss how to quotient this product to mimic the Lightstone-Robinson construction.

链接与引用

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

BibTeX
@article{paperbot2221,
  title = {Stateful Realizers for Nonstandard Analysis},
  author = {Bruno Dinis and Étienne Miquey},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 19, Issue 2},
  year = {2023},
  doi = {10.46298/lmcs-19(2:7)2023}
}