co-RE는 RE에 들어 있는 언어의 보완(complement) 언어의 집합이다. '아니오' 답변은 튜링 기계로 유한한 시간에 검증할 수 있지만, '예' 답변은 검증하지 못할 수도 있다.
RE는 튜링 기계가 모든 '아니오' 예제를 낱낱이 열거할 수 있는 결정 문제의 집합이기도 하다.
