Splittings of effectively speedable sets and effectively levelable sets
The paper studies a theoretical notion of computation speedability in the spirit of \textit{M. Blum} and \textit{I. Marques} [J. Symb. Log. 38, 579--593 (1973; Zbl 0335.02024)]. A computably enumerable set \(A\) is speedable if for any \(i\) such that \(A=W_i\) and for any computable function \(h\) there exists a \(j\) such that \(A=W_j\) and \[ (\exists^\infty x)[\Phi_i(x)>h(x,\Phi_j(x))]. \] \(A\) is effectively speedable if \(j\) can be found uniformly from \(i\) and an index of \(h\). A computably enumerable set \(A\) is levelable if there exists a computable function \(r\) such that for every \(i\) with \(A=W_i\) and for every computable function \(h\) there is \(j\) such that \(A=W_j\) and \[ (\exists^\infty x)[\Phi_i(x)>h(x) \text{ and} \Phi_j(x)<r(x)]. \] \(A\) is effectively levelable if \(j\) can be found uniformly from \(i\) and an index of \(h\). Speedable and levelable sets have been widely studied by Blum, Marques, Gill and Morris, Soare and others. Remmel, while studying splitting properties of spedable sets, posed several questions about possible splittings of speedable sets. One of them was, whether a speedable (effectively speedable) set can be always split into two speedable (effectively speedable) sets. The same question was raised for levelable and effectively levelable sets, but the answer to both questions was unknown for years. In the paper, the author gives answers to these questions showing that a computably enumerable set \(A\) is effectively speedable (effectively levelable) if and only if it is splittable into two effectively speedable (effectively levelable) sets. The proof of both results uses properties of the notion of \(\overline Q\)-reducibility, introduced and studied by the author.
- A Machine-Independent Theory of the Complexity of Recursive Functions
- Computability and models. Perspectives east and west
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- On speedable and levelable vector spaces
- On the size of machines
- Reducibility and Completeness for Sets of Integers
- Splitting theorems and the jump operator
- Splitting theorems in recursion theory
This page was built for publication: Splittings of effectively speedable sets and effectively levelable sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311714)