Skip to main content
1 of 3
puzne
  • 87
  • 7

Is there a language in RE\setminus R which is not RE-complete?

If any recursively enumerable language can be reduced by a mapping reduction to a language $L$, then $L$ is called $RE$ complete. In that case, $L$ must be in $RE\setminus R$. But are there languages in $RE\setminus R$ which are not $RE$ complete? Can anyone give an example of such a language? I'm sure this is well known, but it's not well known to me, and google doesn't help..

Thanks, me

puzne
  • 87
  • 7