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.
8
$\begingroup$
$\endgroup$
-
$\begingroup$ see A simple problem whose decidability is not known on Theoretical Computer Science. $\endgroup$ – Kaveh Jan 4 '16 at 7:38
5
$\begingroup$
$\endgroup$
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 '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
