재귀 열거 언어
1. 개요
재귀 열거 언어는 해당 알파벳으로 구성된 모든 문자열의 집합에서 재귀 열거 가능한 부분 집합이다. 재귀 열거 언어는 형식 언어의 한 종류로, 튜링 머신(또는 다른 계산 가능한 함수)을 사용하여 정의될 수 있으며, 언어에 속하는 모든 문자열을 열거하거나, 해당 문자열이 언어에 속하는지 여부를 판별할 수 있는 튜링 머신이 존재한다. 정규 언어, 문맥 자유 언어, 문맥 의존 언어, 재귀 언어는 모두 재귀 열거 언어에 속한다. 재귀 열거 언어는 클레이니 스타, 연결, 합집합, 교집합 연산에 닫혀 있지만, 차집합과 여집합 연산에는 닫혀 있지 않다.
| 유형 | 형식 언어 부류 |
|---|---|
| 분야 | 계산 가능성 이론, 계산 복잡도 이론 |
| 포함 관계 | 문맥 민감 언어 ⊆ 재귀 열거 언어 ⊆ 재귀 언어 |
| 다른 이름 | 재귀 가산 언어 튜링 인식 가능 언어 0형 언어 |
| 튜링 기계 | 튜링 기계에 의해 인식됨 |
|---|---|
| 클린 정리 | 형식 문법에 의해 생성됨 |
-
앨런 튜링 -
튜링 테스트
-
앨런 튜링 -
이미테이션 게임
-
형식 언어 -
문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다. -
형식 언어 -
튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다. -
언어학에 관한 -
세례명
세례명은 기독교에서 세례를 받을 때 받는 새로운 이름으로, 예수 그리스도 안에서 새롭게 태어남을 의미하며, 성경 속 인물들의 이름 변화에서 유래하여 중세 이후 유럽에서 일반적인 이름 형태로 정착되었고, 수호성인의 이름에서 따와 이름 축일로 기념되기도 한다. -
언어학에 관한 -
개명
개명은 개인이나 법인이 이름을 바꾸는 행위로, 결혼, 이혼, 이민, 종교 개종, 성 정체성 확인, 사회적 이미지 개선, 범죄 회피 등 여러 이유로 행해지며, 절차는 국가별로 다르지만 법적 제약과 고려 사항이 따른다.
2. 정의
재귀 열거 언어는 다음 세 가지와 같이 정의할 수 있다.
# 형식 언어의 알파벳에서 생성 가능한 모든 단어 집합 중, 귀납적 가산인 부분 집합이다.
# 해당 언어에 포함된 모든 문자열을 열거하는 튜링 기계 (또는 계산 가능 함수)가 존재하는 형식 언어이다.
# 입력된 문자열이 해당 언어에 포함될 경우 이를 수락하고 정지하는 튜링 기계 (또는 계산 가능 함수)가 존재하는 형식 언어이다. 단, 입력된 문자열이 해당 언어에 포함되지 않을 경우, 정지하여 거부할 수도 있고, 무한 루프에 빠질 수도 있다.
2.1. 형식 언어 관점
재귀 열거 언어는 형식 언어의 알파벳으로 만들 수 있는 모든 문자열의 집합 중에서 재귀 열거인 부분집합이다.
재귀 열거 언어에는 다음과 같은 동등한 정의들이 있다.
* 튜링 기계 (또는 다른 계산 가능한 함수)가 해당 언어의 모든 유효한 문자열을 열거할 수 있다. 언어가 무한인 경우, 반복을 피하도록 열거 알고리즘을 선택할 수 있다. 숫자 n에 대해 생성된 문자열이 n보다 작은 숫자에 대해 이미 생성되었는지 확인하고, 이미 생성된 경우 입력 n+1에 대한 출력을 대신 사용한다(재귀적으로). 그러나 이 경우에도 n+1에 대한 출력이 새로운지 확인해야 한다.
* 튜링 기계 (또는 다른 계산 가능한 함수)에 해당 언어의 문자열을 입력하면 중지하고 수락하지만, 해당 언어에 없는 문자열을 입력하면 중지하고 거부하거나 영원히 반복할 수 있다. 이는 튜링 머신이 모든 경우에 중지해야 하는 재귀 언어와 대조된다.
모든 정규 언어, 문맥 자유 언어, 문맥 민감 언어, 재귀 언어는 재귀 열거 언어이다.
2.2. 튜링 기계 관점
재귀 열거 언어는 다음 조건을 만족하는 튜링 기계(혹은 다른 계산 가능한 함수)가 존재하는 형식 언어이다.
* 어떤 문자열이 그 언어에 속하면 튜링 기계는 정지하고 승인한다.
* 어떤 문자열이 그 언어에 속하지 않으면 튜링 기계는 정지하고 거절하거나 영원히 멈추지 않을 수 있다.
이는 튜링 기계가 모든 경우에 정지해야 하는 재귀 언어와는 대조된다.
만약 언어가 무한하다면, 반복을 피하도록 하는 알고리듬을 선택할 수 있다. 숫자 n으로 산출된 문자열이 이미 더 작은 숫자 n에서 산출됐는지 확인할 수 있기 때문이다. 만약 이미 산출된 결과라면, 출력을 입력 n+1으로 대신 (귀납적으로) 사용하지만, 반복해서 새로운지 확인이 필요하다.
2.3. 수락/거부 관점
재귀 열거 언어는 어떤 언어의 문자열이 입력으로 주어질 때 정지하고 수락하지만, 언어에 속하지 않는 문자열이 주어질 때는 정지하고 거부하거나 영원히 반복할 수 있는 튜링 기계 (또는 다른 계산 가능 함수)가 존재하는 형식 언어이다. 이는 튜링 기계가 모든 경우에 정지해야 하는 재귀 언어와 대조된다.
2.5. 복잡도 종류
재귀 열거 언어 집합은 복잡도 종류 RE로 나타낸다. RE와 그 여집합인 co-RE는 산술적 계층의 기반이 된다.
3. 예시
정지하는 튜링 기계의 집합은 재귀적으로 열거 가능하지만 재귀적이지는 않다. 실제로 튜링 기계를 실행하고 기계가 정지하면 수용할 수 있으므로 재귀적으로 열거 가능하다. 반면에 이 문제는 풀 수 없다.
재귀적이지 않은 다른 재귀적으로 열거 가능한 언어는 다음과 같다.
* 포스트 대응 문제
* 사망 문제 (계산 가능성 이론)
* 결정 문제
4. 닫힘 성질
재귀 열거 언어는 특정 연산에 대해 닫혀 있는 성질을 가지고 있다. L과 P가 재귀 열거 언어일 때, 이들의 클레이니 스타, 연결, 합집합, 교집합 연산 결과 역시 재귀 열거 언어이다. 하지만, 재귀 열거 언어는 차집합이나 여집합에 대해서는 닫혀 있지 않다.