可盖相对计算度有关问题研究

ISCAS OpenIR > 中科院软件所 > 中科院软件所

	可盖相对计算度有关问题研究
其他题名	Some Tesults about Cappable Degree
	汪德嘉
专业	数理逻辑(mathematical logic)
	1995
学位授予单位	中国科学院软件研究所
学位	博士
学位授予地点	中国科学院软件研究所
关键词	可盖递归枚举度弱真值表无向可盖度无向可杯度 Gap/cogap构造方法
摘要	本文研究可盖递归枚举度（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
页数	23
语种	中文
内容类型	学位论文
URI标识	http://ir.iscas.ac.cn/handle/311060/7452
专题	中科院软件所_中科院软件所
推荐引用方式 GB/T 7714	汪德嘉. 可盖相对计算度有关问题研究[D]. 中国科学院软件研究所. 中国科学院软件研究所,1995.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
N91062.pdf（1693KB）			限制开放	--	请求全文