Logic of Limit Computing and its Applications

极限计算逻辑及其应用

• 批准号: 13480084
• 负责人: HAYASHI Susumu
• 金额: $ 2.62万
• 依托单位: Kobe University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-13480084/
• 关键词: Inductive inference; mathematical logic; classical proof execution; 形式的証明; 形式的技法; 学習理論; 極限計算; 非構成的論理; 非構成的原理

The fundamental theory of Limit Computable Mathematics (LCM) were founded and many new results have been obtained in the project. The followings are the main results among them :1. Improved realizability interpretations for LCM2. sublearning hierarchy3. LCM game4. the arithmetical hierarchy5. LCM categories6. Computability in analysis in the light of LCM. Computability theory of discontinuous functions7. Models of Delta-0-2 maps by means of concurrent computationAmong them, the discovery of sublearning hierarchy is quite important. Below the hierarchy of LEM (the laws of excluded middle), principles corresponding to LLPO of constructive mathematics exist and they are related to WKL (Weak Koenig Lemma). This fact has been conceived by some researchers intuitively. By establishing computational and learning theoretic meanings of this fact, we finally explored the position of WKL in the hierarchy of LCM. We found that the principle represents the limit computational model of Popperian game of non-deterministic computation of refutability by finite numbers of processes.The full arithmetical hierarchy of LCM including this sublearning hierarchy was fully explored.This was done through various techniques of mathematical logic, and it is important also from mathematical point of view. The calibration theory according to this hierarchy has been started by a researcher out of our project.We also found that Coquand's game semantics could be restricted in a very natural way so that it coincides with LCM.

建立了极限可计算数学（LCM）的基本理论，并取得了许多新的成果。主要研究结果如下：1.改进了LCM 2的可实现性解释。子学习层次3. LCM游戏4.算术等级5. LCM分类6.根据LCM分析的可计算性。不连续函数的可计算性理论7.用并行计算的方法建立Delta-0-2映射的模型，其中子学习层次的发现是十分重要的。在LEM（排中律）的层次之下，存在着与构造性数学的LLPO相对应的原理，它们与WKL（弱柯尼希引理）有关。这一事实是一些研究人员凭直觉设想出来的。通过建立这一事实的计算和学习理论意义，我们最终探讨了WKL在LCM层次结构中的位置。我们发现，该原则代表了有限个过程的可反驳性的非确定性计算的Popperian博弈的极限计算模型。LCM的完整的算术层次，包括这个子学习层次被充分探索。这是通过各种数理逻辑技术完成的，从数学的角度来看，它也很重要。我们还发现Coquand的博弈语义可以以一种非常自然的方式被限制，从而与LCM相一致。

项目成果

Susumu Hayashi: "Mathematics based on Incremental Learning, -Excluded middle and Inductive inference-"Theoretical Computer Science. (to appear).

Susumu Hayashi：“基于增量学习的数学，-排除中间推理和归纳推理-”理论计算机科学。

M.Yasugi, Y.Tsujii: "Two notions of sequential computability of a function with jumps"Electronic Notes in Theoretical Computer Science. 66 No.1. (2002)

M.Yasugi、Y.Tsujii：“带有跳跃的函数的顺序可计算性的两个概念”理论计算机科学中的电子笔记。

Akama, Y., et al.: "An arithmetical hierarchy of the law of excluded middle and related principles"Proceedings of LICS2004. (To appear). (2004)

Akama, Y., et al.：“排中律及相关原理的算术层次结构”LICS2004 论文集。

Akama, Y.: "Limiting Partial combinatory Algebras"Theoretical Computer Science. 311. 199-220 (2004)

Akama, Y.：“限制部分组合代数”理论计算机科学。

Akama, Y.: "Limiting Partial Combinatory Algebras"Theoretical Computer Science. Vol.311(1-3). 199-220 (2004)

Akama, Y.：“限制部分组合代数”理论计算机科学。