튜링 기계 : Turing Machine

Turing Machine

1936 년 Alan Turing 이 On Computable Numbers, with an Application to the Entscheidungsproblem 라는 논문에서 소개한 당시로서는 실제 기계가 아닌 추상적인 수학 개념의 오토마타 (Automata) 이었다.

튜링기계는 임시 저장장소가 테이프인 오토마타 (Automata) 이다. 이 테이프는 셀들로 나뉘어 있고, 각 셀은 한 개의 심볼을 저장할 수 있다. 이 테이프와 관련해서 읽기-쓰기 헤드(read-write head) 가 있다. 이 읽기-쓰기 헤드는 테이프에서 왼쪽 또는 오른쪽으로 움직일 수 있고 각 이동마다 하나의 심볼을 읽고 쓸 수 있다....... 우리는 튜링 기계를 오히려 간단한 컴퓨터로 생각할 수 있다. 간단한 컴퓨터는 유한한 메모리를 갖는 처리 유닛 (processing unit) 을 가지고 있고, 테이프에, 무제한 양의 보조 저장장소를 가지고 있다. 그런 컴퓨터가 수행할 수 있는 명령어들은 극히 제한되어 있다. ... 이러한 작은 명령어들의 집합은 복잡한 일을 하기에 적절하지 않은 것처럼 보이나, 그러나 그렇지 않다. 튜링 기계는 원칙적으로 아주 강력하다.......... (Peter Linz 2001)

튜링 '기계' 에 대해서 우선 염두에 두어야 할 사항은 그것이 실제 기계가 아니라 하나의 '추상 수학 개념' 이라는 것이다. 이 개념은 영국의 수학자요 암호 해독 전문가며 컴퓨터의 대가로 알려진 Alan Turing 이 결정문제 (Entscheidungsproblem) 으로 알려진 아주 광범위한 수학 문제를 해결하기 위하여 1936 년에 소개한 개념이다. 이 문제는 독일의 유명한 수학자 David Hilbert 가 1900 년 파리 국제수학회에서 일부 제기한 문제로서 힐베르트의 열 번째 문제라고도 불리는데 이 문제의 완전한 형태는 1928 년 볼로냐 국제학회에서 제시되었다. 힐베르트가 제기한 문제는 매우 엄청난 것이었는데 그것은 모든 수학 문제들을 풀 수 있는 일반적 알고리즘을 찾아 내는 것이었다. 더 엄밀히 말하면 그러한 알고리즘이 (기계가) 원칙적으로 존재할 수 있는가 하는 것에 대한 해답을 구한 것이다. ....

이 문제를 대답하는 데 어려운 점 중의 하나는 도대체 '기계적 프로그램' 의 정확한 의미가 무엇인가를 결정하는 것일 것이다. 그 개념은 당시 일반적인 수학적 개념의 한계를 넘어선 것이었다. 그 개념을 수식화하기 위하여 튜링은 기계 동작을 기본적인 식으로 나누어 정형화함으로써 '기계' 라는 개념이 어떻게 수식으로 표현될 수 있는가를 보이려고 하였다. 튜링은 인간의 뇌 (Brain) 도 하나의 '기계' 로 간주하였다. 그러므로 수학 문제를 푸는 수학자의 행동이 무엇이건 그것이 '기계적 프로그램' 으로 표시될 수 있다고 생각하였다 ....... (Roger Penrose 1989)

튜링기계는 "알고리즘" 또는 "프로그램" 이라 불러도 된다. 현재 우리 주위에 있는 컴퓨터들은 모두 튜링기계라 보아도 좋다. 튜링기계와 형식체계는 일대일 대응을 이룬다.

Turing Machine	형식 체계
입력	공리 (Axiom)
프로그램	추론규칙 (Inference Rule)
출력	정리 (Theorem)

기계를 잘 만들어 임의의 기계가 임의의 입력에 대하여 정지하는지 또는 정지하지 않는지를 (유한시간 안에) 판정할 수 있을까? 튜링은 멈춤문제 (Halting Problem) 의 답이 불가능이라는 것을 "칸토르의 대각화 방법" 을 이용하여 다음과 같이 증명하였다. ..... "그러한 기계는 존재하지 않는다" .... 따라서 Hilbert 의 결정문제 (Entscheidungsproblem) 의 답은 "불가능" 하다.

튜링기계와 Kurt Gödel 의 재귀함수 (Recursive Function) , Alonzo Church 의 람다 계산법 (Lambda Calculus), Emil Post 의 포스트 시스템 (Post Systems) 은 모두 같은 개념이다. Noam Chomsky 는 형식체계에서 기호와 공리의 역할이 언어체계에서 기호와 문법의 역할과 마찬가지라는 것을 보고 문법을 4단계로 분류하였다 (촘스키계층 (Chomsky Hierarchy)). 이들은 모두 튜링기계의 분류라고 말할 수 있다. .... (김홍종)