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 nondeterministic 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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.