THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY

DOI10.1017/JSL.2018.4zbMATH Open1436.03223arXiv1708.04267OpenAlexW2963179791WikidataQ129430096 ScholiaQ129430096MaRDI QIDQ4579823FDOQ4579823

Authors: Eric P. Astor 

Publication date: 10 August 2018

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• INTRINSIC SMALLNESS
• Su alcune proprietà ricorsive legate al concetto di densità
• Title not available (Why is that?)
• 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)