Are there problems the decidability of which is unknown but it is known for certain that the problems are less hard than the halting problem.


Assuming that by "less hard" you mean "reducible to", then any problem that is known to be in $RE$ but not known to be in $R$ satisfies this condition.

For example, take the PCP problem with 4 tiles, whose decidability is open. It is an easy exercise to reduce the problem (or any other problem in RE) to HALT.

| cite | improve this answer | |
  • 2
    $\begingroup$ It is not known that HALT can be reduced to PCP with 4 tiles. The latter is an open problem. $\endgroup$ – Shaull Dec 30 '15 at 16:45
  • 1
    $\begingroup$ It is mentioned (I wrote that the decidability of it is not known, it is implied that there is no known reduction from HALT). $\endgroup$ – Shaull Dec 30 '15 at 17:13

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.