튜링 기계 등가물

튜링 머신
기계
튜링 기계 등가물 튜링 머신의 예 튜링 머신 갤러리
변형
교류 튜링 기계 신경 튜링 기계 비결정적 튜링 기계 양자 튜링 기계 포스트 튜링 머신 확률적 튜링 기계 읽기 전용 튜링 기계 읽기 전용 우측 이동 튜링 머신 멀티테이프 튜링 기계 멀티 트랙 튜링 기계 대칭 튜링 기계 토탈 튜링 머신 언앰비지터 튜링머신 유니버설 튜링 기계 제노머신
과학
앨런 튜링 범주:튜링머신
v t

튜링 기계는 앨런 튜링에 의해 1936년에 처음 고안된 가상의 컴퓨터 장치다.튜링 기계는 유한한 규칙표에 따라 잠재적으로 무한할 수 있는 테이프 줄의 기호를 조작하며, 컴퓨터 알고리즘의 개념에 대한 이론적 기초를 제공한다.

다음의 모델들 중 단방향 무제한의 다심볼 튜링머신 모델보다 더 강력한 힘을 가진 모델은 없는 것으로 나타났지만, 그들의 저자들은 튜링의 a-머신 모델과 함께 머물렀더라면 가질 수 있었던 것보다 더 쉽게 문제를 조사하고 문제를 해결하는 데 그들을 정의하고 사용했다.

튜링 기계 모델과 동등한 기계

튜링 당량

단순한 범용 튜링 기계보다 더 많은 연산 능력을 가지고 있다고 생각될 수 있는 많은 기계들은 더 이상의 파워를 가지고 있지 않다는 것을 보여줄 수 있다.^[1]그들은 아마도 더 빨리 계산하거나, 더 적은 메모리를 사용할 수도 있고, 그들의 명령 집합이 더 작을 수도 있지만, 더 강력한 계산은 할 수 없다.(Church-Turing 논문은 이것이 사실이라는 가설을 세우고 있다: "계산"될 수 있는 것은 어떤 Turing 기계에 의해서도 계산될 수 있다는 것이다.)

순차 기계 모델

다음의 모든 것을 "병렬 기계 모델"과 구별하기 위해 "순차 기계 모델"이라고 한다.^[2]

테이프 기반 튜링 머신

튜링의 기계 모델

튜링의 a-machine(그의 이름대로)은 좌익, 우익-무한(wright-end-infinite)이었다.그는 왼쪽 끝을 표시하기 위해 기호 əə를 제공했다.한정된 수의 테이프 기호가 허용되었다.지시사항(범용 기계인 경우), "입력"과 "출력"은 "F-제곱"에만 쓰여 있었고, "E-제곱"에는 마커가 나타나도록 되어 있었다.본질적으로 그는 자신의 기계를 항상 함께 움직이는 두 개의 테이프로 나누었다.지시사항은 "5-tuple"이라는 표 형식으로 나타나 순차적으로 실행되지 않았다.

제한된 기호 및/또는 지침이 있는 단일 테이프 기계

다음 모델은 단일 테이프 튜링 기계지만 (i) 제한 테이프 기호 { 마크, 공백 } 및/또는 (ii) 순차적, 컴퓨터 유사 지침 및/또는 (iii) 기계 동작 완전 분무화.

포스트의 "형식 1" 계산 모델

에밀 포스트는 계산 프로세스에 대한 독립적 설명에서, 테이프 { "마크", "blank"=not_mark }의 등가 이진 마크 집합에 허용되는 기호를 줄였다.그는 '테이프'라는 개념을 1방향 무제한에서 우측으로 각각 양방향에 종이가 한 장씩 있는 무한 셋트로 바꾸었다.그는 튜링 5개 튜플을 인쇄/삭제 지침과는 별개로 4개 튜플로 분무했다.그의 1936년 모델은 이것에 대해 모호하지만, Post의 1947년 모델은 순차적인 명령 실행을 요구하지 않았다.

그의 극히 단순한 모델은 어떤 튜링 기계도 모방할 수 있으며, 1936년 그의 공식 1은 "프로그램"이나 "기계"라는 단어를 사용하지 않지만, 박스가 무한 비트스트링 메모리의 역할을 하고, 명령어 집합이 a를 구성하는 매우 원시적인 프로그램 가능 컴퓨터와 관련 프로그래밍 언어의 구성이다.프로그램을 짜다

왕머신

하오왕은 영향력 있는 논문에서 포스트의 "형식 1"을 여전히 양방향 무한 이진 테이프를 사용하지만, 지침이 더 간단한 기계(Post의 지시사항의 "원자" 구성요소)로 축소했으며, 기본적으로 순차적으로 ("컴퓨터 프로그램"처럼) 실행된다.그의 명시적인 주된 목적은 튜링의 이론의 대안으로 "기본 운영에 있어 더 경제적"이라는 것을 제공하는 것이었다.그의 결과는 명령어 세트가 있는 5계통 왕W 기계를 포함한 다양한 기계의 "프로그램 공식화"였다.

{shift-왼쪽, Shift-오른쪽, MARK-Square, ERASR-Square, JUMP-IF-Square-MARK-to xxx}}

그리고 그가 가장 많이 줄인 왕비머신("기본"을 위한 B")은 명령 집합과 함께.

{shift-왼쪽, Shift-오른쪽, MARK-Square, JUMP-IF-Square-MARK-to xxx }

ERASR-SQUARE 명령도 없어

후에 많은 저자들은 왕 교수가 논의한 기계의 변형들을 소개했다.

민스키는 별도 헤드의 SHIFT-LEFT와 SHIFT-RHIFT-RIGHT 모션을 허용하면서도 인쇄는 전혀 하지 않는 (멀티테이프) "카운터 머신" 모델을 자신의 버전으로 왕씨의 생각을 진화시켰다.^[3]이 경우 테이프는 왼쪽 끝이며, 각 끝에는 끝을 나타내는 단일 "표시"가 표시된다.그는 이것을 하나의 테이프로 줄일 수 있었지만, 훨씬 단순한 {SHIFT-LEFT = REVENT, SHIFT-REFT = REVENT = INCRING }보다 곱셈과 나눗셈에 해당하는 멀티테이프-제곱 운동을 도입하는 비용을 지불하고 있었다.

Davis는 왕씨가 논의한 기계 중 하나에 명시적 HALT 지침을 추가한 후 명령 집합이 있는 모델을 사용했다.

{SHIFT-왼쪽, Shift-오른쪽, ERASH, MARK, JUMP-IF-SQUARED-to xxx, JUMP-to xxx, STOP }

또한 크기가 2보다 큰 테이프 알파벳을 사용하는 버전도 고려했다.

밥의 이론 기계어 P"

튜링 등가 이론인 '기본 운영의 경제학'을 모색하고, 무조건 점프를 피하고자 하는 왕 교수의 프로젝트에 발맞춰, 주목할 만한 이론 언어는 1964년 코라도 뵈엠이 소개한 4계언어 P(Turing-complete)로, 튜링 완성이 입증된 최초의 'GOTO-less' 필수 '구조적 프로그래밍' 언어인 것이다.

멀티테이프 튜링 기계

실제 분석에서는 다양한 종류의 멀티테이프 튜링 기계가 자주 사용된다.멀티테이프 기계는 싱글테이프 기계와 유사하지만, 몇 가지 k개의 독립 테이프가 일정하게 존재한다.

결정론적 및 비결정적 튜링 기계

동작 테이블이 기호와 상태의 각 조합에 대해 최대 하나의 항목을 가지고 있는 경우 기계는 "결정적 튜링 머신"(DTM)이다. 만일 동작 테이블에 기호와 상태의 조합에 대한 여러 항목이 포함되어 있다면, 기계는 "비결정적 튜링 머신"(NDTM)이다.이 두 가지는 계산적으로 동등하다. 즉, 대개 런타임이 다르지만 NDTM을 DTM(그리고 그 반대의 경우도 가능)으로 바꾸는 것이 가능하다.이것은 공사로 증명할 수 있다.

망각 튜링 기계

망각 튜링 기계는 각 입력 길이에 대해 다양한 헤드의 움직임이 입력과 무관하게 시간의 고정된 함수인 튜링 기계다.즉, 미리 정해진 순서에 따라 다양한 테이프가 스캔되고, 진일보되고, 쓰여지는 순서가 있다.어떤 단계에서든 테이프에 쓰여지는 실제 값은 여전히 그 길이의 입력마다 다를 수 있다.Pippenger와 Fischer는 n단계에서 다중 테이프 튜링 기계에 의해 수행될 수 있는 모든 연산은 $O{\displaystyle }$ (${\displaystyle n}$ ${\displaystyle \log }$ ${\displaystyle n}$){\$displaystyle O(n\log n)}$단계에서$$ 망각된 2-테이프 튜링 기계에 의해 수행될 수 있다는 것을 보여주었다$.$^[4]

기계 모델 등록

피터 판 엠드 보아스는 이러한 유형의 모든 기계를 하나의 클래스인 "등록기"에 포함한다.^[2]그러나 역사적으로 문학은 또한 이 집단의 가장 원시적인 구성원이라고도 불렀다."카운터 머신" – "등록기 기계".그리고 "카운터 머신"의 가장 원초적인 구현을 "민스키 머신"이라고 부르기도 한다.

"등록 기계" 모델이라고도 하는 "카운터 머신"

원시 모델 레지스터 기계는 사실상 동작이 제한된 멀티테이프 2-심볼 포스트-튜링 기계여서 테이프가 단순한 "카운터"처럼 작동한다.

멜작, 람베크, 민스키가 "컴퓨터 프로그램"이라는 개념을 만들 때쯤에는 포스트-튜링 테이프에서 잘라낸 많은 왼쪽 끝 테이프가 있는 다른 형태의 간단한 기계를 생산했다.모든 경우 모델에는 두 개의 테이프 기호 { 마크, 공백 }^[3]만 허용된다.

일부 버전은 양의 정수를 "register"(즉, 왼쪽 끝 테이프)에 허용되는 문자열/더미와 "0"으로 표시된 빈 테이프로만 나타낸다.민스키는 자신의 모델에게 각 테이프의 왼쪽 끝에 의무적인 단일 마크를 제공하는 비용으로 PRINT 지침을 삭제했다.^[3]

이 모델에서 등록한 단일 엔드 테이프는 "상담자"로 생각되며, 그 지침은 2개(또는 TEST/DECTEMENT 지침이 분무화된 경우 3개)로만 제한된다.두 가지 일반적인 명령 집합은 다음과 같다.

(1): { INC ( r "), DEC ( r "), JZ ( r,z ) }, 즉.

{ 레지스터 #r; 레지스터 #r; DECrement 컨텐츠 #r; IF 컨텐츠 #r=Zero의 Zero THE Jump-to 지침 #z}

(2) : { CLR ( r ); INC ( r ); JE ( r, r_i, z_j )}, 즉.

{ register r; increment contents of r; r의 cleaR contents; r의_ij 내용을 비교하고 Equal이면 명령 z로 점프}

그의 모델은 이 간단한 설명보다 더 복잡하지만, 멜작 "페블" 모델은 이 "카운터" 개념을 확장하여 여러 개의 조약돌을 덧셈과 뺄셈을 허용했다.

RAM(Random-Access Machine) 모델

멜작 박사는 자신의 레지스터/카운터 머신 모델에서 몇 가지 심각한 결함을 인지했다.^[5] (i) 간접 어드레싱의 형태가 없으면, 모델이 튜링 등가임을 "쉽게" 보여줄 수 없을 것이다. (ii) 프로그램과 레지스터는 "공간"이 다르기 때문에 자체 수정 프로그램은 쉽지 않을 것이다.멜작의 모델에 간접 주소 지정을 추가했을 때, 그는 랜덤 액세스 머신 모델을 만들었다.

(그러나, 괴델에 번호를 매기면서 민스키는 그러한 번호를 매기면 일반적인 재귀 기능이 실제로 가능하다는 증거를 제시했다; 그는 μ 재귀가 실제로 가능하다는^[3] 증거를 제시한다.)

RASS 모델과 달리 RAM 모델은 기계의 동작이 지시사항을 수정하는 것을 허용하지 않는다.때때로 모델은 축적기 없이 등록만 할 수 있지만, 대부분의 모델은 축적기를 포함하는 것처럼 보인다.

Van Emde Boas는 다양한 RAM 모델을 다음과 같은 여러 하위 유형으로 나눈다.^[2]

• SRAM, 산술 지침이 단 한 개뿐인 "수처 RAM", 후계자(INCREMENT h)이다.다른 것에는 "CLEAR h"와 IF-between-register THING-to xxx가 포함된다.
• RAM: 덧셈과 뺄셈이 있는 표준 모델
• MRAM: 곱셈과 나눗셈으로 증강된 RAM
• BRAM, MBRAM: RAM 및 MRAM의 비트 부울 버전
• N****: 이름 앞에 N이 있는 위의 비결정적 버전

RASP(Random-Access Stored Program) 기계 모델

ROSS는 동일한 '공간', 즉 레지스터 시퀀스에 데이터와 함께 저장된 지침이 포함된 RAM이다.RASS의 개념은 적어도 키퐁스트만큼 일찍 설명되었다.그의 모델은 "mill" 즉 축전지를 가지고 있었지만, 이제 지침서는 데이터와 함께 기록부 안에 있었다. 즉, 폰 노이만 아키텍처라고 불리는 것이다.ROSS에 짝수 및 홀수 레지스터("작업 코드"(인스턴스)와 홀수(인스턴스)가 번갈아 있을 경우, 명령의 피연산자를 간단히 수정함으로써 간접 어드레싱이 달성된다.^[6]

엘곶과 로빈슨의 원래 RASS 모델은 레지스터 머신 모델의 패션에 있어서 세 가지 지침만 가지고 있었지만,^[7] 데이터와 함께 레지스터 공간에 배치했다.(여기서 하나의 레지스터(예: "z" 또는 "0")가 시작되어 항상 0을 포함하는 경우 CLEARE를 대신한다.이런 수법은 예사롭지 않다.레지스터 "단위" 또는 "1"에 있는 단위 1도 유용하다.)

{ INC ( r ), CAPE ( r_j, r_i ), JE ( r_i, r_i, z ) }

ROSS 모델은 직접 덧대기는 물론 간접적인 것도 허용한다. 일부 모델에서는 "즉시" 지침도 허용한다(예: "상수 3으로 축전지 적재").지침서는 하르트마니스의 다음 16가지 지침과 같이 매우 제한적인 집합일 수 있다.^[8]이 모델은 축열조 A를 사용한다.연상학은 저자가 사용한 것이다(그들의 CLA는 상수 또는 등록부가 있는 "부하 축적기"이고, STO는 "저장소 축전기"이다)."즉시", "직접", "간접"의 경우 점프를 제외하고, 이들의 구문은 다음과 같다.점프는 두 개의 "전송 지침" TRA를 통해 이루어진다. 즉, 레지스터 n의 방해 콘텐츠를 직접 "n" 또는 간접적으로 "< n >" 점프를 통해 명령 카운터인 TRZ(Autumulator가 TRA와 동일한 방식으로 0인 경우 조건부 점프):

{ADD n , ADD < n >, ADD << n >, SUB < n >, SUB < N > CLA N, CLA < n >, CLA < n>, STO < n>, TRA N, TRZ N, TRA < N >, STO >}

포인터 머신 모델

상대적 후발주자는 쇤네게의 저장수정기 또는 포인터머신이다.다른 버전은 Kolmogorov-Uspensky 기계와 Knuth "linking automaton" 제안이다. (참고문은 포인터 기계 참조)상태-기계 다이어그램과 마찬가지로, 노드는 다른 노드 또는 노드 등을 가리키는 최소 두 개의 "에지(화살표)"를 방출한다.외부 세계는 중앙 노드를 가리킨다.

입력 및 출력이 있는 시스템

위의 테이프 기반 기계는 입력 및 출력 테이프를 장착할 수 있으며, 위의 레지스터 기반 기계는 전용 입력 및 출력 레지스터를 장착할 수 있다.예를 들어 Shönhage 포인터 머신 모델에는 "입력 put, ,"과₀₁ "출력 β"라는 두 가지 지침이 있다.

기존 모델과 함께 멀티테이프 기계의 비선형 공간 복잡성을 연구하기는 어렵다. 왜냐하면 크기 n의 입력은 이미 공간 n을 차지하기 때문이다.따라서, 작은 DSPACE 수업을 공부하기 위해서, 우리는 다른 모델을 사용해야 한다.어떤 의미에서는 입력 테이프에 절대 "쓰기"를 하지 않는다면, 우리는 이 공간에 대해 우리 자신을 청구하고 싶지 않다.그리고 만약 우리가 우리의 출력 테이프를 절대 "읽지" 않는다면, 우리는 이 공간에 대해 우리 스스로 비용을 청구하고 싶지 않다.

우리는 입출력이 있는 k-string Turing 기계를 도입함으로써 이 문제를 해결한다.이는 일반적인 k-string Turing 기계와 동일하지만, 입력 테이프는 절대 변경될 수 없고, 출력 헤드는 절대 좌회전할 수 없도록 전환 함수 Δ가 제한되어 있다는 점을 제외하면 말이다.이 모델을 통해 선형보다 작은 결정론적 공간 클래스를 정의할 수 있다.입출력 튜링 기계도 다른 튜링 기계와 동일한 시간 복잡성을 가지고 있다; Papadimitriou 1994 Prop 2.2:

시간 $바운드{\displaystyle }$f (${\displaystyle n}$ ${\displaystyle )}${\$displaystyle$f($n)}$ 내에서 작동하는 모든 k-string 시스템 M의 경우 입력과 출력이 있는${\displaystyle }$(${\displaystyle k}$ ${\displaystyle +2}$ )$${\$displaystyle (k+$2) -string$$ 시스템 M'이 있으며, 시간 $바운드{\displaystyle }$O ( ${\displaystyle f}$)${\displaystysty O(f)(n)}$에서 작동한다$.$

입력과 출력이 있는 k-string Turing 기계는 복잡성 자원 DSPAC의 공식 정의에 사용될 수 있다.^[9]

기타 동등한 기계 및 방법

• 다차원 튜링 기계:예를 들어 쇤게이지의 모델은 4개의 헤드 무브 명령 {북,남,동,서}을(를)^[10] 사용한다.
• 단일 테이프 다중 헤드 튜링 기계:민스키와 셰퍼드슨, 스터기스는 '태그 문제'에 대한 미해결의 증거에서 한 머리로 테이프를 따라 읽고 다른 머리로 테이프를 따라 더 길게 쓸 수 있는 하나의 테이프로 기계를 묘사했다.^[11][12]

• 마르코프 알고리즘은 튜링 기계와 동등한 문자열 재작성을 기반으로 한 또 다른 놀랍도록 간단한 연산 모델이다.
• 람다 미적분학
• 큐 오토매틱

참조