DSpace at School of Computing, NUS: Item 1900.100/3042

Please use this identifier to cite or link to this item: http://hdl.handle.net/1900.100/3042

Title:	Turing Degrees And The Ershov Hierarchy
Authors:	STEPHAN, Frank YANG, Yue YU, Liang
Issue Date:	23-Jun-2009
Series/Report no.:	;TRC6/09
Abstract:	An n-r.e. set can be defined as the symmetric difference of n recursively enumerable sets. The classes of these sets form a natural hierarchy which became a well-studied topic in recursion theory. In a series of ground-breaking papers, Ershov generalized this hierarchy to transfinite levels based on Kleene's notations of ordinals and this work lead to a fruitful study of these sets and their many-one and Turing degrees. The Ershov hierarchy is a natural measure of complexity of the sets below the halting problem. In this paper, we survey the early work by Ershov and others on this hierarchy and present the most fundamental results. We also provide some pointers to concurrent work in the field.
URI:	http://hdl.handle.net/1900.100/3042
Appears in Collections:	Technical Reports

Files in This Item:

File	Size	Format
TRC6-09.pdf	272Kb	Adobe PDF	View/Open