Turing definability in the Ershov hierarchy

S. Barry Cooper; Angsheng Li

doi:10.1112/S0024610702003691

Turing definability in the Ershov hierarchy

S. Barry Cooper^*
, Angsheng Li

^*Corresponding author for this work

University of Leeds
CAS - Institute of Software

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

The first nontrivial DCE (2-computably enumerable) Turing approximation to the class of computably enumerable degrees is obtained. This depends on the following extension of the splitting theorem for the DCE degrees. For any DCE degree a and any computably enumerable degree b, if b < a, then there are DCE degrees x₀, x₁ such that b < x₀, x₁ < a and a = x₀ ∨ x₁. The construction is unusual in that it is incompatible with upper cone avoidance.

Original language	English
Pages (from-to)	513-528
Number of pages	16
Journal	Journal of the London Mathematical Society
Volume	66
Issue number	3
DOIs	https://doi.org/10.1112/S0024610702003691
State	Published - Dec 2002
Externally published	Yes

Access to Document

10.1112/S0024610702003691

Cite this

@article{3c68ea4f33e64f8d86af234e0d49605a,

title = "Turing definability in the Ershov hierarchy",

abstract = "The first nontrivial DCE (2-computably enumerable) Turing approximation to the class of computably enumerable degrees is obtained. This depends on the following extension of the splitting theorem for the DCE degrees. For any DCE degree a and any computably enumerable degree b, if b < a, then there are DCE degrees x0, x1 such that b < x0, x1 < a and a = x0 ∨ x1. The construction is unusual in that it is incompatible with upper cone avoidance.",

author = "Cooper, \{S. Barry\} and Angsheng Li",

year = "2002",

month = dec,

doi = "10.1112/S0024610702003691",

language = "英语",

volume = "66",

pages = "513--528",

journal = "Journal of the London Mathematical Society",

issn = "0024-6107",

publisher = "John Wiley and Sons Ltd",

number = "3",

}

TY - JOUR

T1 - Turing definability in the Ershov hierarchy

AU - Cooper, S. Barry

AU - Li, Angsheng

PY - 2002/12

Y1 - 2002/12

N2 - The first nontrivial DCE (2-computably enumerable) Turing approximation to the class of computably enumerable degrees is obtained. This depends on the following extension of the splitting theorem for the DCE degrees. For any DCE degree a and any computably enumerable degree b, if b < a, then there are DCE degrees x0, x1 such that b < x0, x1 < a and a = x0 ∨ x1. The construction is unusual in that it is incompatible with upper cone avoidance.

AB - The first nontrivial DCE (2-computably enumerable) Turing approximation to the class of computably enumerable degrees is obtained. This depends on the following extension of the splitting theorem for the DCE degrees. For any DCE degree a and any computably enumerable degree b, if b < a, then there are DCE degrees x0, x1 such that b < x0, x1 < a and a = x0 ∨ x1. The construction is unusual in that it is incompatible with upper cone avoidance.

UR - https://www.scopus.com/pages/publications/0036953557

U2 - 10.1112/S0024610702003691

DO - 10.1112/S0024610702003691

M3 - 文章

AN - SCOPUS:0036953557

SN - 0024-6107

VL - 66

SP - 513

EP - 528

JO - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

IS - 3

ER -

Turing definability in the Ershov hierarchy

Abstract

Access to Document

Other files and links

Fingerprint

Cite this