权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Comprehensive Study of Recursive Function Theory

递归函数论综合研究

基本信息

批准号：
06302014
负责人：
SHINODA Juichi
金额：
$ 3.26万
依托单位：
Nagoya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Co-operative Research (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至 1995
项目状态：
已结题

项目摘要

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.

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