| NB和PC的比较研究 |
| 其他题名 | On the Relationship Between Nonbounding and Plus Cupping Turing Degrees
|
| 李登峰
|
| 专业 | 基础数学
|
| 2003
|
| 学位授予单位 | 中国科学院软件研究所
|
| 学位 | 博士
|
| 学位授予地点 | 中国科学院软件研究所
|
| 关键词 | 可计算枚举图灵度
极小对
|
| 摘要 | 一个可计算枚举（c.e.）图灵度a被称为Nonbounding,是指它没有囿界任何极小对；一个可计算枚举（c.e.）图灵度a被称为Plus cupping，是指对于任何一个可计算枚举（c．e．）图灵度x，如果x≠0并且x≤a，那么x是可杯的（cuppable）。我们用NB来表示所有Nollb011lldillg可计算枚举（c.e.）图灵度的集合，而用Pc来表示所有Plus cuppillg可计算枚举（c.e.）图灵度的集合。集合NB和集合PC都已有很多研究结果，但是到目前为止还没有给出两个集合相同或者不同的证明。本文研究上述两个集合的关系：构造了一个极小对-其并为一个PIus cuppillg可计算枚举（c.e.）图灵度，从而证明了Pc不包含于NB。 |
| 其他摘要 | A computably enumerable (c.e.) degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below it is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possibe so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC, and show that there exists a minimal pair which join to a plus cupping degree, so that PC?NB. This gives a first known difference between NB and PC. |
| 页数 | 37
|
| 语种 | 中文
|
| 内容类型 | 学位论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/7422
|
| 专题 | 中科院软件所_中科院软件所
|
推荐引用方式
GB/T 7714 |
李登峰. NB和PC的比较研究[D]. 中国科学院软件研究所. 中国科学院软件研究所,2003.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论