I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can you please share some examples or a URL link? Is the NP problem a semidecidable problem? If yes, then it means that NP-complete problems are Recursive enumerable. Please correct me if I am wrong.

I am thankful to you.


This is just equivalent to the class of RE problems (strictly RE\R). So one example would be finding whether a Diophantine equation has a solution.

  • A program could "solve" this problem by iterating through all possible combinations of variables, and testing them. If a solution exists, the program halts and returns yes. If a solution doesn't, the program does not halt.

Here is a wikipedia link for more information: https://en.wikipedia.org/wiki/RE_(complexity)

| cite | improve this answer | |

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.