中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
不可解度研究
作者: 李昂生
答辩日期: 1993
专业: 基础数学
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
摘要: 本论文由四章组成,分别取自我们在r.e.度,d.r.e.度和wtt-度的四个前沿课题的研究工作。第一章我们证明,不存在强非可盖wtt-度,这是T-度之间关系的一个有趣且基本的结果,该结果进一步揭示了T-度和wtt-度的差别。第二章属r.e.度的临界性课题,我们证明,对任非递归可盖r.e.度a,存在非可盖r.e.度b使得a和b不可比较,而且a和b的下确界存在,从而彻底解决了Ambos-spies 1985年提出的问题:是否存在不可比可盖r.e.度a和非可盖r.e.度b使a和b的下确界存在。我们的结果也解决了沿Ambos-spies问题思路而产生的r.e.度临界性课题。第三章我们指出r.e.度结构的拓扑途径之研究,以区别和推动已有的两种途径之研究:逻辑的和代数的,我们建立连续性和相对孤立性这一r.e.度新课题,证明了该课题的一个基本定理:存在r.e.度a,b和c使得c < a, b, a ∧ b = c且对任r.e.度u和v,如果u < a,v ≤ a且a ∧ v = u,那么u ≤ c。在第三章,我们总结了在第一章、第二章和第三章以及作者在其它论文的证明中起关键作用的一个新技巧,即设置多余限制函数的技巧,由于该技巧在作者的若干问题和新课题研究中起了关键的作用,我们把该技巧称为一种方法,和Lachlan [1975]“无休止破坏”(Capricious destruction)0'"方法相对,我们称为“多余保护”(Superfluous preservation)O'"方法。该方法在思想上的突破是:它揭示了,一个策略设置怎样的限制函数将由全体策略的协调性来决定,这是一种整体思想方法,因此是Lachlan 0'"方法的补充和发展。作者深信,此方法将会带来重大的成果。第四章我们加强Cooper等五人[1991]所证明的结果:存在d.r.e.度d≠0'使得(d,o')中没有d.r.e.度,我们证明,对任高r.e.度h,存在d.r.e.度d使d < h且对任意d.r.e.度u如果u d,那么h ≤ u ∨ d。该结果部分解决了Copper~([1992])的猜想:任意d.r.e.高度之下存在d.r.e.度非稠密区间。
英文摘要: In chapter I, we show that there is no strongly noncappable r.e. degree under the weakly truth table reducibility. Chapter II gives a strongly positive answer for the question whether there exist incomparable cappable r.e. degree a and noncappable r.e. degree b such that the greatest lower bound of a and b exists. We show that for any nonrecursive cappable r.e. degree a, there exists noncappable r.e. degree b such that a and b are incomparable and the greatest lower bound of a and b exists. In Chapter III, we propose a new approach in viewpoint of the topological to the study of the structure of the recursively enumerable degrees, we build a new topic of the continuity and the relatively isolate properties of r.e. degrees. We invent a new method of "the superfluous preservation" and prove a result of the continuity and the relatively isolate theorem in the recursively enumerable degrees. Chapter IV is devoted to d.r.e. degrees, we partially give a positive answer to a conjuncture of Cooper in [1992] that the nondense interval of d.r.e. degrees exists below d.r.e. high degree. We show that, the conjuncture is true for high r.e. degree.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6094
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
N88269.pdf(1470KB)----限制开放-- 联系获取全文

Recommended Citation:
李昂生. 不可解度研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 1993-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[李昂生]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[李昂生]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace