튜링머신에 대한 완벽한 이해 (1편)

요약

과거에는 어떤것이 "computable" 한지 혹은 아닌지에 대한 수학적인 정의가 없었다. 엘런튜링 이 개발한 Turing machine 은 어떤것이 연산가능한지/아닌지를 판단할 수 있는 수학적 정의를 제공해주어 computability(계산 가능함) 에 대한 거대 담론의 시발점이 되었고, 또한 이는 현대의 컴퓨터의 전신이 되었다. 

 

Motivation

"튜링 머신이 등장하게 된 배경은 무엇일까?"

20세기 초반, 독일의 수학자 힐버르트는 정의와 공리를 입력하면 모든 수학적 명제를 도출해 줄 수 있는 만능 기계를 만들자는 제안을 한다. 쉽게 말해 우리가 알고있는 수학적 명제와 정의들을 때려 넣으면 자동으로 증명을 해주는 컴퓨터를, 즉 수학자를 대체할 인공지능을 개발하자는 것이다.  

앨런 튜링은 힐버르트 프로젝트가 불가능하다고 주장하기 위해 반례를 드는 방식으로 증명한다. 모든 계산을 할 수 있는 보편적 만능기계를 설계하고 그 기계로도 정지문제는 풀 수 없다고 주장한다. 이때 설계한 만능 기계가 바로 튜링머신이다. 과연 어떻게 했을까? 이 논리를 따라가려면 우선은 튜링머신에 대한 이해가 선행되어야하고 그 다음 증명을 살펴보아야한다. 

Turing machine 은 실존하는 기계가 아니라 수학적 상상이다. 튜링 머신이 제안될 당시는 (1936년) 컴퓨터가 개발되기 한참 전 이였고 심지어는 제대로된 기계장치도 많지 않았던 시대임을 염두에 두자.

튜링머신의 구성요소

 

구성 요소중 가장 기본이 되는 헤드와 테이프의 도식이다. 

 

1. 테이프 (메모리): 기호 정보를 저장할 수 있는 셀이 연결된 정보저장 장치

2. 헤드 (cpu): 셀을 읽고 쓰거나 좌우로 이동할 수 있는 제어 장치 

3. 알파벳 집합 (모든 정보)

4. 상태 집합: 튜링 머신이 가질 수 있는 모든 상태

5. 명령 테이블: 현재 상태와 기호에 따라 해야할일을 지정하는 명령 목록

 

여기에서 튜링머신이 어떻게 작동하는지를 한번 보고오면 훨씬 이해가 쉬울 것이다. 2분정도 되는 짦은 영상인데 꽤 훌륭한 시각화를 제공한다. 참고로 우리가 종종 보는 예시는 가장 기본적인 형태인 one-head one-tape turing machine 이고 헤드가 여러개거나 테이프가 여러개가 되는 등 변형된 형태의 다양한 튜링 머신이 존재한다. 

 

테이프는 현대의 컴퓨터의 메모리에, 헤드는 cpu에 대응되며 0,1 의 정보는 모든 정보로 일반화될 수 있다. 왜 튜링머신이 컴퓨터의 전신이 되었는지 알 수 있다. 

 

튜링머신은 어떻게 계산가능함 (computability)를 정의하는데 도움을 주는가?

사실 튜링머신과 유사한 시스템들(post systems, μ-recursive functions, λ-calculus, combinatory logic)이 많이 존재하는데 이들은 다루는 데이터의 종류에만 차이가 있다. 예를들어 튜링머신이 유한한 알파벳으로 이루어진 기호집합을 다룬다면 유사한 시스템인 μ-recursive functions 은 자연수를 다룬다. 중요한 사실은 그 시스템들이 상호 변환 가능하다는 것이다. 이는 자연수가 0,1 로 표현된 이진수로 변환 가능하듯 모든 정보를 0,1로 표현될 수 있다는 사실을 이해하면 쉽게 받아들일 수 있다. 

모든 종류의 데이터가 튜링머신에 들어가는 기호 집합과 같은 형태로도 변환 가능하기 때문에 이론적으로 계산가능한 모든 것을 이 튜링머신으로 계산할 수 있다. 현실에 존재하는 컴퓨터는 메모리가 무한대가 아니기 때문에 어떤 문제가 현실에서는 사실상 풀 수 없더라도, 튜링머신은 무한대의 셀을 가정하므로 이 문제의 연산이 가능할 수 있다. 따라서 어떤 문제가 computable 하다는 것을 튜링머신으로 풀 수 있다고 정의하는 것이 꽤나 타당하다. 

정리하자면, 튜링머신이 정립되기 이전에는 다양한 문제를 효과적으로 풀기 위한 알고리즘은 상당히 많이 제안되어왔지만 그것들이 효과적인 연산(effective computation) 인지 판단하는 것에 대한 명확한 기준이 없었다. 튜링 머신을 포함한 당대에 제안된 시스템들(post systems, μ-recursive functions, λ-calculus, combinatory logic), 그리고 그들이 상호 변환 가능하다는 사실의 발견이 어떤 알고리즘이 computable/noncomputable 한지 구분지을 수 있는 일반적인 기준을 정립할 수 있게끔 도와주었다. 

 

왜 우리는 튜링머신을 공부하는가?

언급된 유사한 시스템들도 모두 중요하지만 앞서 언급했듯 튜링머신이 가장 현대의 컴퓨터와 비슷한 형태이기때문에 우리는 튜링머신에 대해 공부한다. 물론 튜링머신이 computation 에 대한 모든 정의를 포함하는 것은 아니다. 예를들어 튜링머신으로 ramdomized 혹은 interactive computation에 대해 논할 수는 없다. 하지만 튜링머신을 이용한 computation의 정의는 견고하며 중요하다.