Institutional Repository
| NB和PC的比较研究 | |
| Alternative Title | On the Relationship Between Nonbounding and Plus Cupping Turing Degrees |
| 李登峰 | |
| Major | 基础数学 |
| 2003 | |
| Degree Grantor | 中国科学院软件研究所 |
| Degree Level | 博士 |
| Place of Degree Grantor | 中国科学院软件研究所 |
| Keyword | 可计算枚举图灵度 极小对 |
| English 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。 |
| 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. |
| Pages | 37 |
| Language | 中文 |
| Content Type | 学位论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/7422 |
| Collection | 中科院软件所_中科院软件所 |
| Recommended Citation GB/T 7714 | 李登峰. NB和PC的比较研究[D]. 中国科学院软件研究所. 中国科学院软件研究所,2003. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| LW011224.pdf（1408KB） | 限制开放 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment