Nonexistence of minimal pairs for generic computability
Nonexistence of minimal pairs for generic computability
Abstract A generic computation of a subset A of ℕ consists of a computation that correctly computes most of the bits of A , and never incorrectly computes any bits of A , but which does not necessarily give an answer for every input. The motivation for this concept comes …