1
$\begingroup$

Is there a difference between a non computable problem and an undecidable problem? Or is one included in the other?

$\endgroup$
2
$\begingroup$

Non computable problems are also undecidable. Basically undecidable is a subset of non computable.

This is because if you can't even say yes or no then you can't compute it. Take for example the Halting Problem of a Turing Machine, suppose someone asked you after how many steps the Turing Machine will halt on a given input. To answer the exact number you first have to answer whether the Turing Machine is going to halt or not. Then i may count the steps.

What we do is to convert our optimization problem to a decision problem. And if we are not able to give answer of that decision problem we cannot compute it. So, computing is harder than saying yes or no. So if the problem is undecidable then it will be also non computable.

$\endgroup$
  • $\begingroup$ Sorry to comment on such an old answer, but the second sentence through me off. I don't think you mean to say that undecidable is a subset of non computable. I think you meant to say it is a superset. If it were a subset, then there would exist non computable problems that are decidable. $\endgroup$ – sunnyohno Sep 24 '17 at 15:32

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.