Computably inseparable (original) (raw)

In computability theory, two disjoint sets of natural numbers are called computably inseparable or recursively inseparable if they cannot be "separated" with a computable set. These sets arise in the study of computability theory itself, particularly in relation to Π01 classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.