| Title: | NB和PC的比较研究 |
| Author: | 李登峰
|
| Issued Date: | 2003
|
| Major: | 基础数学
|
| Degree Grantor: | 中国科学院软件研究所
|
| Place of Degree Grantor: | 中国科学院软件研究所
|
| Degree Level: | 博士
|
| Keyword: | 可计算枚举图灵度
; 极小对
|
| Alternative Title: | On the Relationship Between Nonbounding and Plus Cupping Turing Degrees
|
| Abstract: | 一个可计算枚举（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。 |
| English Abstract: | 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. |
| Language: | 中文
|
| Content Type: | 学位论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/7422
|
| Appears in Collections: | 中科院软件所
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| LW011224.pdf（1408KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
李登峰. NB和PC的比较研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2003-01-01.
|
|
|
