범용 튜링 기계

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

컴퓨터 과학에서, 범용 튜링 기계(UTM)는 임의의 입력에 대해 임의의 튜링 기계를 시뮬레이션할 수 있는 튜링 기계이다.유니버설 머신은 기본적으로 시뮬레이트할 머신의 설명과 그 머신의 입력을 테이프에서 읽어냄으로써 이를 실현합니다.앨런 튜링은 1936-1937년에 그러한 기계의 개념을 도입했다.이 원리는 1946년 존 폰 노이만이 현재 폰 노이만의 ^[1]이름인 "전자계산기"를 위해 사용한 저장된 프로그램 컴퓨터의 발상이라고 여겨진다.

계산 복잡성의 관점에서, 멀티 테이프 범용 튜링 기계는 시뮬레이션하는 ^[2]기계들에 비해 로그 인수에 의해서만 느리면 된다.

서론

모든 튜링 기계는 알파벳 위에 입력 문자열로부터 특정한 고정된 부분 계산 가능 함수를 계산한다.그런 의미에서 그것은 고정된 프로그램을 가진 컴퓨터처럼 동작한다.단, 튜링 머신의 동작 테이블을 문자열로 인코딩할 수 있습니다.따라서 우리는 그 테이프에 동작 테이블을 기술하는 문자열과 입력 테이프를 기술하는 문자열을 예상하고 인코딩된 튜링 기계가 계산했을 테이프를 계산하는 튜링 기계를 구성할 수 있다.튜링은 1936년 논문에서 이러한 구조를 완전히 상세하게 기술했다.

"계산 가능한 시퀀스를 계산하기 위해 사용할 수 있는 단일 기계를 발명할 수 있습니다.이 기계 U의 선두에 일부 컴퓨팅 기계 M의 S.D [액션 테이블의 「표준 기술」이라고 기재되어 있는 테이프가 부속되어 있으면, U는 ^[3]M과 같은 시퀀스를 산출한다.

프로그램 저장 컴퓨터

데이비스는 "저장된 프로그램 컴퓨터"로 알려진 것에 대한 튜링의 개념이 입력 데이터와 동일한 "메모리"에 "동작 테이블"을 배치하는 것이 존 폰 노이만의 최초의 (아날로그와 반대되는) 이산 기호 컴퓨터인 EDVAC에 대한 개념에 강한 영향을 미쳤다고 설득력 있는 주장을 펼친다.데이비스는 타임지의 말을 인용해 "키보드를 두드리는 모든 사람은...'존 폰 노이만이 앨런 튜링의 작품을 바탕으로 했다'는 내용(타임지 1999년 3월 29일자 인용 2000:193).

데이비스는 튜링의 ACE(Automatic Computing Engine) 컴퓨터가 마이크로 프로그래밍(마이크로 코드)과 RISC 프로세서(Davis 2000:188)의 개념을 "예상"했다고 주장합니다.Knuth는 ACE 컴퓨터에 대한 튜링의 작업을 "서브루틴 연결을 용이하게 하기 위한 하드웨어"(Knuth 1973:225)를 설계한 것으로 인용한다. 데이비스는 또한 이 작업을 튜링의 하드웨어 "스택" 사용으로 언급한다(Davis 2000:237 각주 18).

튜링 머신이 컴퓨터의 건설을 장려하고 있었기 때문에 UTM은 신생 컴퓨터 과학의 발전을 장려하고 있었다.최초의 어셈블러는 아니더라도 EDVAC(Davis 2000:192)를 위해 "젊은 핫샷 프로그래머에 의해" 제안되었습니다.Von Neumann의 "첫 번째 진지한 프로그램...[] 데이터를 효율적으로 정렬하는 것이었습니다.(Davis 2000:184)Knuth는 특별한 레지스터가 아닌 프로그램 자체에 포함된 서브루틴 리턴이 von Neumann과 Goldstine에 ^[4]기인한다고 관찰했다.Knuth는 더 나아가 다음과 같이 말한다.

"첫 번째 해석 루틴은 "유니버설 튜링 머신"이라고 할 수 있습니다."존 모클리가 1946년 무어 학교 강연에서 전통적인 의미의 해석적 일상을 언급했다.튜링도 이 개발에 참여했다; 파일럿 ACE 컴퓨터를 위한 해석 시스템은 그의 지시에 따라 작성되었다." (Knuth 1973:226)

데이비스는 데이터로서의 프로그램(Program-as-Data) 개념의 결과로 운영 체제와 컴파일러를 간략히 언급하고 있습니다(Davis 2000:185).

그러나 일부에서는 이 평가에 대해 문제를 제기할 수 있다.당시(1940년대 중반에서 1950년대 중반)에는 비교적 소규모의 연구자들이 새로운 "디지털 컴퓨터"의 아키텍처에 깊이 관여하고 있었습니다.이 시기 젊은 연구자인 Hao Wang(1954)은 다음과 같이 관찰했다.

튜링의 계산 가능 함수에 대한 이론은 앞서 있었지만 디지털 컴퓨터의 광범위한 실제 구성에 큰 영향을 미치지 않았다.이론과 실제의 이 두 가지 측면은 거의 서로 독립적으로 개발되어 왔다.주된 이유는 논리학자들이 응용 수학자나 전기 공학자들이 주로 관심을 갖는 것과 근본적으로 다른 문제에 관심을 가지고 있기 때문이다.그러나 같은 개념이 종종 두 발전에서 매우 다른 용어로 표현되는 것은 다소 이상한 일이 아닐 수 없다." (왕 1954, 1957:63)

왕 교수는 자신의 논문이 "두 가지 접근 방식을 연결시켜 줄 것"이라고 기대했다.실제로 민스키는 이것을 확인한다: "컴퓨터와 같은 모델에서 튜링 기계 이론의 첫 공식은 왕(1957년)에서 나타난다." (민스키 1967:200)민스키는 카운터머신의 튜링 등가성을 증명했다.

컴퓨터를 단순한 튜링 등가 모형으로 환원하는 것에 관해서, 민스키가 왕에게 "첫 번째 공식화"를 한 것으로 칭한 것은 논란의 여지가 있다.1961년의 민스키의 논문과 1957년의 왕씨의 논문은 모두 셰퍼드슨과 스터기스에 의해 인용되고 있지만, 그들은 또한 유럽 수학자 카펜스트, 에르쇼프, 페터(1958)의 업적을 인용하고 상세하게 요약한다.수학자 에르메스(1954, 1955, 1961년)와 카펜스트(1959)의 이름은 셰퍼슨 스터기스(1963년)와 엘고트 로빈슨(1961년)의 참고 문헌에 모두 등장한다.다른 두 명의 중요한 이름은 캐나다 연구원 멜작(1961년)과 램벡(1961년)이다.더 자세한 내용은 튜링 기계 등가물을 참조하십시오. 참조는 레지스터 기계에서 찾을 수 있습니다.

수학 이론

동작 테이블을 문자열로 인코딩하면 원칙적으로 튜링 기계가 다른 튜링 기계의 동작에 대한 질문에 답하는 것이 가능해집니다.그러나 이러한 질문의 대부분은 결정할 수 없으며, 이는 문제의 함수를 기계적으로 계산할 수 없다는 것을 의미한다.예를 들어, 임의의 튜링 기계가 특정 입력에서 정지할 것인지 아니면 정지 문제로 알려진 모든 입력에서 정지할 것인지를 결정하는 문제는 일반적으로 튜링의 원래 논문에서 결정 불가능한 것으로 나타났다.라이스의 정리는 튜링 기계의 출력에 대한 어떤 사소한 질문도 결정할 수 없다는 것을 보여준다.

범용 튜링 기계는 재귀 함수를 계산하고 재귀 언어를 결정하고 재귀 열거 가능한 언어를 받아들일 수 있다.처치-튜링 논문에 따르면, 범용 튜링 기계로 풀 수 있는 문제들은 알고리즘이나 효과적인 계산 방법으로 풀 수 있는 문제들이다.이러한 이유로, 범용 튜링 기계는 계산 시스템을 비교하기 위한 표준이 되고, 범용 튜링 기계를 시뮬레이션할 수 있는 시스템을 튜링 컴플리트라고 한다.

범용 튜링 기계의 추상 버전은 범용 함수이며, 다른 계산 가능 함수를 계산하기 위해 사용될 수 있는 계산 가능 함수이다.UTM 정리는 그러한 함수의 존재를 증명한다.

효율성.

일반성을 잃지 않고 튜링 기계의 입력은 {0,1} 알파벳으로 가정할 수 있습니다. 다른 모든 유한 알파벳은 {0,1} 위에 인코딩할 수 있습니다.튜링 기계 M의 동작은 그 전이 함수에 의해 결정된다.이 함수는 알파벳 {0, 1) 위의 문자열로도 쉽게 인코딩할 수 있습니다.M의 알파벳 크기, 테이프 수 및 상태 공간의 크기는 전환 함수의 표에서 추론할 수 있습니다.구별되는 상태와 기호는 그 위치로 식별할 수 있다. 예를 들어 처음 두 상태는 관례상 출발 상태와 정지 상태가 될 수 있다.따라서 모든 튜링 머신은 {0, 1) 알파벳 위의 문자열로 인코딩할 수 있습니다.또한 모든 무효 부호화가 즉시 정지하는 사소한 튜링 머신에 매핑되고, 모든 튜링 머신이 프로그래밍 언어에서 코멘트가 동작하는 것처럼 마지막에 임의의 수의 (예를 들어)1로 부호화를 패딩함으로써 무한한 수의 부호화를 가질 수 있다는 것을 소집한다.튜링 기계와 μ-재귀 함수 사이의 Gödel 수와 계산적 등가성이 존재한다면 우리가 이 부호화를 달성할 수 있다는 것은 놀랄 일이 아니다.마찬가지로, 우리의 구성은 튜링 기계_α M인 모든 이진 문자열α와 관련지어진다.

위의 인코딩에서, 1966년에 시작된 F.CHennie과 R.E. 스턴, 그 다음에는 입력 α에 정지한다는multi-tape 보편적 튜링 기계,)CN로그에( 다른 테이프에 주어진)N, C가machine-specific는 번째의 길이에 의존하지 않는다 일정하다 존재하는 입력에)N단계 안에 정지한다는 튜링 기계 Mα을 보여 주었다.e입력 x 단, M의 알파벳 크기, 테이프 수 및 상태 수에 따라 달라집니다.사실상 이것은 Donald Knuth의 Big O ^[5]표기법을 사용한 O${\displaystyle }$(${\displaystyle N}$ log${\displaystyle n}$N$$) \ $displaystyle$\ $mathcal${ $O$} \$left$( $N$\ $log$ { N } \ $right )$ $시뮬레이션$입니다.시간 복잡성이 아닌 공간 복잡성에 대응하는 결과는 O$)\displaystyle(\displaystyle$ {$O}}($^[6]N) $시뮬레이션$에서 최대 CN 세포를 사용하는 방식으로 시뮬레이션할 수 있습니다.

최소 기계

Alan Turing이 범용 기계의 아이디어를 생각해 냈을 때 그는 계산될 수 있는 모든 가능한 함수를 계산할 수 있을 만큼 충분히 강력한 계산 모델을 염두에 두고 있었다.클로드 섀넌은 1956년에 처음으로 가능한 가장 작은 범용 튜링 기계를 찾는 문제를 분명히 제기했다.그는 충분한 상태만 사용된다면 두 개의 기호로 충분하며, 기호와 상태를 교환하는 것은 항상 가능하다는 것을 보여주었다.그는 또한 어떤 하나의 상태의 보편적인 튜링 기계도 존재할 수 없다는 것을 보여주었다.

Marvin Minsky는 1962년 2-태그 시스템을 사용하여 7-상태 4-심볼 범용 튜링 기계를 발견했습니다.다른 작은 범용 튜링 기계는 태그 시스템 시뮬레이션의 이 접근법을 확장함으로써 유리 로고진과 다른 사람들에 의해 발견되었다.m 상태 및 n개의 기호를 가진 UTM 클래스를 (m, n)로 나타내면 (15, 2, 9, 3, 6, 4, 4, (4, 6), (3, 9) 및 (2, 18)^[7][8][9]의 튜플이 발견되었습니다.로고진(4, 6)의 기계는 22개의 명령만 사용하며, 덜 복잡한 표준 UTM은 알려져 있지 않습니다.

그러나, 표준 튜링 기계 모델을 일반화하면 더 작은 UTM이 허용된다. 그러한 일반화 중 하나는 튜링 기계 입력의 한쪽 또는 양쪽에서 무한히 반복되는 단어를 허용함으로써 보편성의 정의를 확장시키고 각각 "반약" 또는 "약" 보편성으로 알려져 있다.규칙 110 셀룰러 오토마톤을 시뮬레이트하는 작고 약한 범용 튜링 기계는 (6, 2, 3, 4), 상태-심볼 ^[10]쌍에 대해 제공되어 왔다.울프람의 2-상태 3-심볼 튜링 기계에 대한 보편성의 증명은 특정 비주기적 초기 구성을 허용함으로써 약한 보편성의 개념을 더욱 확장합니다.작은 UTM을 생성하는 표준 튜링 머신 모델의 다른 변형으로는 여러 개의 테이프 또는 다차원 테이프가 있는 기계와 유한 오토마톤과 결합된 기계가 있습니다.

내부 상태가 없는 시스템

튜링 기계에서 여러 헤드를 허용하면 내부 상태가 전혀 없는 튜링 기계를 가질 수 있습니다."상태"는 테이프의 일부로 인코딩됩니다.예를 들어 0, 1, 2, 0A, 1A, 2A의 6가지 색상의 테이프를 생각해 보겠습니다.3개의 헤드 튜링 기계가 3중(2,2A,0) 위에 위치한 0,0,1,2,1과 같은 테이프를 생각해 보십시오.규칙은 트리플을 다른 트리플로 변환하고 3개의 헤드를 왼쪽 또는 오른쪽으로 이동합니다.예를 들어 규칙에서 (2,2A,0)을 (2,1,0)으로 변환하고 헤드를 왼쪽으로 이동할 수 있습니다.따라서 이 예에서 기계는 내부 상태 A와 B(문자 없음)를 가진 3색 튜링 기계처럼 작동합니다.2헤드 튜링 머신의 경우도 매우 유사합니다.따라서 2-헤드 튜링 기계는 6가지 색상으로 범용할 수 있습니다.다중 헤드 튜링 기계에 필요한 최소 색수가 무엇인지 또는 다중 헤드로 2색 범용 튜링 기계가 가능한지 여부는 알려지지 않았다.이것은 또한 트리플 규칙이 규칙을 다시 쓰는 것과 같기 때문에 다시 쓰는 규칙이 튜링 완전하다는 것을 의미합니다.헤드가 레터 및 그 이웃 8개를 샘플링하여 테이프를 2차원까지 연장하면 예를 들어 110과 같은 수직 트리플 패턴으로 색상을 부호화할 수 있는 등 2가지 색상만 필요하다.

유니버설 머신 코딩의 예

튜링의 지정대로 UTM을 설계하는 도전을 받고 싶은 사람은 코프랜드의 데이비스(2004:103ff)의 기사를 참조한다.Davies는 원본의 오류를 수정하고 샘플 실행의 모습을 보여 줍니다.그는 (어느 정도 단순화된) 시뮬레이션을 성공적으로 실행했다고 주장한다.

다음 예는 튜링(1936)에서 가져온 것이다.이 예에 대한 자세한 내용은 튜링 기계의 예를 참조하십시오.

튜링은 7개의 기호(A, C, D, R, L, N, })를 사용하여 각 5개의 태플을 부호화했다. 튜링 기계에서 기술한 바와 같이, 그의 5개의 튜플은 N1, N2, N3의 유형으로만 구성되어 있다.각 "m-구성"(명령, 상태)의 번호는 "D" 뒤에 A의 단항 문자열(예: "q3" = DAAA)로 표시됩니다.마찬가지로 빈 기호를 "D", 기호 "0"을 "DC", 기호 "1"을 DCC 등으로 부호화한다.기호 "R", "L" 및 "N"은 그대로 유지됩니다.

각 5 태플을 부호화한 후 다음 표에 나타나듯이 문자열로 "어셈블리"됩니다.

현재 m-구성	테이프 기호	인쇄 조작	테이프 모션	최종 m-구성	현재 m-구성 코드	테이프 기호 코드	인쇄작업코드	테이프 모션코드	최종 m-구성 코드	5 태플 조립 코드
문제 1	백지	P0	R	문제 2	DA	D	직류	R	DAA	DADDCRDAA
문제 2	백지	E	R	문제 3	DAA	D	D	R	DAAA	주소
문제 3	백지	P1	R	문제 4	DAAA	D	DCC	R	DAAAA	DAAddccrdAAAA
문제 4	백지	E	R	문제 1	DAAAA	D	D	R	DA	DAAAAddrada

마지막으로, 4개의 5튜플의 코드는 모두 ";"로 시작하고 ";"로 구분되는 코드로 스트링됩니다.

;DADDCRDAA;DADDRDAAA;DAADDCCRDAAAA;DAAAAddrada

이 코드는 "F-제곱"이라는 대체 사각형에 배치하여 "E-제곱"(소거될 수 있는 부분)을 비워 둡니다.U-머신용 테이프의 코드 마지막 조합은 두 개의 특수 기호("e")를 차례로 배치한 다음, 코드를 정사각형으로 구분하고, 마지막으로 이중 콜론 기호 ":"(명확하게 하기 위해 여기에 "."와 함께 공백 표시)로 구성됩니다.

e.;.D.C.D.C.D.A.D.C.D.A.D.A.D.A.D.C.D.A.A.A.A.A.D.C.D.A.D.A.A.A.D.C.D.A.D.A.D.A.D.D.D.C.D.D.D.A.A.D.D.A.D.D.A.A.D.D.D.D.D.D.D.D.D.C.D.D.D.D.D.D.D.D.

U-머신의 작업 테이블(상태 전환 테이블)은 심볼 디코딩을 담당합니다.튜링의 작업 테이블은 마커 "u", "v", "x", "y", "z"를 "표시 기호" 오른쪽에 배치하여 위치를 추적합니다. 예를 들어, 현재 명령 z는 "구성" DAA의 오른쪽에 배치됩니다. x는 현재 "구성" DAA에 대한 위치를 유지합니다.U-machine의 작업 테이블은 계산이 진행됨에 따라 이러한 기호를 셔틀링합니다(지우고 다른 위치에 배치).

e.; .D.D.C.R.D.A.A.; zD.A.AxD.D.A.D.C.C.C.C.C.C.A.A.A.D.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.C.C.C.C.C.C.C.C.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.A.

튜링의 U-머신에 대한 액션 테이블은 매우 중요합니다.

다수의 다른 해설자(특히 Penrose 1989)는 유니버설 머신의 명령어를 부호화하는 방법의 예를 제공하고 있습니다.Penrose와 마찬가지로 대부분의 해설자는 이진 기호만 사용합니다. 즉, 기호 { 0, 1 } 또는 { blank, mark }.Penrose는 더 나아가 U-머신 코드 전체를 작성합니다(Penrose 1989:71–73).그는 이것이 진정한 U-머신 코드라고 단언하는데, 이는 1과 0의 거의 2페이지에 걸쳐 있는 엄청난 숫자이다.Post-Turing 기계를 위한 간단한 인코딩에 관심이 있는 독자에게는 Steen의 Davis(Steen 1980:251ff)에 대한 논의가 유용할 수 있다.

Asperti와 Riccioti는 전체 동작 표를 명시적으로 제공하는 것이 아니라 매우 단순한 의미론을 가진 초등 기계를 구성함으로써 정의된 멀티 테이프 UTM을 설명했습니다.이 접근방식은 마티타 증명 보조기에서 기계의 정확성을 공식적으로 입증할 수 있도록 충분히 모듈화되었습니다.

튜링 기계 프로그래밍

다양한 고급 언어들이 튜링 기계로 컴파일되도록 설계되어 있다.예를 들어 Laconic과 Turing Machine Descriptor가 ^[11][12]있습니다.

「 」를 참조해 주세요.

• 교대 튜링 기계
• Von Neumann 유니버설 컨스트럭터 - 자기 복제 튜링 머신을 구축하려는 시도
• Kleene의 T 술어 - γ-재귀 함수에 대한 유사한 개념
• 튜링 완전성

레퍼런스

일반 참고 자료

• Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"

원본 용지

• Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem" (PDF).

신간지

• Hennie, F. C.; Stearns, R. E. (1966). "Two-Tape Simulation of Multitape Turing Machines". Journal of the ACM. 13 (4): 533. doi:10.1145/321356.321362. S2CID 2347143.

실행

• Kamvysselis (Kellis), Manolis (1999). "Scheme Implementation of a Universal Turing Machine". Self-published.

정식 검증

• Asperti, Andrea; Ricciotti, Wilmer (2015). "A formalization of multi-tape Turing machines" (PDF). Theoretical Computer Science. Elsevier. 603: 23–42. doi:10.1016/j.tcs.2015.07.013. ISSN 0304-3975.

기타 참고 자료

• Copeland, Jack, ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Oxford UK: Oxford University Press, ISBN 0-19-825079-7
• 를 클릭합니다Davis, Martin (1980), "What is Computation?", in Steen, Lynn Arthur (ed.), Mathematics Today: Twelve Informal Essays, New York: Vintage Books (Random House), ISBN 978-0-394-74503-9.
• Davis, Martin (2000), Engines of Logic: Mathematicians and the origin of the Computer (1st ed.), New York NY: W. W. Norton & Company, ISBN 0-393-32229-7, (pb.)
• Goldstine, Herman H.; von Neumann, John. Planning and Coding of the Problems for an Electronic Computing Instrument. Institute for Advanced Study (Rep. 1947 ed.). Princeton.
  Bell, C. Gordon; Newell, Allen (1971). Computer Structures: Readings and Examples (Reprinted ed.). New York: McGraw-Hill Book Company. pp. 92–119. ISBN 0-07-004357-4.
• Herken, Rolf (1995), The Universal Turing Machine – A Half-Century Survey, Springer Verlag, ISBN 3-211-82637-8
• Knuth, Donald E. (1973), The Art of Computer Programming, vol. 1/Fundamental Algorithms (second ed.), Addison-Wesley Publishing Company 크누스의 세 권의 책 중 첫 번째 책입니다.
• Kudlek, Manfred; Rogozhin, Yurii (2002), "A universal Turing machine with 3 states and 9 symbols", in Werner Kuich; Grzegorz Rozenberg; Arto Salomaa (eds.), Developments in Language Theory: 5th International Conference, DLT 2001 Wien, Austria, July 16–21, 2001, Revised Papers, Lecture Notes in Computer Science, vol. 2295, Springer, pp. 311–318, doi:10.1007/3-540-46011-x_27, ISBN 978-3-540-43453-5
• Minsky, Marvin (1962), "Size and Structure of Universal Turing Machines using Tag Systems, Recursive Function Theory", Proc. Symp. Pure Mathematics, Providence RI: American Mathematical Society, 5: 229–238, doi:10.1090/pspum/005/0142452
• Neary, Turlough; Woods, Damien (2009), "Four Small Universal Turing Machines" (PDF), Fundamenta Informaticae, 91 (1): 123–144, doi:10.3233/FI-2009-0036
• Neary, Turlough; Woods, Damien (2009b), "Small Weakly Universal Turing Machines", 17th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 5699, Springer, pp. 262–273
• Penrose, Roger (1989), The Emperor's New Mind, Oxford UK: Oxford University Press, ISBN 0-19-851973-7, (hc.), (pb.)
• Rogozhin, Yurii (1996), "Small Universal Turing Machines", Theoretical Computer Science, 168 (2): 215–240, doi:10.1016/S0304-3975(96)00077-1
• Shannon, Claude (1956), "A Universal Turing Machine with Two Internal States", Automata Studies, Princeton, NJ: Princeton University Press, pp. 157–165
• Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2, vol. 42, pp. 230–65, doi:10.1112/plms/s2-42.1.230
• ）Turing, A.M. (1938), "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction", Proceedings of the London Mathematical Society, 2 (published 1937), vol. 43, no. 6, pp. 544–6, doi:10.1112/plms/s2-43.6.544 。
  Davis, Martin, ed. (1965). The Undecidable (Reprint ed.). Hewlett, NY: Raven Press. pp. 115–154. with corrections to Turing's UTM by Emil Post cf footnote 11 pg:299

외부 링크

Smith, Alvy Ray. "A Business Card Universal Turing Machine" (PDF). Retrieved 2 January 2020.