中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
可盖相对计算度有关问题研究
作者: 汪德嘉
答辩日期: 1995
专业: 数理逻辑(mathematical logic)
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 可盖递归枚举度 ; 弱真值表 ; 无向可盖度 ; 无向可杯度 ; gap/cogap构造方法
其他题名: Some Tesults about Cappable Degree
摘要: 本文研究可盖递归枚举度(cappable r.e. degree)的有关问题。我们首先证明不存在弱真值表(wtt)可盖度的一致性构造,即不存在递归函数f和递归泛函#PHI#使得对任意e #belongs to (is member of ) the set# #omega#, w_f(e)=[#PHI#](We),deg_wtt(W_f(e))为弱真值表可盖度,且W_e非递归蕴涵W_f(e)非递归。在T.A.Slaman的问题集中,Lempp提出了一个与一致性构造有关的猜想:对任意递归枚举度a和b,若a #not<=# b则在区间R(<=a)-R(<=b)中存在可盖度c(即c<=a且c#not<=#b)。我们考虑Lempp猜想成立的条件,并且证明了若加上条件b∈NB(NB为其下无极小对的度集合),则Lemmp猜想成立;进一步,如果a#not<=#b, b∈M,那么在区间R(<=a)-R(<=b)中存在可盖度。最后我们研究可盖度在R中的分布情况。递归枚举度a称为无向可盖度,若O
英文摘要: In this paper, we are doing research on some problems about cappable degrees. Firstly, we have shown that there does not exist uniform construction of wtt-cappable degree, that is, there is no recursive function f and p.r. functional #PHI# such that for any e #belongs to (is member of ) the set# #omega#, w_f(e)=[#PHI#](We),deg_wtt(W_f(e)) is a wtt-cappable degree and W_e nonrecursive implies W_f(e) nonrecursive. In T.A.Slaman's "Questions in Recursion Theory", Lempp communicates a conjecture which is also related to the uniform construction of cappable degree: For any r.e. degree a and b, if a #not<=# b them=n there exists a cappable degree c in R(<=a)-R(<=b). We consider the positive aspects of Lempp's conjec-ture under some conditions, and show that if we add condition b∈NB (where NB=({a>O|a does not bound a minimal pair}), then the conjecture of Lempp is true. Furthermore, if a#not<=#b and b∈M, then there also exists a cappable degree in R(<=a)-R(<=b). Lastly, we consider the distribution of cappable degree in R.A recursively enumerable degree a is undirectly cappable if O
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/7452
Appears in Collections:中科院软件所

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

Recommended Citation:
汪德嘉. 可盖相对计算度有关问题研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 1995-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