加杯图灵度的代数结构

ISCAS OpenIR > 中科院软件所 > 中科院软件所

	加杯图灵度的代数结构
其他题名	Algebraic Structure of the Plus Cupping Turing Degrees
	赵宜成
专业	基础数学
	2003
学位授予单位	中国科学院软件研究所
学位	博士
学位授予地点	中国科学院软件研究所
关键词	可计算枚举集损害优先方法加杯
摘要	在这篇论文中，我们主要致力于研究加杯度（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.
页数	49
语种	中文
内容类型	学位论文
URI标识	http://ir.iscas.ac.cn/handle/311060/5938
专题	中科院软件所_中科院软件所
推荐引用方式 GB/T 7714	赵宜成. 加杯图灵度的代数结构[D]. 中国科学院软件研究所. 中国科学院软件研究所,2003.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
LW011247.pdf（1701KB）			限制开放	--	请求全文