1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Non-membership is always in $\emptyset'$, since given $x$, you can decide whether $\exists y \, f(x,y)$ using an oracle for the halting problem. $\endgroup$ – Yuval Filmus Nov 2 '18 at 6:43
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.