Comprehensive Study of Recursive Function Theory

本项目所获研究成果的详细内容将以日文报告的形式发表。主要结果如下：(1)关于函数及其图的计算复杂性，证明了连续存在多项式增长率的函数，它们的图不是多项式时间可计算的；(2)关于广义Kolmogorov复杂性，证明了连续存在许多稀疏但不是自P-可打印的集合。(3)建立了Peano算法非标准模型上的布尔值模型理论。作为应用，理论I Sigma_0+Pigeon Hole原理不证明命题计数。(4)控制所有算术函数的每个函数都有比一般次数更高的次数。存在一个函数，它的次数是算术次数的一个最小上界，而任何低于它的次数的函数都由一个算术函数支配。(5)证明了在集合论的布尔值模型中，从给定的超结构可以构造一个非标准宇宙，从而强迫方法适用于非标准分析。通过改进形式化的Berry悖论，给出了Godel第一不完全性定理的一个新证明，并从理论上推导出了Godel第二不完全性定理。基于Kolmogorov复杂性，给出了Godel第二不完全性定理的一个新证明。(7)假设V=L，证明了II^1_集的Kleene度是非分配的。

The detail of the research results obtained in this project is to be published as a report in Japanese. Summary of several results is as follows.(1) On computational complexity of functions and their graphs, it is shown that there are continuaously many functions of polynomial growth rate which are not polynomial time computable from their graphs.(2) On generalized Kolmogorov complexity, it is shown that there are continuaously many sets which are sparse but not self P-printable.(3) The theory of Boolean-valued models on nonstandard models of Peano Arithmetic is established. As an application, the theory I Sigma_0 plus Pigeon Hole Principle does not prove the proposition Count.(4) Every function which dominates all arithmeical functions has higher degree than a generic degree. There is a function such that its degree is a minimal upper bound of the arithmetical degrees and any functon of degree below its degree is dominated by an arithmetical function.(5) It is shown that from a given supersutructure in a Boolean-valed model of set theory a nonstandard universe can be condtructed so that the forcing method is applicable to nonstandard analysis. Using this method, a uniform incomplete ultrapower of reals is constructed.(6) By improving the formalized Berry's paradox, a new proof of the Godel first incompleteness theorem is obtained, and from it the Godel second incomplete theorem is deduced model-theoretically. Also, a new proof of the Godel second incompleteness theorem is given based on the Kolmogorov complexity.(7) Assuming V = L,it is shown that the Kleene degrees of II^1_ sets are nondistributive.