Multiple Permitting and Array Noncomputability
| Autor: | Klaus Ambos-Spies |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Sailing Routes in the World of Computation ISBN: 9783319944173 CiE |
| DOI: | 10.1007/978-3-319-94418-0_3 |
| Popis: | Downey et al. [5] have introduced the array noncomputable (a.n.c.) computably enumerable (c.e.) sets which capture certain multiple permitting arguments. In this way they have classified the c.e. degrees below which certain constructions can be performed. More recently, Downey et al. [3] have introduced the not totally \(\omega \)-c.a. c.e. degrees allowing some stronger permitting arguments. Here we introduce a formal notion of multiple permitting which captures the permitting strength of the a.n.c. sets. This notion which – in contrast to array noncomputability – is wtt-invariant allows to simplify the proofs of the basic properties of the a.n.c. sets. Moreover, some results on the a.n.c. sets can be naturally extended to the multiply permitting sets hence to the c.e. sets which are wtt-equivalent to a.n.c. sets. We demonstrate this by showing that multiply permitting sets are not dense simple. Finally, in Ambos-Spies and Losert (ta) the multiply permitting notion introduced here is refined in order to get a new formal characterization of the permitting power of the not totally \(\omega \)-c.a. c.e. degrees too. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|