Is there a difference between a non computable problem and an undecidable problem? Or is one included in the other?
1
$\begingroup$
$\endgroup$
2
$\begingroup$
$\endgroup$
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.
-
$\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
