A c.e. real that cannot be sw-computed by any \(\Omega\) number

DOI10.1305/ndjfl/1153858646zbMath1113.03035OpenAlexW1967504445MaRDI QIDQ867401

Andrew E. M. Lewis, George Barmpalias

Publication date: 15 February 2007

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1153858646

zbMATH Keywords

measure of relative randomnessstrong weak truth table reducibilitysw-degrees of c.e. reals

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (10)

Randomness and the linear degrees of computability ⋮ Non-low\(_2\)-ness and computable Lipschitz reducibility ⋮ The computable Lipschitz degrees of computably enumerable sets are not dense ⋮ Maximal pairs of c.e. reals in the computably Lipschitz degrees ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ The ibT degrees of computably enumerable sets are not dense ⋮ A uniform version of non-\(\mathrm{low}_{2}\)-ness ⋮ The method of the Yu–Ding Theorem and its application ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ Unnamed Item

This page was built for publication: A c.e. real that cannot be sw-computed by any \(\Omega\) number