THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY

DOI10.1017/JSL.2018.4MaRDI QIDQ4579823zbMATH OpenOpenAlexWikidataFDO

Authors Eric P. Astor

Publication date 10 August 2018

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

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

zbMATH Keywords

Turing degreeDNRdominatingintrinsic densitydiagonal non-computablereverse mathematic

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Other Turing degree structures (03D28) Second- and higher-order arithmetic and fragments (03F35)

Abstract: In a previous paper, the author introduced the idea of intrinsic density --- a restriction of asymptotic density to sets whose density is invariant under computable permutation. We prove that sets with well-defined intrinsic density (and particularly intrinsic density 0) exist only in Turing degrees that are either high ($$) or compute a diagonally non-computable function. By contrast, a classic construction of an immune set in every non-computable degree actually yields a set with intrinsic lower density 0 in every non-computable degree. We also show that the former result holds in the sense of reverse mathematics, in that (over $mathsf{RCA}_0$) the existence of a dominating or diagonally non-computable function is equivalent to the existence of a set with intrinsic density 0.

Recommendations

• Computing invariant densities and metric entropy
• scientific article; zbMATH DE number 5504304
• scientific article; zbMATH DE number 10086
• Asymptotic density and computability
• Intrinsic theories and computational complexity
• Density revisited
• scientific article; zbMATH DE number 2222875
• Multiscale inference about a density
• Modelling of one class of densities

Cites work

• A cohesive set which is not high
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Algorithmic randomness and complexity.
• Asymptotic density and the Ershov hierarchy
• Asymptotic density and the coarse computability bound
• Asymptotic density, immunity and randomness
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Coarse reducibility and algorithmic randomness
• Dense computability, upper cones, and minimal pairs
• Generic computability, Turing degrees, and asymptotic density
• Generic-case complexity, decision problems in group theory, and random walks.
• Nonexistence of minimal pairs for generic computability
• Notions of robust information coding
• Randomness and Computability: Open Questions
• Randomness, relativization and Turing degrees
• Subsystems of second order arithmetic
• Turing computability. Theory and applications
• Upward closure and cohesive degrees
• Weakly represented families in reverse mathematics

Cited in

(5)

• INTRINSIC SMALLNESS
• Su alcune proprietà ricorsive legate al concetto di densità
• scientific article; zbMATH DE number 5504304 (Why is no real title available?)
• Fixed point theorems for precomplete numberings
• Asymptotic density, immunity and randomness

This page was built for publication: THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY

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