题名 | 不可解度研究 |
作者 | 李昂生 |
学位类别 | 博士 |
答辩日期 | 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.度非稠密区间。 |
语种 | 中文 |
公开日期 | 2011-03-17 |
页码 | 55 |
内容类型 | 学位论文 |
源URL | [http://ir.iscas.ac.cn/handle/311060/6094] ![]() |
专题 | 软件研究所_中科院软件所_中科院软件所 |
推荐引用方式 GB/T 7714 | 李昂生. 不可解度研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 1993. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论