Department of Pure Mathematics, University of Waterloo, Waterloo, ON, Canada N2L 3G1 E-mail: csima{at}math.uwaterloo.ca
Abstract:
The settling time reducibility ordering gives an ordering oncomputably enumerable sets based on their enumerations. The<st ordering is in fact an ordering on c.e. sets, since itis independent of the particular enumeration chosen. In thisarticle, we show that it is not possible to extend this orderingin an approximation-independent way to sets in general, or even to n-c.e. sets for anyfixed n 3.