Post's Programme for the Ershov Hierarchy
| dc.contributor.author | AFSHARI, Bahareh | en_US |
| dc.contributor.author | BARMPALIAS, George | en_US |
| dc.contributor.author | COOPER, S. Barry | en_US |
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.date.accessioned | 2006-11-02T02:04:01Z | en_US |
| dc.date.accessioned | 2017-01-23T06:59:56Z | |
| dc.date.available | 2006-11-02T02:04:01Z | en_US |
| dc.date.available | 2017-01-23T06:59:56Z | |
| dc.date.issued | 2006-10-31 | en_US |
| dc.description.abstract | 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'. | en_US |
| dc.format.extent | 527375 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/2253 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TR10/06 | en_US |
| dc.title | Post's Programme for the Ershov Hierarchy | en_US |
| dc.type | Technical Report | en_US |