HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Problems whose decidability status is unknown but known to be less hard than the halting problem

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#51290, answer score: 5

Revisions (0)

No revisions yet.