| 题名: | 加杯图灵度的代数结构 |
| 作者: | 赵宜成
|
| 答辩日期: | 2003
|
| 专业: | 基础数学
|
| 授予单位: | 中国科学院软件研究所
|
| 授予地点: | 中国科学院软件研究所
|
| 学位: | 博士
|
| 关键词: | 可计算枚举集
; 损害优先方法
; 加杯
|
| 其他题名: | Algebraic Structure of the Plus Cupping Turing Degrees
|
| 摘要: | 在这篇论文中，我们主要致力于研究加杯度（plus cupPingde－grees）的代数结构。一个可计算枚举（computobly enumeroble，简记为c.e.）度被称为加杯的，如果它囿界的每个非零的c.e.度都是可杯的，也就是说能与一个不完全c.e.度结合为0'。本篇论文分为4个部分：第部分介绍了这个领域的些背景知识；第二部分主要回顾了前人在研究可计算枚举度的结构和层谱时所取得的一些基本和最新结果，这些结果与我们的主题一加杯图灵度的代数结构密切相关；在第三部分中，我们概要的描述了优先树方法的基本原理，此方法是可计算性理论中定理证明的一个重要框架和工具；第四部分证明了一个加杯图灵度代数结构的新结果：存在两个可计算枚举度a，b，满足a，b∈PC，而且a和b的并a∨b是一个高度。因此所有加杯可计算枚举度组成的集合PC不是ε的理想，这里ε是所有可计算枚举度构成的上半格。 |
| 英文摘要: | In this thesis we investigate the algebraic structure of the plus cupping degrees. A computably enumerable (c.e., for short) degree is called plus cupping, if every nonzero c.e. degree below it is cuppable, in the sense that it joins to 0' with an incomplete c.e. degree. The thesis consists of four sections. In section one, we introduce some background of the topic, in section two we review some basic and recent results about the structure and hierarchies of the computably enumerable degrees which are closely related to our topic- the algebraic structure of the plus cupping Turing degrees, in section three, we outline the basic principles of the priority tree argument, one of the main frameworks and tools of theorem proving in computability theory, and in section four, we prove a new result concerning the algebraic structure of the plus cupping Turing degrees that there exist two computably enumerable degrees a,b such that a,b∈PC, and the join a∨ b of a and b is high. Consequently, the class PC of the plus cupping computably enumerable degrees is not an ideal of ε, the upper semilattice of the computably enumerable degrees. |
| 语种: | 中文
|
| 内容类型: | 学位论文
|
| URI标识: | http://ir.iscas.ac.cn/handle/311060/5938
|
| Appears in Collections: | 中科院软件所
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| LW011247.pdf（1701KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
赵宜成. 加杯图灵度的代数结构[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2003-01-01.
|
|
|
