Non-Uniformity and Generalised Sacks Splitting

S. Barry Cooper; Ang Sheng Li

doi:10.1007/s101140100150

Non-Uniformity and Generalised Sacks Splitting

S. Barry Cooper^*
, Ang Sheng Li

^*Corresponding author for this work

University of Leeds
CAS - Institute of Software

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

6 Scopus citations

Abstract

We show that there do not exist computable functions f1(e,i), f2(e, i), g1(e,i), g2(e,i) such that for all e, i ∈ w, (1) (W_f1(e,i) - W_f2(e,i)) ≤T (W_e - W_i); (2) (W_g1(e,i) - W_g2(e,i)) ≤T (W_e - W_i); (3) (W_e - W_i) ≤T (W_f2(e,i) - W_f2(e.i)) ⊖ (W_g1(e,i) - W_g2(e,i)); (4) (W_e - W_i) ≰T (W_f1(e,i) - W_f2(e,i)) unless (W_e - W_i) ≤T 0 and (5) (W_e - W_i) ≰T (W_g1(e,i) - W_g2(e,i)) unless (W_e - W_i) ≤T 0. It follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly.

Original language	English
Pages (from-to)	327-334
Number of pages	8
Journal	Acta Mathematica Sinica, English Series
Volume	18
Issue number	2
DOIs	https://doi.org/10.1007/s101140100150
State	Published - Apr 2002
Externally published	Yes

Keywords

Computably enumerable (c.e.)
Difference of computably enumerable sets (d.c.e., or 2-c.e.)
Splitting and nonsplitting
Turing degrees

Access to Document

10.1007/s101140100150

Cite this

@article{1c79736bc87c44abbcf284549039ffca,

title = "Non-Uniformity and Generalised Sacks Splitting",

abstract = "We show that there do not exist computable functions f1(e,i), f2(e, i), g1(e,i), g2(e,i) such that for all e, i ∈ w, (1) (Wf1(e,i) - Wf2(e,i)) ≤T (We - Wi); (2) (Wg1(e,i) - Wg2(e,i)) ≤T (We - Wi); (3) (We - Wi) ≤T (Wf2(e,i) - Wf2(e.i)) ⊖ (Wg1(e,i) - Wg2(e,i)); (4) (We - Wi) ≰T (Wf1(e,i) - Wf2(e,i)) unless (We - Wi) ≤T 0 and (5) (We - Wi) ≰T (Wg1(e,i) - Wg2(e,i)) unless (We - Wi) ≤T 0. It follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly.",

keywords = "Computably enumerable (c.e.), Difference of computably enumerable sets (d.c.e., or 2-c.e.), Splitting and nonsplitting, Turing degrees",

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

year = "2002",

month = apr,

doi = "10.1007/s101140100150",

language = "英语",

volume = "18",

pages = "327--334",

journal = "Acta Mathematica Sinica, English Series",

issn = "1439-8516",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - Non-Uniformity and Generalised Sacks Splitting

AU - Cooper, S. Barry

AU - Li, Ang Sheng

PY - 2002/4

Y1 - 2002/4

N2 - We show that there do not exist computable functions f1(e,i), f2(e, i), g1(e,i), g2(e,i) such that for all e, i ∈ w, (1) (Wf1(e,i) - Wf2(e,i)) ≤T (We - Wi); (2) (Wg1(e,i) - Wg2(e,i)) ≤T (We - Wi); (3) (We - Wi) ≤T (Wf2(e,i) - Wf2(e.i)) ⊖ (Wg1(e,i) - Wg2(e,i)); (4) (We - Wi) ≰T (Wf1(e,i) - Wf2(e,i)) unless (We - Wi) ≤T 0 and (5) (We - Wi) ≰T (Wg1(e,i) - Wg2(e,i)) unless (We - Wi) ≤T 0. It follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly.

AB - We show that there do not exist computable functions f1(e,i), f2(e, i), g1(e,i), g2(e,i) such that for all e, i ∈ w, (1) (Wf1(e,i) - Wf2(e,i)) ≤T (We - Wi); (2) (Wg1(e,i) - Wg2(e,i)) ≤T (We - Wi); (3) (We - Wi) ≤T (Wf2(e,i) - Wf2(e.i)) ⊖ (Wg1(e,i) - Wg2(e,i)); (4) (We - Wi) ≰T (Wf1(e,i) - Wf2(e,i)) unless (We - Wi) ≤T 0 and (5) (We - Wi) ≰T (Wg1(e,i) - Wg2(e,i)) unless (We - Wi) ≤T 0. It follows that the splitting theorems of Sacks and Cooper cannot be combined uniformly.

KW - Computably enumerable (c.e.)

KW - Difference of computably enumerable sets (d.c.e., or 2-c.e.)

KW - Splitting and nonsplitting

KW - Turing degrees

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

U2 - 10.1007/s101140100150

DO - 10.1007/s101140100150

M3 - 文章

AN - SCOPUS:0347068838

SN - 1439-8516

VL - 18

SP - 327

EP - 334

JO - Acta Mathematica Sinica, English Series

JF - Acta Mathematica Sinica, English Series

IS - 2

ER -

Non-Uniformity and Generalised Sacks Splitting

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this