Comprehensive Study of Recursive Function Theory

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

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.