关于极限引理的一些应用

本文首先推广定义 n-可加速集,给出 n-非可加集与 n-低度之间的关系.证明 r.e.度(?)使得存在 r.e.n-可加速集 A≡_n(?)当且仅当(?)~(n)>(?)~(n).然后运用极限引理到 H_n 的描述中,证明 r.e.度(?)包含一个 n-极大集 A≡_n(?)当且仅当(?)∈H_n,i.,e.(?)~(n)≥(?)~(n+1)且(?)∈H_n 当且仅当存在一个度≤(?)的函数 f,n-do-minate 每个递归函数.     

R/M的局部分配性

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＡｍｂｏｓ－Ｓｐｉｅｓ,Ｊｏｃｋｕｓｃｈ,ＳｈｏｒｅａｎｄＳｏａｒｅ［１９８４］ｐｒｏｖｅｄｔｈａｔＭ,ｔｈｅｓｅｔｏｆａｌｌｔｈｅｃａｐ－ｐａｂｌｅｒ．ｅ．ｄｅｇｒｅｅｓ,ｉｓａｎｉｄｅａｌｉｎＲａｎｄＮＣ,ｔｈｅｓｅｔｏｆａｌｌｔｈｅｎｏｎｃａｐｐａｂｌｅｒ．ｅ．ｄｅｇｒｅｅｓ,ｉｓａｆｉｌ－ｔｅｒｉｎＲａｎｄＮＣ＝ＰＳ,ｔｈｅｓｅｔｏｆａｌｌｔｈｅｐｒｏｍｐｔｌｙｓｉｍｐｌｅｄｅｇｒｅｅｓ．Ｗｅｈａｖｅａｑｕｏｔｉｅｎｔｐａｒｔｉａｌｏｒｄｅｒｏｆｔｈｅｒ．…     

W—度与T—度的结构差别（Ⅱ）

§1 介绍与基本概念最近,许多文章讨论r.e。集合的T-度与W-度之间的结构差别,例如Lerman和Remmel讨论USP性质以及UWP性质。1985年Downey证明每个度中都存在一个r.e。集合具有～USP和～UWP性质,并且猜想除contiguous度和完备度以外,所有度不包含具有USP(UWP)性质的r.e.集合。如果这样的话,contiguous集合具有的结构性质,具有USP性质的集合也应该具有。我们这里只讨论一种结构性质。Ambos,Spies和Fejer[ta]证明contiguous度在低度中     

W-度与T-度的结构差别Ⅰ

这篇文章,我们结合枝上的树型构造和具有～USP性质的集合构造方法,构造r.e.集合A,B使得T-deg(A)∩T-deg(B)与W-deg(A)∩W-deg(B)在T-归约以及W-归约下都不相等.从而推出r.e.的W-归约度结构与T-归约度结构不等价. 我们说r.e.集合A具有～UWP性质,如果存在r.e.集B≤(?),A使得对任意C≡_TB有C_wA;并且称B为A具有～UWP性质的证据.定义     

高型递归论,Kleene-递归论及一般递归论之间的一个关系

这篇文章中,我们用算子代替泛函作为量词变量定义递归分层和推广递归论,证明半递归于E的子集集合在量词下封闭,这样就使得更高型递归论与型-2递归论在许多方面都是一致的;而在一般定义下,更高型递归论与型-2递归论之间有一个主要差别就是半递归于n~E的子集集合在量词(?)~(n-1)下不封闭,尽管在量词(?)_(n-2)下封闭.这说明了,用算子代替泛函作为量词变量更为合适.     

递归可枚举度临界性问题的一个结果(Ⅰ)

本文证明:对任 cappable r.e.度■,存在 r.e.度■和■使得■>■,■∧■=0且对任 r.e.度■,如果■且■,那么■∧■≠■.