摘要
证明了给定任何非零的递归可枚举图灵度 a存在递归可枚举图灵度 c<a和 d∈M,使得 a≤ d∪ c.由此可以得到 :在每个非零 [a]∈ R∧ M中不存在极小元 ,即给定任何非可盖递归可枚举图灵度 a,存在一个递归可枚举图灵度 c<a,使得 [c]=[a].
It is proved that given any nonrecursive r.e. degree a, there exist r.e. degrees c<a and d∈M such that a≤d∪c. Therefore, there is no minimal r.e. degree in every nonzero [a]∈R/M, the quotient upper semilattice of the recursively enumerable degrees modulo the cappable r.e. degrees, i.e., given any noncappable r.e. degree a there is an r.e. degree c<a such that [c]=[a].
出处
《软件学报》
EI
CSCD
北大核心
2000年第11期1425-1429,共5页
Journal of Software
基金
国家自然科学基金&&
关键词
图灵度
递归可枚举度
极小时
Turing degree, recursively enumerable set, minimal pair4
