A Generic relation on Recursively Enumerable Sets

详细

We introduce the concept of a generic relation for algorithmic problems, which preserves the property of being decidable for a problem for almost all inputs and possesses the transitive property. As distinct from the classical m-reducibility relation, the generic relation under consideration does not possess the reflexive property: we construct an example of a recursively enumerable set that is generically incomparable with itself. We also give an example of a set that is complete with respect to the generic relation in the class of recursively enumerable sets.