New answers tagged

1

Having a verifier for a language in general is known as semidecidability, which is actually weaker than decidability. So in general, the answer is no, we can't build a decider for $L$. But if the verifier is efficient (i.e., $L \in $ NP), then indeed $L$ is decidable, and your argument is pretty close for why that is. Let's say we have an efficient verifier $...


0

A language is said to be co-Turing-Recognisable or co-Recursively Enumerable if it is the complement of a Turing recognisable Language. We can show that if a language L is Turing recognisable and it is co-Turing-Recognisable meaning that it's complement is also Turing recognisable then this language is decidable (this may be useful to use as a contradiction ...


Top 50 recent answers are included