A c.e. real that cannot be sw-computed by any number

DOI10.1305/NDJFL/1153858646zbMATH Open1113.03035OpenAlexW1967504445MaRDI QIDQ867401FDOQ867401

Authors: George Barmpalias, Andrew E. M. Lewis 

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

Recommendations

• \(\mathcal M^2\)-computable real numbers
• Weakly computable real numbers
• On \(0'\)-computable reals
• On the computational properties of the uncountability of the real numbers
• A non-generic real incompatible with \(0^\sharp\)
• Undefinability results in o-minimal expansions of the real numbers
• On Σ‐definability without equality over the real numbers
• scientific article; zbMATH DE number 1136091
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• scientific article; zbMATH DE number 5287432

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)

Cited In (13)

• New Computational Paradigms
• The ibT degrees of computably enumerable sets are not dense
• The method of the Yu–Ding Theorem and its application
• A uniform version of non-\(\mathrm{low}_{2}\)-ness
• There is no SW-complete c.e. real
• Some properties of sw-reducibility
• The computable Lipschitz degrees of computably enumerable sets are not dense
• Maximal pairs of c.e. reals in the computably Lipschitz degrees
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Randomness and the linear degrees of computability
• Title not available (Why is that?)
• Non-low\(_2\)-ness and computable Lipschitz reducibility
• Working with strong reducibilities above totally \(\omega \)-c.e. and array computable degrees

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

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