Skip to main content

Is there a language in RE\setminus R$RE \setminus R$ which is not RE$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

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

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.

edited tags; edited tags
Link
Carl Mummert
  • 9.7k
  • 1
  • 46
  • 68
Source Link
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