patternMinor
Problems whose decidability status is unknown but known to be less hard than the halting problem
Viewed 0 times
problemthewhoseunknownbutthanhardhaltingstatusless
Problem
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#51290, answer score: 5
Revisions (0)
No revisions yet.