재귀 열거 언어

재귀적 열거 가능 언어(再歸的列擧可能言語, 영어: Recursively enumerable language, 귀납적 가산 언어(歸納的可算言語)), 부분 결정성 언어 또는 튜링 수리성 언어는 계산 이론과 수리논리학에서 다루는 형식 언어의 종류로, 문자열의 집합의 재귀 열거인 부분집합이다. 촘스키 위계의 type-0 언어이기도 하다. 재귀 열거 언어의 모임을 RE라고 한다.

재귀 열거 언어의 개념에 관한 세개의 동등한 주요 정리가 존재한다.

1. 재귀 열거 언어는 언어의 문자로 만들 수 있는 재귀 열거 집합의 부분집합이다.
2. 재귀 열거 언어는 언어의 모든 옳은 문자열을 세는 튜링 기계 (또는 다른 계산 가능 함수)가 존재하는 형식언어이다. 주목할 것은 만약 언어가 무한하다면 제공된 가산알고리듬을 고를 수 있어 반복을 피할 수 있는데 우리가 숫자 n으로 산출된 문자열이 이미 더 작은 숫자 n에서 산출됐는지 확인할 수 있기 때문이다. 만약 이미 산출된 결과라면, 출력을 입력 n+1으로 대신 (귀납적으로)사용하지만, 반복해서 새로운지 확인이 필요하다.
3. 재귀 열거 언어는 어떤 언어의 문자열이 입력으로 주어질때 서고 승인하지만 언어에 속하지 않은 문자열이 주어질때 정지하고 거절하는 튜링 기계 (또는 다른 계산 가능 함수)이 존재하는 형식언어이다. 튜링머신이 정지하는 필요한 모든 경우에 이것을 재귀 언어와 대조한다.

모든 정규 언어, 문맥 자유 언어, 문맥 의존 언어, 재귀 언어는 재귀 열거 언어이다.

RE, 그것의 보완물 co-RE는 산술적 위계의 기반이 되고 있다.

재귀 열거 언어는 다음 과정에 대해 닫혀있다. 만약 L 과 P 가 재귀 열거 언어라면 다음의 언어는 재귀 열거 언어이다.

• L의 클레이니 스타(Kleene star): ${\displaystyle L^{*}}$
• L과P의 연결: ${\displaystyle L\circ P\,}$
• L과P의 합집합: ${\displaystyle L\cup P\,}$
• L과P의 교집합: ${\displaystyle L\cap P\,}$

주목할 것은 재귀 열거 언어는 차집합이나 여집합에서는 닫혀있지 않다는 것이다. 차집합 L\P는 재귀 열거 언어일 수도 아닐 수도 있다. 만약 L이 재귀 열거 언어라면, L의 여집합은 재귀 열거 언어인 경우에만 L이 또한 귀납적이다.

• 재귀 언어