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.


1 Answer 1


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.

  • 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, 2015 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, 2015 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.