RE
(
循環 列擧
)는 '예' 答辯을 튜링 機械로 有限한 時間에 檢證할 수 있는 判定 問題의 集合이다. (答辯이 '아니오'인 境遇에는 機械가 멈추지 않을 수도 있다.)
RE
는 튜링 機械가 모든 '예' 예제를 낱낱이 列擧할 수 있는 決定 問題의 集合이기도 하다. 이 定義는 앞쪽 正義랑 同等하다.
RE
의 元素는 모두
循環 列擧 集合
의 元素이기도 하다.
Co-RE
[
編輯
]
co-RE
는 RE에 들어 있는 言語의
補完
(
complement
) 言語의 集合이다. '아니오' 答辯은 튜링 機械로 有限한 時間에 檢證할 수 있지만, '예' 答辯은 檢證하지 못할 수도 있다.
RE는 튜링 機械가 모든 '아니오' 예제를 낱낱이 列擧할 수 있는 決定 問題의 集合이기도 하다.
같이 보기
[
編輯
]
外部 링크
[
編輯
]
