On low for speed oracles

DOI10.4230/LIPICS.STACS.2018.15MaRDI QIDQ3304109zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, Rodney G. Downey

Publication date 5 August 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2018.15

zbMATH Keywords

lowness for speedoracle computationsTuring degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• On low for speed oracles
• Separating the low and high hierarchies by oracles
• Being low along a sequence and elsewhere
• scientific article; zbMATH DE number 4011940
• Bad oracles in higher computability and randomness

Cites work

• Algorithmic randomness and complexity.
• Computability and randomness
• scientific article; zbMATH DE number 3715539 (Why is no real title available?)
• Limits on the computational power of random strings
• On Effective Procedures for Speeding Up Algorithms
• On the degrees less than 0'
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• The degrees below a 1-generic degree < 0′
• Theory of computation.
• Turing computability. Theory and applications
• What can be efficiently reduced to the Kolmogorov-random strings?

Cited in

(2)

• A MINIMAL SET LOW FOR SPEED
• Speed-up theorems in type-2 computations using oracle Turing machines

This page was built for publication: On low for speed oracles

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