Asymptotic Density and the Theory of Computability: A partial survey

2016/10/20 by Carl G. Jockusch, Jockusch, Carl G., Paul E. Schupp +1
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Benford’s Law and Fraud Detection #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1610.06504

Abstract

In this article we survey the development of generic and coarse computability and the main results on how classical asymptotic density interacts with the theory of computability.

Related

• Asymptotic Density and Computably Enumerable Sets
• Asymptotic density and the coarse computability bound
• The computational content of intrinsic density
• Dense computability, upper cones, and minimal pairs
• From Nonstandard Analysis to various flavours of Computability Theory