Logic of Limit Computing and its Applications

点击翻译按钮获取中文摘要

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.