Dense computability, upper cones, and minimal pairs
Dense computability, upper cones, and minimal pairs
This paper concerns algorithms that give correct answers with (asymptotic) density 1. A dense description of a function g:ω→ω is a partial function f on ω such that {n:f(n)=g(n)} has density 1. We define g to be densely computable if it has a partial computable dense description f. Several previous …