비결정론적 튜링 기계
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
비결정론적 튜링 기계(NTM)는 1959년 처음 소개되었으며, 계산 복잡도 이론에서 중요한 역할을 하는 추상적인 계산 모델이다. 튜링 기계의 확장으로, 주어진 상태에서 여러 개의 가능한 다음 동작을 가질 수 있다는 특징을 가진다. NTM은 결정론적 튜링 기계(DTM)와 계산 능력 면에서 동등하지만, 시간 복잡도 측면에서는 차이를 보일 수 있다. NTM은 계산 트리를 통해 작동하며, 입력 문자열을 허용하는지 여부를 결정한다. NTM은 P-NP 문제와 밀접한 관련이 있으며, 양자 컴퓨터와 비교되기도 한다. NTM은 이론적인 모델이지만, NP-완전 문제와 같은 문제의 난이도를 분류하는 데 기여한다.
더 읽어볼만한 페이지
- 튜링 기계 - 튜링 완전
튜링 완전은 계산 이론에서 시스템이 튜링 기계와 동등한 계산 능력을 갖춰 튜링 기계가 계산할 수 있는 모든 함수를 계산하고 범용 튜링 기계를 시뮬레이션할 수 있음을 의미하며, 튜링 동등이라고도 한다. - 튜링 기계 - 양자 튜링 기계
양자 튜링 기계는 폴 베니오프가 처음 제안하고 데이비드 도이치 등이 발전시킨, 고전적인 튜링 기계를 양자 역학적으로 일반화한 계산 모델로서, 힐베르트 공간과 유니타리 행렬을 사용하여 양자 컴퓨팅의 기본 원리를 구현하며, 양자 컴퓨터의 이론적 토대를 제공한다. - 계산 모형 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다. - 계산 모형 - 양자 회로
양자 회로는 양자 컴퓨팅에서 양자 논리 게이트들을 연결한 회로로, 큐비트의 양자역학적 특성을 활용하여 계산을 수행하며 양자 계산의 핵심 요소로서 연구가 활발히 진행되고 있다.
비결정론적 튜링 기계 | |
---|---|
기본 정보 | |
유형 | 추상 기계 |
결정성 | 비결정적 |
읽기/쓰기 헤드 | 1 |
테이프 | 1 |
기계 상태 | 유한 |
테이프 기호 | 유한 |
관련 주제 | |
관련 항목 | 결정적 튜링 기계 |
관련 항목 | 오토마타 이론 |
관련 항목 | 계산 복잡도 이론 |
다른 이름 | |
일본어 | 非決定性チューリングマシン (Hiketteisei Chūringu Mashin) |
한국어 | 비결정론적 튜링 기계 |
2. 역사적 배경
튜링 기계는 1936년 앨런 튜링에 의해 처음 소개되었으며, 계산 가능성의 한계를 정의하는 데 중요한 역할을 했다. 비결정론적 튜링 기계의 개념은 1959년 마이클 래빈과 다나 스콧의 논문에서 처음 등장했다. 비결정론적 튜링 기계는 계산 복잡도 이론의 발전에 큰 영향을 미쳤으며, 특히 NP-완전 문제의 정의에 중요한 역할을 했다.
비결정론적 튜링 기계(NTM)는 6-튜플 로 형식적으로 정의할 수 있다. 여기서 각 기호는 다음을 의미한다.
전산학에서 일반적인 (결정론적) 튜링 기계(DTM)는 현재 상태에서 다음 상태로 바뀔 때 다음 상태가 유일하게 결정되는 반면, 비결정론적 튜링 기계(NTM)는 다음 명령이 하나 이상이거나 아예 없을 수도 있다.[1]
3. 정의
결정론적 튜링 기계(DTM)와 NTM의 주요 차이점은 DTM의 전이 관계는 함수인 반면, NTM의 전이 관계는 함수가 아니라는 점이다. 즉, NTM은 현재 상태와 테이프 심볼의 조합에 대해 여러 개의 다음 동작이 허용될 수 있다.
3. 1. 작동 방식
전산학에서, 일반적인 (결정론적) 튜링 기계(DTM)와 달리, 비결정론적 튜링 기계(NTM)는 주어진 상황에 대해 규칙 집합이 둘 이상의 행동을 규정할 수 있다. 예를 들어, 테이프의 X가 상태 3에 있을 때, NTM은 다음 중 하나를 선택할 수 있다.
'''또는'''
NTM이 어떤 동작을 수행해야 하는지 "아는" 방법에 대해서는 두 가지 관점이 있다.
1. 기계가 "가장 운이 좋은 추측자"라고 보는 것이다. 즉, 수락 상태로 이어지는 전이가 있다면 항상 그 전이를 선택한다.
2. 기계가 가능한 각 전이를 따르는 여러 복사본으로 "분기"한다고 보는 것이다. DTM은 단일 계산 경로를 따르는 반면, NTM은 계산 트리를 갖는다. 트리의 한 분기라도 "수락" 조건으로 중단되면 NTM은 입력을 수락한다.
4. 결정론적 튜링 기계(DTM)와의 관계
전산학에서 일반적인 (결정론적) 튜링 기계(DTM)는 현재 상태에서 다음 상태로 전이할 때 다음 상태가 유일하게 결정된다. 더 정확하게 말하면, 현재 헤드가 위치한 테이프의 기호가 s이고 현재 상태가 q라면, 다음 명령 (s', q', d)가 유일하게 결정된다. 이때 s'는 헤드가 테이프에 쓰는 기호, q'는 컴퓨터의 다음 상태, d는 테이프를 왼쪽이나 오른쪽으로 움직일 방향을 지정한다.
이에 반해 비결정론적 튜링 기계(NTM)는 다음 명령이 하나 이상이거나 아예 없을 수도 있다. 각 계산 단계마다 컴퓨터가 '가지치기'를 해서 각각 병렬적으로 계산을 한다고 생각하면 이해하기 쉽다. 결정론적 튜링 기계는 유일한 계산 경로를 따르지만, 비결정론적 튜링 기계는 계산 경로가 트리 형태가 된다. 트리의 여러 가지 중 한 곳에서 "accept" 상태가 되어 계산이 끝나면, 비결정론적 튜링 기계가 입력을 받아들인다(accept)고 한다.
DTM은 주어진 상황에 대해 최대 하나의 동작을 수행하도록 규칙이 정해져 있다. DTM은 주어진 상태와 테이프 헤드 아래의 기호에 대해 다음 세 가지를 지정하는 ''전이 함수''를 갖는다.
- 테이프에 기록할 기호 (현재 위치의 기호와 같거나, 기록하지 않아 변경이 없을 수도 있음)
- 헤드가 이동할 방향 (왼쪽, 오른쪽, 또는 없음)
- 유한 제어의 후속 상태
예를 들어, 상태 3의 테이프에 X가 있으면, DTM은 테이프에 Y를 쓰고, 헤드를 한 칸 오른쪽으로 이동시키고, 상태 5로 전환하도록 할 수 있다.
NTM은 상태와 테이프의 기호에 의해 수행해야 할 작업이 고유하게 지정되지 않는다는 점이 다르다. 같은 상태와 기호 조합이라도 다양한 동작을 할 수 있다. 예를 들어, 테이프에 X가 있고 상태 번호 3일 때, NTM은 Y를 기록하고 오른쪽으로 이동하여 상태 5가 될 수도 있고, X를 기록하고 왼쪽으로 이동하여 상태 3을 유지할 수도 있다.
NTM이 어떤 동작을 해야 하는지 "아는" 방법에 대한 두 가지 관점이 있다. 첫째는 NTM을 "가장 운 좋은 추측기"로 보는 것이다. 즉, NTM은 항상 수락 상태에 도달할 수 있는 상태를 선택한다. 둘째는 NTM이 여러 복제로 분기하여 각각 가능한 전이 중 하나를 실행한다고 보는 것이다. DTM은 계산 경로가 하나뿐이지만 NTM은 계산 트리 구조를 가진다. 이 트리의 한 가지에서 수락 상태로 정지하면 NTM 전체가 입력을 수락했다고 할 수 있다.
4. 1. DTM과의 동치성
결정적 튜링 기계(DTM)으로 풀 수 있는 모든 계산 문제는 비결정론적 튜링 기계(NTM)으로도 풀 수 있으며 그 반대도 성립한다. 그러나 일반적으로 시간 복잡도는 같지 않을 수 있다고 여겨진다.NTM은 DTM을 특별한 경우로 포함하므로, DTM으로 수행할 수 있는 모든 계산은 동일한 NTM으로도 수행할 수 있다. NTM이 인식 가능한 언어는 모두 DTM에서도 인식 가능하다. DTM은 NTM의 전이 분기마다 복제를 생성하여 멀티태스킹과 같은 방식으로 병렬로 시뮬레이션할 수 있다.
이러한 시뮬레이션은 NTM에 비해 매우 많은 시간이 소요되는 것은 분명하다. 일반적으로 얼마나 오래 걸리는지는 불분명하며, 이는 P≠NP 문제와 근본적으로 같다.
4. 2. DTM에 의한 NTM 시뮬레이션
결정론적 튜링 기계(DTM)는 비결정론적 튜링 기계(NTM)의 여러 계산 경로를 시뮬레이션할 수 있다. 한 가지 방법은 NTM의 여러 구성 상태를 나타내는 DTM을 사용하는 것이다. DTM은 각 구성 상태를 차례로 방문하여 한 단계를 실행하고, 전이 관계가 여러 개의 연속 상태를 정의할 때마다 새로운 구성 상태를 생성한다.[3]다른 구성 방식은 3개의 테이프를 가진 DTM으로 NTM을 시뮬레이션하는 것이다. 첫 번째 테이프는 항상 원래의 입력 문자열을 유지하고, 두 번째 테이프는 NTM의 특정 계산을 시뮬레이션하는 데 사용되며, 세 번째 테이프는 NTM의 계산 트리에 있는 경로를 인코딩한다.[3] 이러한 3-테이프 DTM은 일반적인 단일 테이프 DTM으로 쉽게 시뮬레이션할 수 있다.
NTM이 인식 가능한 언어는 모두 DTM에서도 인식 가능하다. DTM은 NTM의 전이 분기마다 복제를 생성하여 멀티태스킹과 같은 방식으로 병렬로 시뮬레이션할 수 있다. 이러한 시뮬레이션에는 NTM에 비해 매우 많은 시간이 소요될 수 있으며, 일반적으로 얼마나 오래 걸리는지는 불분명하며, 이는 P≠NP 문제와 근본적으로 같다.
4. 3. 시간 복잡도
전산학에서 결정론적 튜링 기계(DTM)는 현재 상태에서 다음 상태가 유일하게 결정되지만, 비결정론적 튜링 기계(NTM)는 그렇지 않다. NTM은 각 계산 단계마다 여러 계산 경로를 '가지치기'하여 병렬적으로 계산을 수행하는 것으로 생각할 수 있다. DTM은 NTM의 계산 트리를 너비 우선 탐색 방식으로 시뮬레이션할 수 있는데, 이때 DTM의 계산 시간은 일반적으로 NTM의 계산 시간에 비해 지수적으로 증가한다.NTM이 다항 시간에 해결할 수 있는 문제를 DTM도 다항 시간에 해결할 수 있는지 여부는 컴퓨터 과학의 중요한 미해결 문제인 P = NP 문제의 핵심 질문 중 하나이다. NTM은 가능한 계산을 동시에 병렬로 수행할 수 있어 DTM보다 강력해 보이지만, NTM이 인식 가능한 언어는 모두 DTM으로도 인식 가능하다. DTM은 NTM의 각 분기마다 복제를 생성하여 멀티태스킹처럼 병렬로 시뮬레이션할 수 있기 때문이다.
이러한 시뮬레이션에서 NTM에 비해 DTM이 얼마나 많은 시간을 소요하는지는 P≠NP 문제와 근본적으로 관련되어 있으며, 아직 명확하게 밝혀지지 않았다.
5. P-NP 문제
P 대 NP 문제는 전산학에서 중요한 미해결 문제 중 하나로, 결정적 튜링 기계(DTM)로 다항 시간에 풀 수 있는 문제(P)와 비결정론적 튜링 기계(NTM)로 다항 시간에 풀 수 있는 문제(NP)가 같은지 묻는 문제이다. NTM은 가능한 계산을 동시에 병렬로 수행할 수 있고, 그 중 하나만 성공하면 되므로 DTM보다 강력하다고 생각할 수 있다. 그러나 NTM이 인식 가능한 언어는 모두 DTM에서도 인식 가능하다. DTM은 NTM의 전이 분기마다 복제를 생성하여 멀티태스킹과 같은 방식으로 병렬로 시뮬레이션할 수 있다.
DTM은 NTM의 계산 트리를 효과적으로 너비 우선 탐색하여 허용하는 계산을 찾을 때까지 NTM의 모든 가능한 계산을 길이 순서대로 방문한다. 따라서 DTM의 허용하는 계산의 길이는 일반적으로 NTM의 가장 짧은 허용하는 계산의 길이에 대해 지수적으로 증가한다.
이러한 시뮬레이션이 NTM에 비해 매우 많은 시간이 소요되는 것은 분명하며, 일반적으로 얼마나 오래 걸리는지는 불분명하다. 이는 P≠NP 문제와 근본적으로 같다.
6. 제한된 비결정성
NTM은 제한된 비결정성을 가진다. 즉, NTM이 주어진 입력 테이프 ''T''에서 항상 정지한다면, 유한한 단계 수 내에 정지하며 가능한 구성의 수는 유한하다.
7. 양자 컴퓨터와의 비교
양자 컴퓨터는 기존의 비트가 아닌, 상태의 양자 중첩 상태가 될 수 있는 큐비트를 사용하기 때문에, 양자 컴퓨터가 NTM이라는 오해가 있다.[4] 그러나 전문가들은 (증명되지는 않았지만) 양자 컴퓨터의 성능이 NTM의 성능과 비교할 수 없다고 생각한다. 즉, NTM이 효율적으로 풀 수 있지만 양자 컴퓨터는 풀 수 없는 문제가 존재할 수 있으며, 그 반대의 경우도 마찬가지이다.[5] 특히, NP-완전 문제는 NTM으로는 풀 수 있지만 양자 컴퓨터로는 다항 시간 내에 풀 수 없을 가능성이 높다.
직관적으로 말해서, 양자 컴퓨터는 NTM과 유사하게 실제로 동시에 실행된 모든 가능한 계산 분기에 해당하는 중첩 상태가 될 수 있다. 하지만 최종 측정은 양자 컴퓨터를 무작위로 선택된 분기로 붕괴시킨다. NTM과 달리, 이 분기는 지수적으로 많은 분기 중에서 올바른 솔루션을 선택할 수 있는, 원하는 솔루션을 나타내지 않는 것이 일반적이다.
8. 활용 및 응용
비결정론적 튜링 기계는 계산 복잡도 이론의 핵심 개념으로, 다양한 문제의 난이도를 분류하는 데 사용된다. NP-완전, NP-난해 등의 개념은 비결정론적 튜링 기계를 기반으로 정의된다. 실제 응용보다는 이론적인 중요성이 더 크지만, 알고리즘 설계 및 분석에 간접적인 영향을 미친다.
참조
[1]
서적
Computers and Intractability: A Guide to the Theory of NP-Completeness
https://archive.org/[...]
W. H. Freeman
[2]
웹사이트
Nondeterministic Turing Machines
http://jeffe.cs.illi[...]
U. Illinois Urbana-Champaign
2019-04-07
[3]
서적
Elements of the Theory of Computation
https://archive.org/[...]
Prentice-Hall
[4]
블로그
The Orion Quantum Computer Anti-Hype FAQ
http://www.scottaaro[...]
Scott Aaronson
[5]
논문
Quantum complexity classes
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com