Page 282

		This conjecture is appealing but false. The collection of self-describing functions, , is identifiable, but it is easily shown that cannot be identified by any scientist that is an enumerator.

		In defense of Gold's intuitions, refutation of his conjecture via seems like a trick. After all, to identify requires no more than fetching some coded value from the input function. In the 1970's, Barzdins * formulated a more sophisticated version of Gold's conjecture designed to transcend such counterexamples. He reasoned that if a class of functions is identifiable only by way of a self-referential property, then there would be a total recursive operator that would transform the class into an unidentifiable one. The idea is that if a scientist is able to find the embedded self-referential information in the elements of a class, so can a total recursive operator which can then weed out this information. To see this in the context of , consider the operator such that, if , then g(x) = f(x + 1), for all . essentially "shifts the function f to the left." It is easy to see that, and we know from prior work that . Thus, transforms the identifiable class into an unidentifiable class by removing the self-referential information from that made it identifiable.

		Informally stated, Barzdins'* conjecture is:

		If the projection of a class of functions under all total recursive operators is identifiable, then the class is identifiable by enumeration.

		More formally, we have:

		13.3 Definition (Fulk [72]) is said to be robustly Ex-identifiable just in case for all total recursive operators , .

		13.4 Conjecture (Barzdins* as formalized by Fulk [72]) Every subclass of that is robustly Ex-identifiable is contained in some r.e. indexable subclass of .

		This conjecture is also appealing, and also false. The next section presents a cunning refutation due to Fulk [72]. Beyond simply showing the conjecture to be false, the refutation demonstrates an identification strategy that is strictly more general than enumeration but in the same spirit.

		§13.2 Fulk's Refutation of Barzdins'* Conjecture

		Here is Fulk's result.