Extending CL-reducibility on array noncomputable degrees
Given a function f, f-bounded-Turing (f-bT-) reducibility is the Turing reducibility with use function bounded by f. In the special case where f=id+c (with id being the identity function and c a constant), this is referred to as cl-reducibility. In a work by Barmpalias, Fang, and Lewis-Pye, it was p...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
28 November 2024
|
| In: |
Information and computation
Year: 2025, Volume: 303, Pages: 1-11 |
| ISSN: | 1090-2651 |
| DOI: | 10.1016/j.ic.2024.105258 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.1016/j.ic.2024.105258 Verlag, kostenfrei, Volltext: https://www.sciencedirect.com/science/article/pii/S0890540124001238 
|
| Author Notes: | Nan Fang, Wolfgang Merkle |
MARC
| LEADER | 00000naa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1934675733 | ||
| 003 | DE-627 | ||
| 005 | 20250825202211.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 250825s2025 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1016/j.ic.2024.105258 |2 doi | |
| 035 | |a (DE-627)1934675733 | ||
| 035 | |a (DE-599)KXP1934675733 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Fang, Nan |d 1991- |e VerfasserIn |0 (DE-588)1196037493 |0 (DE-627)1677911077 |4 aut | |
| 245 | 1 | 0 | |a Extending CL-reducibility on array noncomputable degrees |c Nan Fang, Wolfgang Merkle |
| 264 | 1 | |c 28 November 2024 | |
| 300 | |a 11 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 25.08.2025 | ||
| 520 | |a Given a function f, f-bounded-Turing (f-bT-) reducibility is the Turing reducibility with use function bounded by f. In the special case where f=id+c (with id being the identity function and c a constant), this is referred to as cl-reducibility. In a work by Barmpalias, Fang, and Lewis-Pye, it was proven that there exist two left-c.e. reals such that no left-c.e. real (id+g)-bT-computes both of them whenever g is computable, nondecreasing, and satisfies ∑n2−g(n)=∞. Moreover, such maximal pairs exist precisely within every array noncomputable degree. This result generalizes a prior result on cl-reducibility, which states that there exist two left-c.e. reals such that no left-c.e. real cl-computes both of them. An open question remained as to whether a similar extension could apply to another result on cl-reducibility, which asserts that there exists a left-c.e. real not cl-reducible to any random left-c.e. real. We answer this question affirmatively, providing a simpler proof compared to previous works. Additionally, we streamline the proof of the initial extension. | ||
| 700 | 1 | |a Merkle, Wolfgang |e VerfasserIn |0 (DE-588)1049898400 |0 (DE-627)782852831 |0 (DE-576)40388201X |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Information and computation |d Amsterdam : Elsevier, 1987 |g 303(2025) vom: März, Artikel-ID 105258, Seite 1-11 |h Online-Ressource |w (DE-627)26688170X |w (DE-600)1468010-5 |w (DE-576)10337308X |x 1090-2651 |7 nnas |a Extending CL-reducibility on array noncomputable degrees |
| 773 | 1 | 8 | |g volume:303 |g year:2025 |g month:03 |g elocationid:105258 |g pages:1-11 |g extent:11 |a Extending CL-reducibility on array noncomputable degrees |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.ic.2024.105258 |x Verlag |x Resolving-System |z kostenfrei |3 Volltext |
| 856 | 4 | 0 | |u https://www.sciencedirect.com/science/article/pii/S0890540124001238 |x Verlag |z kostenfrei |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20250825 | ||
| 993 | |a Article | ||
| 994 | |a 2025 | ||
| 998 | |g 1049898400 |a Merkle, Wolfgang |m 1049898400:Merkle, Wolfgang |d 110000 |d 110300 |e 110000PM1049898400 |e 110300PM1049898400 |k 0/110000/ |k 1/110000/110300/ |p 2 |y j | ||
| 999 | |a KXP-PPN1934675733 |e 4763989626 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"physDesc":[{"extent":"11 S."}],"relHost":[{"title":[{"title_sort":"Information and computation","title":"Information and computation"}],"note":["Gesehen am 16.07.13"],"type":{"bibl":"periodical","media":"Online-Ressource"},"disp":"Extending CL-reducibility on array noncomputable degreesInformation and computation","recId":"26688170X","language":["eng"],"pubHistory":["72.1987 - 209.2011; Vol. 210.2012 -"],"part":{"pages":"1-11","year":"2025","extent":"11","text":"303(2025) vom: März, Artikel-ID 105258, Seite 1-11","volume":"303"},"origin":[{"dateIssuedDisp":"1987-","dateIssuedKey":"1987","publisher":"Elsevier ; Academic Press","publisherPlace":"Amsterdam ; Orlando, Fla."}],"id":{"issn":["1090-2651"],"zdb":["1468010-5"],"eki":["26688170X"]},"physDesc":[{"extent":"Online-Ressource"}]}],"name":{"displayForm":["Nan Fang, Wolfgang Merkle"]},"origin":[{"dateIssuedKey":"2025","dateIssuedDisp":"28 November 2024"}],"id":{"doi":["10.1016/j.ic.2024.105258"],"eki":["1934675733"]},"note":["Gesehen am 25.08.2025"],"type":{"bibl":"article-journal","media":"Online-Ressource"},"language":["eng"],"recId":"1934675733","person":[{"family":"Fang","given":"Nan","roleDisplay":"VerfasserIn","display":"Fang, Nan","role":"aut"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Merkle, Wolfgang","given":"Wolfgang","family":"Merkle"}],"title":[{"title":"Extending CL-reducibility on array noncomputable degrees","title_sort":"Extending CL-reducibility on array noncomputable degrees"}]} | ||
| SRT | |a FANGNANMEREXTENDINGC2820 | ||