کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
424428 | 685443 | 2007 | 13 صفحه PDF | دانلود رایگان |
A class is an effectively closed set of reals. One way to view it is as the set of infinite paths through a computable tree. We consider the notion of acceptably equivalent numberings of classes. We show that a permutation exists between any two acceptably equivalent numberings that preserves the computable content. Furthermore the most commonly used numberings of the classes are acceptably equivalent. We also consider decidable classes in enumerations. A decidable class may be represented by a unique computable tree without dead ends, but we show that this tree may not show up in an enumeration of uniformly computable trees which gives rise to all classes. In fact this is guaranteed to occur for some decidable class. These results are motivated by structural questions concerning the upper semilattice of enumerations of classes where notions such as acceptable equivalence arise.
Journal: Electronic Notes in Theoretical Computer Science - Volume 167, 24 January 2007, Pages 289-301