On a question of nearly minimal identification of functions

Author: Sanjay Jain

Source: Information Processing Letters Vol. 70, No. 3, 1999, 113 - 117.

Abstract. Suppose A and B are classes of recursive functions. A is said to be an m-cover (*-cover) for B, iff for each g B, there exists an f A such that f differs from g on at most m inputs (finitely many inputs). C, a class of recursive functions, is a-immune iff C is infinite and every recursively enumerable subclass of C has a finite a-cover. C is a-isolated iff C is finite or a-immune.

Chen (1981) conjectured that every class of recursive functions that is MEx^*_m-identifiable is *-isolated. We refute this conjecture.