재귀 열거 언어
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
재귀 열거 언어는 해당 알파벳으로 구성된 모든 문자열의 집합에서 재귀 열거 가능한 부분 집합이다. 재귀 열거 언어는 형식 언어의 한 종류로, 튜링 머신(또는 다른 계산 가능한 함수)을 사용하여 정의될 수 있으며, 언어에 속하는 모든 문자열을 열거하거나, 해당 문자열이 언어에 속하는지 여부를 판별할 수 있는 튜링 머신이 존재한다. 정규 언어, 문맥 자유 언어, 문맥 의존 언어, 재귀 언어는 모두 재귀 열거 언어에 속한다. 재귀 열거 언어는 클레이니 스타, 연결, 합집합, 교집합 연산에 닫혀 있지만, 차집합과 여집합 연산에는 닫혀 있지 않다.
더 읽어볼만한 페이지
- 앨런 튜링 - 튜링 테스트
튜링 테스트는 앨런 튜링이 제안한 기준으로, 기계가 인간과 구별할 수 없을 정도로 행동하는지 판별하며, 뢰브너 상 등을 통해 실현 가능성과 한계에 대한 논쟁이 지속되고 있고, 유진 구스트만, LaMDA, ChatGPT 등이 테스트 통과 또는 자의식 논란을 일으키고 있다. - 앨런 튜링 - 이미테이션 게임
제2차 세계 대전 당시 독일군의 에니그마 암호 해독에 결정적인 역할을 한 수학자 앨런 튜링의 실화를 바탕으로, 암호 해독팀이 암호 해독 기계 "봄베"를 개발하는 과정과 전후 동성애 사실이 밝혀져 박해받는 그의 비극적인 삶을 그린 2014년 영화이다. - 계산 이론 - 튜링 완전
튜링 완전은 계산 이론에서 시스템이 튜링 기계와 동등한 계산 능력을 갖춰 튜링 기계가 계산할 수 있는 모든 함수를 계산하고 범용 튜링 기계를 시뮬레이션할 수 있음을 의미하며, 튜링 동등이라고도 한다. - 계산 이론 - 디지털 물리학
디지털 물리학은 우주를 거대한 디지털 컴퓨터로 보고 정보 이론, 통계 역학, 양자역학 등을 융합하여 우주의 작동 방식을 디지털 계산 과정으로 설명하려는 이론적 관점이다. - 형식 언어 - 문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다. - 형식 언어 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
| 재귀 열거 언어 | |
|---|---|
| 개요 | |
| 유형 | 형식 언어 부류 |
| 분야 | 계산 가능성 이론, 계산 복잡도 이론 |
| 포함 관계 | 문맥 민감 언어 ⊆ 재귀 열거 언어 ⊆ 재귀 언어 |
| 다른 이름 | 재귀 가산 언어 튜링 인식 가능 언어 0형 언어 |
| 특징 | |
| 튜링 기계 | 튜링 기계에 의해 인식됨 |
| 클린 정리 | 형식 문법에 의해 생성됨 |
2. 정의
재귀 열거 언어는 다음 세 가지와 같이 정의할 수 있다.
# 형식 언어의 알파벳에서 생성 가능한 모든 단어 집합 중, 귀납적 가산인 부분 집합이다.
# 해당 언어에 포함된 모든 문자열을 열거하는 튜링 기계 (또는 계산 가능 함수)가 존재하는 형식 언어이다.
# 입력된 문자열이 해당 언어에 포함될 경우 이를 수락하고 정지하는 튜링 기계 (또는 계산 가능 함수)가 존재하는 형식 언어이다. 단, 입력된 문자열이 해당 언어에 포함되지 않을 경우, 정지하여 거부할 수도 있고, 무한 루프에 빠질 수도 있다.
2. 1. 형식 언어 관점
재귀 열거 언어는 형식 언어의 알파벳으로 만들 수 있는 모든 문자열의 집합 중에서 재귀 열거인 부분집합이다.재귀 열거 언어에는 다음과 같은 동등한 정의들이 있다.
- 튜링 기계 (또는 다른 계산 가능한 함수)가 해당 언어의 모든 유효한 문자열을 열거할 수 있다. 언어가 무한인 경우, 반복을 피하도록 열거 알고리즘을 선택할 수 있다. 숫자 ''n''에 대해 생성된 문자열이 ''n''보다 작은 숫자에 대해 이미 생성되었는지 확인하고, 이미 생성된 경우 입력 ''n''+1에 대한 출력을 대신 사용한다(재귀적으로). 그러나 이 경우에도 ''n''+1에 대한 출력이 새로운지 확인해야 한다.
- 튜링 기계 (또는 다른 계산 가능한 함수)에 해당 언어의 문자열을 입력하면 중지하고 수락하지만, 해당 언어에 없는 문자열을 입력하면 중지하고 거부하거나 영원히 반복할 수 있다. 이는 튜링 머신이 모든 경우에 중지해야 하는 재귀 언어와 대조된다.
모든 정규 언어, 문맥 자유 언어, 문맥 민감 언어, 재귀 언어는 재귀 열거 언어이다.
2. 2. 튜링 기계 관점
재귀 열거 언어는 다음 조건을 만족하는 튜링 기계(혹은 다른 계산 가능한 함수)가 존재하는 형식 언어이다.- 어떤 문자열이 그 언어에 속하면 튜링 기계는 정지하고 승인한다.
- 어떤 문자열이 그 언어에 속하지 않으면 튜링 기계는 정지하고 거절하거나 영원히 멈추지 않을 수 있다.
이는 튜링 기계가 모든 경우에 정지해야 하는 재귀 언어와는 대조된다.
만약 언어가 무한하다면, 반복을 피하도록 하는 알고리듬을 선택할 수 있다. 숫자 ''n''으로 산출된 문자열이 이미 더 작은 숫자 ''n''에서 산출됐는지 확인할 수 있기 때문이다. 만약 이미 산출된 결과라면, 출력을 입력 ''n+1''으로 대신 (귀납적으로) 사용하지만, 반복해서 새로운지 확인이 필요하다.
2. 3. 수락/거부 관점
재귀 열거 언어는 어떤 언어의 문자열이 입력으로 주어질 때 정지하고 수락하지만, 언어에 속하지 않는 문자열이 주어질 때는 정지하고 거부하거나 영원히 반복할 수 있는 튜링 기계 (또는 다른 계산 가능 함수)가 존재하는 형식 언어이다. 이는 튜링 기계가 모든 경우에 정지해야 하는 재귀 언어와 대조된다.2. 4. 언어 종류 포함 관계
모든 정규 언어, 문맥 자유 언어, 문맥 의존 언어, 재귀 언어는 재귀 열거 언어이다.RE와 그 여집합 co-RE는 산술적 계층의 기반이 된다.
2. 5. 복잡도 종류
재귀 열거 언어 집합은 복잡도 종류 '''RE'''로 나타낸다. '''RE'''와 그 여집합인 co-'''RE'''는 산술적 계층의 기반이 된다.3. 예시
정지하는 튜링 기계의 집합은 재귀적으로 열거 가능하지만 재귀적이지는 않다. 실제로 튜링 기계를 실행하고 기계가 정지하면 수용할 수 있으므로 재귀적으로 열거 가능하다. 반면에 이 문제는 풀 수 없다.
재귀적이지 않은 다른 재귀적으로 열거 가능한 언어는 다음과 같다.
- 포스트 대응 문제
- 사망 문제 (계산 가능성 이론)
- 결정 문제
4. 닫힘 성질
재귀 열거 언어는 특정 연산에 대해 닫혀 있는 성질을 가지고 있다. ''L''과 ''P''가 재귀 열거 언어일 때, 이들의 클레이니 스타, 연결, 합집합, 교집합 연산 결과 역시 재귀 열거 언어이다. 하지만, 재귀 열거 언어는 차집합이나 여집합에 대해서는 닫혀 있지 않다.
4. 1. 닫힘 연산
만약 ''L'' 과 ''P'' 가 재귀 열거 언어라면 다음의 언어는 재귀 열거 언어이다.재귀 열거 언어는 차집합이나 여집합에서는 닫혀있지 않다. 차집합 ''L''\''P''는 재귀 열거 언어일 수도 아닐 수도 있다. 만약 ''L''이 재귀 열거 언어라면, ''L''의 여집합은 ''L''이 또한 귀납적인 경우에만 재귀 열거 언어이다.
4. 2. 비닫힘 연산
재귀 열거 언어는 차집합이나 여집합에 대해 닫혀 있지 않다. 차집합 ''L''\''P''는 재귀 열거 언어일 수도 있고 아닐 수도 있다. 만약 ''L''이 재귀 열거 언어라면, ''L''의 여집합은 ''L''이 재귀적일 경우에만 재귀 열거 가능하다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com