비결정적 튜링 기계 (nTM)
- 각 상태와 테이프 기호의 조합에 대해 하나 이상의 가능성이 존재할 수 있습니다.
- 이 변형 V는 각 (qi, zr)에 대해 대체 전환의 유한 집합 {(qi, zw1, D1), (qj, zw2, D2), ...}을 할당하는 튜링 프로그램 δ를 가지고 있다. 기계는 이 집합에서 전환을 비결정적으로 (예측할 수 없게) 선택하고 수행한다. 만약 그러한 전환들이 존재한다면 기계는 해결책 (예: 최종 상태 qyes)으로 이어지는 전환 중 하나를 선택한다고 가정된다. 그렇지 않으면 기계는 멈춘다.
비결정적 튜링 기계는 결정적 튜링 기계(dTM)보다 더 강력한가요? 그렇게 "보이지만", ...
- nTM에 의해 수용되는(accepted) 언어 = dTM에 의해 수용되는(accepted) 언어
- (재귀적recursively 열거 가능enumerable 언어 = 튜링 인식recognizable 언어 = 반결정적semi-decidable 언어)
- nTM에 의해 결정되는(decided) 언어 = dTM에 의해 결정되는(decided) 언어
- (재귀recursive 언어 = 결정적decidable 언어)
그러나! 능력(capability) 대 효율성(efficiency)?
- 비결정적 튜링 기계 (nTM): nTM은 주어진 상태와 테이프 기호에 대해 여러 가지 다른 가능한 행동을 할 수 있는 튜링 기계입니다. 예를 들어, 같은 상태와 테이프 기호에서 nTM은 테이프의 오른쪽 또는 왼쪽으로 이동할 수 있습니다.
- 능력 vs 효율성: 비결정적 튜링 기계와 결정적 튜링 기계는 모두 같은 언어를 수용하거나 결정할 수 있습니다. 이는 그들의 "능력" 측면에서 동등하다는 것을 의미합니다. 그러나 "효율성"의 관점에서 보면, 비결정적 튜링 기계는 문제의 해결을 더 빠르게 찾을 수 있는 가능성이 있습니다. 비결정적 모델은 특정 문제에 대한 해결책의 여러 경로를 동시에 탐색할 수 있으므로, 때로는 결정적 모델보다 더 빠른 결과를 얻을 수 있습니다.
- 언어의 동등성: nTM과 dTM은 같은 언어를 수용하고 결정합니다. 이것은 비결정적이든 결정적이든 튜링 기계가 컴퓨터 과학에서 계산할 수 있는 것의 한계를 나타냅니다.
- 비결정적 튜링 기계 (nTM): nTM은 주어진 상태와 테이프 기호에 대해 여러 가지 다른 가능한 행동을 할 수 있는 튜링 기계입니다. 이는 기계가 여러 가지 가능한 방향 중 하나를 무작위로 선택하여 수행한다는 것을 의미합니다.
- 능력 vs 효율성: 비결정적 튜링 기계와 결정적 튜링 기계는 언어를 수용하고 결정하는 능력 면에서 동일합니다. 즉, 그들은 같은 범주의 언어를 인식하고 결정할 수 있습니다. 그러나 효율성의 관점에서 nTM은 때로는 더 빠른 답변을 찾을 수 있을 것입니다. 비결정적 모델은 특정 문제의 해결책의 여러 경로를 동시에 탐색할 수 있기 때문입니다.
튜링 기계의 실행 시간 (결정적 튜링 기계(dTM)나 비결정적 튜링 기계(nTM) 모두) - decider 만을 위한 것.
N이 결정자decider인 비결정적 튜링 기계라고 하자. N의 실행 시간은 함수 이며, 여기서 은 길이가 n인 모든 입력에 대해 N이 계산의 어느 분기에서든 사용하는 최대 스텝 수입니다. 다음 그림에서 보여진다.
왼쪽은 결정적 튜링 기계를 나타내며, 그 실행 시간을 으로 나타낸다. 이 기계는 결정적으로 '수락/거부'의 결정을 한다. 오른쪽은 비결정적 튜링 기계를 나타내며, 그 실행 시간 또한 으로 나타낸다. 이 기계는 여러 가능한 경로 중 하나로 '수락' 또는 '거부'를 선택할 수 있다.
"계산 이론 소개"에서, M. Sipser 저.
이 문장은 튜링 기계의 실행 시간에 관한 주제를 다루며, 이는 어떤 튜링 기계가 주어진 입력을 처리하고 결과를 반환하는 데 얼마나 오래 걸리는지에 대한 것입니다. 여기서 언급된 "판별자"는 항상 '예' 또는 '아니오'와 같은 명확한 결론을 내리는 튜링 기계를 의미합니다. 결정적 튜링 기계와 비결정적 튜링 기계 모두 이러한 판별자로 동작할 수 있습니다.
이 내용은 튜링 기계의 실행 시간을 설명하는 것입니다.
- 결정적 튜링 기계(dTM): 이는 모든 입력에 대해 한 가지 결과만을 내놓는 기계입니다. 그림에서 보여지는 것처럼 한 줄로 표시되며, 입력이 주어지면 한 가지 경로만을 따라 결과를 내놓습니다.
- 비결정적 튜링 기계(nTM): 이는 주어진 입력에 대해 여러 가능한 경로가 있을 수 있습니다. 그러나 이 기계의 실행 시간은 모든 가능한 경로 중 가장 오래 걸리는 경로(즉, 가장 많은 단계를 거치는 경로)에 기반한다는 것입니다.
따라서, 비결정적 튜링 기계의 실행 시간은 그 기계가 특정 입력에 대해 수행할 수 있는 모든 계산 경로 중에서 가장 많은 단계를 거치는 경로의 단계 수를 기반으로 합니다.
함수 가 주어졌다고 하자. 시간 복잡도 클래스 TIME(t)은 시간 튜링 머신으로 결정될 수 있는 모든 언어의 집합을 정의한다.
P는 다항 시간 내에 결정적 단일 테이프 튜링 머신에서 결정될 수 있는 언어의 클래스다. 다시 말해서, .
PATH = { (G, s, t) | G는 s에서 t까지의 방향 경로가 있는 방향 그래프다. }
PATH는 노드 s에서 노드 t로의 경로가 있는 모든 방향 그래프의 집합입니다.
다시 말해, PATH는 모든 'yes' 인스턴스의 집합입니다.
모든 '예' 인스턴스가 문자열로 표현(= 인코드)된다고 가정합니다.
- 첫 번째 내용은 시간 복잡도에 대한 정의를 제공합니다. 주어진 함수 에 대해, 시간 복잡도 클래스 TIME()은 시간 내에 튜링 머신으로 결정될 수 있는 모든 언어를 포함합니다.
- 두 번째 내용은 P 클래스에 대한 설명입니다. P는 다항 시간 안에 결정적 튜링 머신으로 결정될 수 있는 모든 언어를 포함하는 클래스를 나타냅니다. P는 모든 에 대해 의 유니온으로 정의됩니다. 이는 P가 모든 다항 시간 복잡도를 갖는 언어를 포함한다는 것을 의미합니다.
- 세 번째 내용은 PATH 문제에 대한 정의입니다. 이 문제는 주어진 그래프 에서 두 노드 와 사이에 방향 경로가 존재하는지 여부를 결정하는 문제입니다.
여기서 말하는 PATH는 방향 그래프 내에서 특정 시작 노드 s에서 특정 종료 노드 t로 가는 경로가 있는 그래프의 집합을 나타냅니다.
'yes' 인스턴스란, s에서 t로 가는 경로가 실제로 존재하는 그래프 인스턴스를 말합니다. 이런 인스턴스는 어떤 문제의 특정 해결책을 나타낼 수 있으며, 여기서는 s에서 t로의 경로가 있는 그래프를 의미합니다.
마지막으로, 이런 그래프 인스턴스들은 문자열로 인코드될 수 있다고 설명되어 있습니다. 이는 컴퓨터에서 그래프를 저장하거나 처리하기 위한 표현 방식을 의미합니다. 문자열로 인코딩하는 방식은 그래프의 노드, 간선, 방향 등의 정보를 문자나 숫자의 시퀀스로 변환하는 것을 포함할 수 있습니다.