1

As stated, is there any decision problems in the complexity class RE that are neither RE-complete nor recursive?

It seems that almost all of nonrecursive RE problems are in RE-complete...

user2346
  • 631
  • 2
  • 7
  • 14

1 Answers1

3

This is known as Post's problem and the answer is yes. The first such problem (and the only one I am familiar with) was constructed using forcing and the method of finite injury.

Alex Becker
  • 60,569