New answers tagged semi-decidability
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
