튜링 기계
이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이다. 상당히 간단해 보이지만 이 기계는 적당한 규칙과 기호를 입력한다면 일반적인 컴퓨터의 알고리즘을 수행할 수 있으며 컴퓨터 CPU의 기능을 설명하는데 상당히 유용하다.
1936년 앨런 튜링은 계산하는 기계를 대표할 수 있는 가상의 장치를 만들었고
이 장치에 영어 단어인 automatic의 a를 따서 "a-기계"라는 이름을 붙였다. 이 기계가 바로 나중에 창시자인 앨런 튜링의 이름을 따서 튜링 기계라 불리게 되었다.
1948년 "똑똑한 기계"라는 글에서 앨런 튜링은 자신의 "a-기계"를 간결히 정의하였다. 1936년 논문 "계산 가능한 수와 결정성 문제에의 응용"을 언급하며 튜링기계(이 글에서는 논리적 계산 기계라는 표현을 사용한다.)를 다음과 같이 기술하였다.
튜링 기계는 수학적 모형의 일종으로, 특수한 테이프를 기반으로 작동하는 기계이다. 튜링 기계가 사용하는 테이프 위에는 테이프 머릿기호를 바탕으로 기계가 인식하거나 기록할 수 있는 기호들이 있다. 작동 방식은, “42번째 상태에서 0이라는 기호가 있다면 1을 쓴다. 1이라는 기호가 있다면 17번째 상태로 간다. 17번째 상태에서 0이라는 기호가 있다면 1을 쓰고, 1이라는 기호가 있다면 6번째 상태로 간다”와 같이 유한한 개수의 기초적 지시문으로 이루어진다. 원문(“계산가능수와 결정문제에 대한 응용에 관하여On computable numbers, with an application to the Entscheidungsproblem”)에 따르면 튜링이 상상한 것은 이러한 연산을 특출하게 수행할 수 있는 "컴퓨터"라 불릴 사람이었다.
더 자세히 설명하자면, 튜링 기계는 다음과 같은 부분들로 구성되어 있다.튜링 기계가 가진 기호와 상태, 그리고 행동은 모두 유한하고 이산적이며, 구분 가능하다.
호프크로프트와 일맨은 7투플의 단일 테이프 튜링 기계를
formula_1로 정의했다. 각 변수들의 의미는 다음과 같다.
이 정의를 바탕으로 작동하는 모든 것은 튜링 기계라고 불린다.
반 엠데 보아스(1990)에 따르면, “7투플의 이론적 구상은 기계의 행동과 계산의 극히 단적인 부분밖에 보여주지 못한다”라고 말했다.
예를 들면,
정의들은 설명을 위해 조금씩 다르게 표현되지만, 항상 같은 계산력을 가지도록 유도된다. 예를 들어, 집합 formula_9를 formula_10로 바꾸는 연산은 기계의 계산력을 높여주지 않는다.
가장 일반적인 정의는 튜링 기계의 지시를 튜링표로 표현한 것이다. 이것은 9개의 5투플로 구성되어 있다. (튜링(1936), 해독불가능에 대해서, p. 126-127과 데이비스(2000) p. 152)
다른 저자들 (민스키(1967), p. 119, 호프크로프트와 일맨 (1979) p. 158, 스톤 (1972) p. 9)은 새로운상태 qm이 읽혀진 기호 Sj의 바로 뒤에 위치하게 함으로써 다른 정의를 취했다.
이 글의 나머지 부분에 대해서는 “정의 1” (튜링/데이비스 정의)를 사용할 것이다.
다음 표에서 볼 수 있듯이, 튜링의 본래 모델은 N1, N2, N3라고 불리는 세 가지의 행동만을 허용했다. 예를 들어, 읽혀진 구간의 지우기를 0번째 기호인 S=”지움” 또는 “비어있음” 등으로 표현하는 것은 허용했으나 아무것도 쓰지 않는 것은 허용하지 않았기 때문에 모든 행동에는 “기호 S를 인쇄한다” 또는 “지운다”라는 명령이 포함되어 있었다. 약어들은 튜링이 만든 것인데, 튜링의 원문이 나온 이후 기계 모델은 9가지의 5투플을 포함하고 있다.
어떠한 종류의 튜링표도 위의 아홉 개의 5투플로부터 조합될 수 있다. 기술적인 이유로 세 개의 “N” 지시는 무시되기도 한다. 반면, 4투플은 잘 사용되지 않는다. 이들은 튜링 지시를 단순화할 때 사용된다.
튜링 기계를 설명하는 데 있어서 상태라는 말은 두 가지의 뜻을 가진다. 대부분의 경우는 현재 지시의 이름이나 내용을 뜻한다(상태 기록기에 저장된 정보). 하지만 튜링 (1936)은 계산과정 상에서 기계의 m배열과 기계의 진행 상태를 확실하게 구분했다. 튜링이 “상태식”이라 표현했던 것은 현재의 지시와 테이프 상의 모든 기호들을 포함한다.
이러한 모식도들은 일련의 계산 궤적을 나타내는 것이 아니라 순간을 포착해서 보여주는 것이다. 아주 바쁜 기계는 작동하는 동안 항상 동일한 궤적을 따라 진행하지만 다른 유사한 기계의 경우에는 아닐 수도 있다.
단순한 범용 튜링 기계보다 더 높은 계산능력을 지니고 있는 기계가 존재할 것이라는 주장이 있었지만, 그러한 가상 기계들은 결국 범용 튜링 기계와 같은 능력을 가지고 있다는 사실이 증명되었다(홉크로프트와 울만, p. 159, cf Minsky(1967)). 그 기계들이 더 높은 속도와 적은 저장 공간을 가질지언정, 범용 튜링 기계보다 더 많은 수학적 함수들을 계산 할 수는 없다는 것이다.(처치-튜링 명제는 모든 기계가 이러한 법칙을 따를 것이라고 주장한다. 즉 모든 계산 가능한 문제는 튜링 기계로 계산할 수 있으며, 그 역 역시 성립한다는 의미이다.)
몇 개의 다른 모델들도 튜링 기계와 동일한 계산 능력을 가지고 있다는 것이 밝혀졌다. 그중에는 다중 테이프 튜링 기계, 다중 트랙 튜링 기계, 입력과 출력이 있는 튜링 기계, 비결정론적 튜링 기계등이 있다.
튜링은 미결정성에 다음과 같이 적었다.
지금은 이 발견이 당연하다고 생각하지만 그 당시(1936)로서는 정말 놀라운 발견이었다. 일부 학자들은 튜링이 범용 기계(Universal Machine)"이라고 부른 이 계산 모델이 프로그램 내장식 컴퓨터를 위한 기초적인 이론적 해결책을 제시했다고 생각한다.
계산복잡도의 측면에서 보면 다중테이프 튜링 기계는 이 기계가 시뮬레이트하는 기계에 비해 로그 인수만큼 느려야 한다. 이 결과는 1966년에 F.C. 헨리와 R.E. 스턴에의해 얻어졌다.(아오라와 바락, 2009, 정리 1.9)
흔히들 튜링 기계는 다른 오토마타와 다르게 실제 기계만큼 강력하고 실제 프로그램이 할 수 있는 연산을 모두 실행할 수 있다고 한다. 여기서 간과하고 있는 사실은 실제 기계는 유한개의 배형만을 가질 수 있기 때문에 이 "실제 기계"는 선형 구속 오토마타에 그친다. 그에 비해 튜링 기계는 연산을 위한 무한한 저장 공간을 가진 기계이다. 튜링 기계는 컴퓨터를 모델링한 것이 아니라 연산 자체를 모델링한 것이다. 역사적으로 보자면 고정된 내부 저장장치를 이용해 연산하는 컴퓨터는 튜링 기계보다 훨씬 나중에 개발되었다.
튜링 기계는 다음과 같은 이유들로 실제 컴퓨터의 모형으로서 상당히 유용하다.하지만 튜링 기계도 어떤 경우에는 실제 프로그램에 대한 좋지 못한 모델이 될 수 있다. 운영 체제나 워드 프로세서 같은 경우에는 시간에 따라 무한한 입력을 받을 수 있어야 하는데 튜링 기계는 그러한 무한한 연산의 경우 모델링이 힘들다.(그렇지만 역시 부분적인 과정들은 모델링할 수 있다.)
튜링 기계의 한계는 일부 배열들의 능력을 잘 모델링하지 못한다. 현대의 저장 프로그램 컴퓨터들은 추상적인 랜덤 접근 저장 프로그램 기계(Random Access Store Program Machine, RASP machine)들의 실질적인 예이다. 범용 튜링 기계와 같이 RASP는 무한개의 구분 가능한, 동시에 셀 수 있지만 무한한 레지스터(정수를 하나 저장할 수 있는 메모리 공간)를 가지고 있다. RASP의 유한 상태 기계는 하나의 레지스터가 다른 레지스터의 주소를 포함 하는 등 간접적으로 주소를 저장하는 것이 가능하다. 따라서 RASP의 프로그램은 레지스터 배열에 있는 다른 레지스터를 호출하는 것이 가능하다. 메모리 인덱스를 이용한 연산의 최적화가 튜링 기계에서는 불가능하므로 튜링 기계로 모델링 할 때 일부 알고리즘에 대해서는 시간복잡도의 잘못된 하한을 줄 수 있다. 예를 들어 이진 검색 알고리즘의 경우 튜링 기계 모델보단 RASP 모델로 훨씬 더 빠르게 연산이 가능하다.
앨런 튜링(1912-1954)의 제자이자 평생의 친구인 로빈 간디(1919-1995)는 '계산 기계(calculatng machine)'의 관념의 기원을 배비지에서 찾았으며 실제로 배비지 이론을 제안했다.
간디는 배비지의 해석 기관을 다섯 개의 연산으로 묘사했다.간디는 1, 2, 4에 의해 계산될 수 있는 함수를 계산 가능한 함수로 정의했다.
1900년 수학자 다비트 힐베르트가 제안한 힐베르트의 문제들 중 열 번째 문제는 그 개념이 정립되기 이전에 거의 30년 가까이 해결되지 않은 채 부유했다. 힐베르트의 열 번째 문제는 다음과 같다.
1928년 힐베르트는 다음의 세 물음을 통해 자신의 문제를 좀 더 엄밀하게 만들었다.
첫 번째와 두 번째 문제는 1930년 쿠르트 괴델에 의해 해결되었으나, 세 번째 문제는 1930년대 중반까지 해결되지 않았다.
1935년 봄, 케임브리지 킹스 칼리지의 젊은 박사 과정 학생이었던 튜링은 한 과제에 직면했다. 그는 논리학자 뉴먼의 강의에 자극을 받았으며, 결정 문제에 대한 괴델의 연구에 대해서 알게 되었다. 뉴먼은 '기계적'이라는 단어를 사용했으며, 1955년 튜링의 부고에 뉴먼은 다음과 같이 기술했다.
튜링은 그의 일생동안 기계에 대한 흥미를 가지고 있었다. 아래에도 나와있지만, 튜링은 그의 박사후과정 동안 불 논리 곱셈 기계를 만들었다. 그의 박사후과정 논문인 'Systems of Logic Based on Ordinals'는 계산 가능한 함수에 대한 다음의 정의를 담고 있다.
튜링이 영국으로 돌아왔을 때, 그는 독일의 암호 기계인 '에니그마 the Enigma'를 해독하기 위한 방법을 구상하는 것에 참여했다.
그는 ACE(Automatic Computing Engine)의 개발에 참여하기도 했다.
1937년, 그의 박사후 과정을 위해 프린스턴에서 연구하는 동안 튜링은 전기-기계식 릴레이를 이용해 디지털(Boolean-logic) 곱셈 기계를 만들었다.
튜링의 발명은 단순한 호기심과 실험 정신에 의해 시작되었지만, 같은 방향을 향하는 연구들이 독일과 미국에서 행해지고 있었으며,
그러한 노력의 결과물은 2차 세계 대전 동안 연합국과 주축국의 군사 활동에 사용되었다.
1950년대 중반 하오 왕과 마빈 민스키는 튜링 기계를 좀 더 간단한 형태로 바꾸었다.
동시에 유럽의 연구자들은 최신식의 전자 컴퓨터를 현재의 튜링 기계인 '컴퓨터와 같은 이론적 오브젝트'로 환원시켜 생각했다.
1950년대 후반에서 1960년대 초반에 멜자크와 레벡(1961), 민스키(1961), 셰퍼슨과 스터기스(1961) 등의 유럽 연구자들은 일련의 연구들을 통해 튜링 기계를 좀 더 친숙하고 컴퓨터와 같은 '셈 기계 counter machine'로 만들었다.
이후 1970년대 초반에는 엘곳과 로빈슨(1964), 할트마니스(1971), 쿡과 렉하우(1973) 등은 이 연구를 진척시켜 '기록 기계 register machine'와 RAM의 모델로 발전시켰다.
오늘날의 셈 기계, 기록 기계, 그리고 RAM은 그 근간을 튜링 기계에 두고 있으며, 수많은 연구자들은 계산 이론을 풀어나가는 데에 있어서 튜링 기계를 사용한다.
특히 계산 복잡도 이론의 경우 튜링 기계의 사용이 필수적이다.