Can I read Enumerations of Π10 Classes: Acceptability and Decidable Classes on EtoBox?

Enumerations of Π10 Classes: Acceptability and Decidable Classes by Paul Brodhead is a Computer Science article available to read on EtoBox.

What is Enumerations of Π10 Classes: Acceptability and Decidable Classes about?

A Π 0 1 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 Π 0 1 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 Π 0 1 classes are acceptably equivalent. We also consider decidable Π 0 1 classes in enumerations. A decidable Π 0 1 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 Π 0 1 classes. In fact this is guaranteed to occur for some decidable Π 0 1 class. These results are motivated by structural questions concerning the upper semilattice of enumerations of Π 0 1 classes where notions such as acceptable equivalence arise.

Who reads Enumerations of Π10 Classes: Acceptability and Decidable Classes?

Author

Paul Brodhead

Publisher

Elsevier Science; Elsevier ; Elsevier BV; Amsterdam: Elsevier BV (ISSN 1571-0661)

Published

2007

Language

EN

Field

Computer Science (Physical Sciences)