Affiliations: [a] Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 CC Utrecht, the Netherlands. J.vanLeeuwen1@uu.nl | [b] Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vodárenskou věží 2, 182 07 Prague 8, Czech Republic. jiri.wiedermann@cs.cas.cz
Correspondence:
[*]
Address for correspondece: Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 CC Utrecht, The Netherlands.
Note: [†] This research was partially supported by RVO 67985807 and GA ČR grant No. 15-04960S.
Abstract: We resolve an old problem, namely to design a ‘natural’ machine model for accepting the complements of recursively enumerable languages. The model we present is based on non-deterministic Turing machines with ‘one-sided’ advice. We prove that these machines precisely accept the co-RE languages, without restriction on the advice functions that are used. We show that for accepting a co-RE language, one-sided advice is as powerful as arbitrary advice, but also that linearly bounded one-sided advice is sufficient. However, ‘long’ sublinear advice can make Turing machines with one-sided advice accept more co-RE languages than ‘short’ sublinear advice. We prove that infinite proper hierarchies of language classes inside co-RE can be devised, using suitable increasing sequences of bounding functions for the allowed advice. The machine model and the results dualize for the family of recursively enumerable languages.
