NON-SPLITTINGS OF SPEEDABLE SETS

DOI10.1017/JSL.2014.83MaRDI QIDQ5501773zbMATH OpenOpenAlexFDO

Authors Ellen S. Chih

Publication date 14 August 2015

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.1986

zbMATH Keywords

splittingsspeedable sets

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15)

Abstract: An r.e. set $A$ is speedable if for every recursive function, there exists a program enumerating membership in $A$ faster, by the desired recursive factor, on infinitely many integers. We construct a speedable set that cannot be split into speedable sets. This solves a question of B"{a}uerle and Remmel.

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• A recursively enumerable degree which will not split over all lesser ones
• On speedable and levelable vector spaces
• On the degrees less than 0'
• Some lowness properties and computational complexity sequences

This page was built for publication: NON-SPLITTINGS OF SPEEDABLE SETS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501773)