题名 | 可盖相对计算度有关问题研究 |
作者 | 汪德嘉 |
学位类别 | 博士 |
答辩日期 | 1995 |
授予单位 | 中国科学院软件研究所 |
授予地点 | 中国科学院软件研究所 |
关键词 | 可盖递归枚举度 弱真值表 无向可盖度 无向可杯度 gap/cogap构造方法 |
其他题名 | Some Tesults about Cappable Degree |
学位专业 | 数理逻辑(mathematical logic) |
中文摘要 | 本文研究可盖递归枚举度(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 |
语种 | 中文 |
公开日期 | 2011-03-17 |
页码 | 23 |
内容类型 | 学位论文 |
源URL | [http://ir.iscas.ac.cn/handle/311060/7452] ![]() |
专题 | 软件研究所_中科院软件所_中科院软件所 |
推荐引用方式 GB/T 7714 | 汪德嘉. 可盖相对计算度有关问题研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 1995. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论