비결정론적 튜링 기계

튜링 기계
기계.
튜링 기계 등가물 튜링 기계 예시 튜링 기계 갤러리
변종
교대 튜링 기계 신경 튜링 기계 비결정론적 튜링 기계 양자 튜링 기계 포스트튜어링 머신 확률론적 튜링 기계 멀티테이프 튜링 머신 멀티트랙 튜링 머신 대칭 튜링 기계 토탈 튜링 머신 명확한 튜링 기계 범용 튜링 기계 제노 기계
과학
앨런 튜링 카테고리:튜링 기계
v t

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 찾기 : "결정적이지 않은 튜링 머신"– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2019년 1월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

이론 컴퓨터 과학에서, 비결정론적 튜링 기계(NTM)는 주어진 상황에서 하나 이상의 가능한 동작을 규정하는 지배 규칙을 가진 계산의 이론 모델이다.즉, NTM의 다음 상태는 결정론적 튜링 기계와 달리 동작과 현재 기호에 의해 완전히 결정되지 않는다.

NTM은 때때로 컴퓨터의 능력과 한계를 조사하기 위해 사고 실험에서 사용됩니다.이론 컴퓨터 공학에서 가장 중요한 미해결 문제 중 하나는 P 대 NP 문제이며, 이는 (다른 동등한 공식들 중에서도) 결정론적 컴퓨터로 비결정론적 계산을 시뮬레이션하는 것이 얼마나 어려운가에 관한 문제이다.

배경

본질적으로, 튜링 기계는 한 번에 한 개씩 무한 테이프에 심볼을 읽고 쓰는 단순한 컴퓨터라고 상상됩니다.내부 상태와 현재 표시되는 심볼에 따라 다음에 수행할 작업을 결정합니다.튜링 기계의 규칙 중 하나는 다음과 같습니다: "상태 2에 있고 'A'가 보이면, 그것을 'B'로 변경하고, 왼쪽으로 이동하고, 상태 3으로 변경하십시오."

결정론적 튜링 기계

결정론적 튜링 머신(DTM)에서 규칙 세트는 주어진 상황에 대해 수행되어야 할 최대 하나의 동작을 규정한다.

결정론적 튜링 기계는 테이프 헤드 아래의 주어진 상태와 심볼에 대해 세 가지를 지정하는 전이 함수를 가진다.

• 테이프에 기록할 기호(현재 위치에 있는 기호와 동일하거나 전혀 쓰지 않아 실질적인 변화가 없을 수 있음)
• 머리가 움직여야 하는 방향(좌, 우 또는 둘 다)
• 유한 제어의 후속 상태.

예를 들어 상태 3의 테이프에 X가 있으면 DTM이 테이프에 Y를 쓰고 헤드를 오른쪽으로1개 이동한 후 상태 5로 전환할 수 있습니다.

직감

결정론적 튜링 기계와는 대조적으로, 비결정론적 튜링 기계(NTM)에서 규칙 세트는 주어진 상황에 대해 실행되는 하나 이상의 동작을 규정할 수 있다.예를 들어, 스테이트 3의 테이프에 X 가 붙어 있으면, NTM 는 다음의 조작을 실시할 수 있습니다.

• Y를 쓰고 오른쪽으로 이동한 후 상태 5로 전환합니다.

또는

• X를 쓰고 왼쪽으로 이동한 후 상태 3을 유지하십시오.

여러 규칙의 해결

NTM은 다음 중 어떤 조치를 취해야 하는지 어떻게 알 수 있습니까?그것을 바라보는 두 가지 방법이 있다.하나는 기계가 "가장 운이 좋은 추측자"라고 말하는 것입니다. 기계는 항상 최종적으로 수용 상태로 이어지는 전환을 선택합니다. 만약 그러한 전환이 있을 경우.다른 하나는 기계가 여러 개의 복사본으로 "분기"되고 각 복사본은 가능한 전환 중 하나를 따른다고 상상하는 것입니다.DTM에는 1개의 "계산 경로"가 있으며, NTM에는 "계산 트리"가 있습니다.트리의 적어도1개의 브런치가 "accept" 조건으로 정지하면 NTM은 입력을 받아들입니다.

정의.

비결정적 튜링 머신은 공식적으로 6개의 $태플{\displaystyle }$ ${\displaystyle M=}$( Q ,${\displaystyle \mathrm{\sigma }}$ ,${\displaystyle }$, , ${\displaystyle a}$ ,${\displaystyle a}$ ,${\displaystyle ,}$ $){$ $displaystyle$ M = ( $Q$, \ $Sigma$, \ $iota$, \ $cup$, $A$, \ $delta$ $)$로 정의할 수 있습니다.

• $(\displaystyle$ Q$)$는 유한한 상태의 집합입니다.
• $σ$\ $displaystyle$ \$$Sigma$$ }는 한정된 기호 세트(테이프 알파벳)입니다.
• ${\displaystyle \S }$ $(\displaystyle\iota\inQ$$)$는 초기 상태입니다.
• ${\displaystyle }$⊔$σ （$ display$style$ \$sqcup$\ $in$ \ Sigma$$）는$$ 공백 기호입니다${\displaystyle .}$
• $(\displaystyle$ A$\subseteq)$는 수용(최종) 상태의 집합입니다.
• $、$ A$σ$ )${\displaystyle }$× ( ${\displaystyle Q}$ × ${\displaystyle \times }$ × {${\displaystyle }$L ,${\displaystyle S}$ , $}$ ) ($displaystyle$ \ delta \ $subseteq$\ $left$ ( Q \ $backslash A$\ $times$ \$Sigma$ \$right$ ) \ $times$\ $left$ ($Q$\ $times$ \$Sigma$ \ right ) 、 $\ right$ )$(디스플레이 스타일$ L$)$은 왼쪽으로, $(디스플레이 스타일$ S$)$는 움직이지 않고 R$(디스플레이 스타일$ R$)$은 오른쪽으로 이동합니다.

표준과의 차이(결정론적)튜링 기계는 결정론적 튜링 기계에서 전이 관계가 단순한 관계가 아닌 함수라는 것이다.

테이프의 가능한 내용이 주어진 튜링 기계의 가능한 동작을 기술하는 구성과 구성에 대한 수율 관계는 더 이상 수율 관계가 단일 값이 아니라는 점을 제외하고 표준 튜링 기계와 같다.(기계가 결정론적인 경우 가능한 계산은 모두 단일(가능성이 있는 무한) 경로의 접두사입니다.)

NTM 의 입력은, 결정론적 튜링 머신과 같은 방법으로 제공됩니다.테이프 헤드가 문자열의 첫 번째 문자(있는 경우)에 있는 구성으로 기동하고, 그렇지 않은 경우 테이프는 모두 공백입니다.

NTM은 입력 문자열을 받아들이는데, 그 문자열에서 시작하는 가능한 계산 경로 중 적어도1개가 머신을 허용 상태로 했을 경우에만 받아들입니다.결정론적 머신 상에서 NTM의 많은 분기 경로를 시뮬레이션할 때, 어느 분기라도 허용 상태에 도달하는 즉시 전체 시뮬레이션을 중지할 수 있습니다.

대체 정의

주로 증명에 사용되는 수학적 구조로서 NTM의 정의에 대한 다양한 작은 변형이 있지만, 이러한 변이들은 모두 동등한 언어를 받아들인다.

전환 관계 출력의 헤드 이동은 종종 왼쪽(-1), 고정(0) 및 오른쪽(+1)을 나타내는 문자 대신 숫자로 ${\displaystyle 인코딩}$되어${\displaystyle }$(Q ×${\displaystyle \mathrm{\Omega }\times }$ {${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle 0}$ , + 1$})$의 전환 함수 출력을 제공합니다. \ $display style \left (Q\times \Sigma \{$- 0 , 1 . 0 , 1 }일반적으로 고정(0) ^[1]출력을 생략하고 대신 원하는 고정 전환의 전환 닫힘을 삽입합니다.

일부 작성자는 명시적인 거부 ^[2]상태를 추가하여 NTM이 승인하지 않고 중지됩니다.이 정의에서는 비결정적 브랜치가 받아들일 수 있는 비대칭성이 유지되지만 스트링이 거부되기 위해서는 모든 브랜치가 거부해야 합니다.

DTM과의 계산 동등성

DTM으로 해결할 수 있는 계산상의 문제는 NTM으로 해결할 수도 있고, 그 반대도 마찬가지입니다.그러나 일반적으로 시간 복잡도는 같지 않을 수 있습니다.

NTM의 특수한 경우로서의 DTM

NTM은 DTM을 특수한 경우로 포함하기 때문에 DTM에 의해 실행될 수 있는 모든 계산도 동등한 NTM에 의해 실행될 수 있습니다.

NTM의 DTM 시뮬레이션

NTM은 동일한 초기 설정에서 발생할 수 있는 계산을 트리로 할 수 있기 때문에 DTM보다 강력하다고 생각됩니다.트리의 어느 브랜치라도 스트링을 받아들이면 스트링을 받아들일 수 있습니다.단, DTM을 사용하여 NTM을 시뮬레이트할 수 있으며, 실제로는 여러 가지 방법으로 실행할 수 있습니다.

구성 상태의 다양성

하나의 접근방식은 구성이 NTM의 여러 구성을 나타내는 DTM을 사용하는 것입니다.DTM의 동작은 각 구성을 차례로 방문하여 방문 시마다 한 단계를 수행하고 전환 관계가 여러 개의 연속성을 정의할 때마다 새로운 구성을 생성하는 것입니다.

테이프의 다양성

또 다른 구조는 3테이프 DTM을 사용하여 NTM을 시뮬레이트합니다.첫 번째 테이프는 항상 원본 입력 문자열을 보유하고 있으며 두 번째 테이프는 NTM의 특정 계산을 시뮬레이트하는데 사용되며 세 번째 테이프는 NTM의 계산 ^[3]트리에서 경로를 인코딩합니다.3 테이프 DTM 은, 통상의 싱글 테이프 DTM 로 간단하게 시뮬레이트 할 수 있습니다.

시간의 복잡성과 P 대 NP

두 번째 구성에서 구축된 DTM은 NTM의 계산 트리의 너비 우선 검색을 효과적으로 수행하며, 수용 가능한 계산 트리를 찾을 때까지 길이를 늘려 NTM의 모든 가능한 계산을 방문한다.따라서 DTM의 수용연산의 길이는 일반적으로 NTM의 최단 수용연산의 길이에서 지수적이다.이것은 DTM에 의한 NTM 시뮬레이션의 일반적인 속성이라고 생각됩니다.컴퓨터 과학에서 가장 유명한 미해결 문제인 P = NP 문제는 이 문제의 한 가지 경우에 관한 것이다. 다항 시간에 NTM이 풀 수 있는 모든 문제가 다항 시간에 DTM에 의해 풀 수 있는지 여부이다.

유계 비결정론

NTM은 유계 비결정론의 특성을 가지고 있다.즉, NTM이 항상 소정의 입력 테이프 T로 정지하는 경우, 제한적인 수의 스텝으로 정지하기 때문에 가능한 설정 수는 한정됩니다.

양자 컴퓨터와의 비교

왜냐하면 양자 컴퓨터가 superpositions에, 통상적인 비트들보다는 수 있는 양자 비트, 이용, 가끔 거긴 오해는 양자 컴퓨터 NTMs.[4] 하지만 전문가들에 의해( 하지만 아직 증명되지 않)은 양자 컴퓨터의 힘, 사실, NTMs 것에 비할 바 아니게 믿어지고 있다. 그것은, 문제 있다.사행NTM은 양자 컴퓨터가 해결할 수 없는 문제를 효율적으로 해결할 수 있으며 그 ^{[5][better source needed]}반대도 마찬가지입니다.특히, NP-완전 문제는 NTM에 의해 해결되지만 다항식 시간에는 양자 컴퓨터에 의해 해결되지 않을 가능성이 있다.

직관적으로 말하면, 양자컴퓨터는 실제로 동시에 실행된 모든 가능한 계산 브랜치에 대응하는 중첩 상태에 있을 수 있지만(NTM과 유사), 최종 측정은 양자컴퓨터를 랜덤으로 선택된 브랜치로 압축한다.따라서 이 브랜치는 기하급수적으로 많은 브랜치 중에서 적절한 솔루션을 선택할 수 있는 NTM과는 달리 일반적으로 요구되는 솔루션을 나타내지 않습니다.

「 」를 참조해 주세요.

• 확률론적 튜링 기계

레퍼런스

• Martin, John C. (1997). "Section 9.6: Nondeterministic Turing machines". Introduction to Languages and the Theory of Computation (2nd ed.). McGraw-Hill. pp. 277–281. ISBN 978-0073191461.
• Papadimitriou, Christos (1993). "Section 2.7: Nondeterministic machines". Computational Complexity (1st ed.). Addison-Wesley. pp. 45–50. ISBN 978-0201530827.

외부 링크

• 비결정적 멀티테이프 튜링 머신의 C++ 시뮬레이터(자유 소프트웨어).
• 소스 포지에서 비결정적 멀티테이프 튜링 머신의 C++ 시뮬레이터 다운로드 링크.그물