Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
A language is called semi-decidable if there is an algorithm for identifying members. There are well-known examples of semi-decidable languages where identifying non-members is equivalent to $\emptyset'$, such as the Halting Problem.
My question is: how hard can identifying non-membership be?
A language $L$ is semidecidable if there exists a computable predicate $f$ such that $$ x \in L \Leftrightarrow \exists y \, f(x,y). $$ We can construct a machine $M$ which halts on $x$ iff $\exists y \, f(x,y)$: the machine just goes over all possible $y$, for each one checks whether $f(x,y)$, and if so, halts. This shows that we can decide $L$ using an oracle to the halting problem, i.e., using an $\emptyset'$-machine.
