School of Computing

Permanent URI for this community

Now showing 1 - 1 of 1

Post's Programme for the Ershov Hierarchy
(2006-10-31) AFSHARI, Bahareh; BARMPALIAS, George; COOPER, S. Barry; STEPHAN, Frank
This paper extends Post's programme to finite levels of the Ershov hierarchy of limit-computable sets. Our initial characterisation, in the spirit of Post's paper from 1944, of the degrees of the immune and hyperimmune n-enumerable sets leads to a number of results setting other immunity properties in the context of the Turing and wtt-degrees derived from the Ershov hierarchy. For instance, we show that any n-enumerable hyperhyperimmune set must be co-enumerable, for each The situation with regard to the wtt-degrees is particularly interesting, as demonstrated by a range of results concerning the wtt-predecessors of hypersimple sets. Finally, we give a number of results directed at characterising, in terms of natural information content. For example, a 2-enumerable degree contains a 2-enumerable dense immune set iff it contains a 2-enumerable r-cohesive set iff it bounds a high enumerable set. This result is extended to a characterisation of n-enumerable degrees which bound high enumerable degrees. Furthermore, a characterisation for n-enumerable degrees is given which only bound enumerable sets A with A''=K'.