튜링기계 - 수학 산책

현재 우리는 컴퓨터 없이는 단 하루도 살 수 없는 세상에 살고 있다. 문서 편집과 같은 업무적인 일부터 시작해, 인터넷 검색, 동영상 수업, 동호회 활동이나 게임과 같은 여가생활까지, 컴퓨터가 일상생활에서 차지하는 비중은 어마어마하다. 컴퓨터는 지금까지 인류가 발명한 여러 가지 도구 중에서 일찍이 다른 것에는 없던 아주 독특한 능력을 지닌 도구다. 그렇다면 이러한 컴퓨터는 어떻게 탄생하게 됐을까? 1936년, 영국의 앨런 튜링(Alan Turing, 1912~1954)이라는 청년은 다음 제목의 논문을 런던 수리학회(London Mathematical Society)에 제출한다.

“계산 가능한 수에 대해, 수리명제 자동생성 문제에 응용하면서” (On Computable Numbers, with an Application to the Entscheidungsproblem)

이 논문에서 튜링은 컴퓨터의 근본적인 디자인을 최초로 선보인다. 이때 튜링은 고작 24세였다. 제목만으로는 도저히 컴퓨터와 관계없을 것 같은 이 논문은 컴퓨터의 기본 설계도가 됐다. 이렇듯 현대 컴퓨터의 모델을 최초로 고안한 튜링을 기념해 그것을 ‘튜링기계(Turing Machine)’라고 부른다. 또한, 컴퓨터분야의 노벨상을 “튜링상(Turing Award)”이라고 할 정도로, 튜링기계의 고안은 20세기 이후 과학사의 10대 사건에 뽑힐 만큼 중요한 사건이다.

컴퓨터는 지금까지 인류가 발명한 도구 중에서도 아주 독특한 능력을 지닌 도구다. 그렇다면 이러한 컴퓨터는 어떻게 탄생하게 됐을까? <출처 : NGD>

현대 컴퓨터의 모델이 된 논문 발표 1934년, 튜링은 케임브리지(Cambridge)대학 수학 학부과정을 최우수 성적으로 마친 우수한 학생이었다. 그 후 1936년 9월, 프린스턴(Princeton)대학 고등연구소(Institute for Advanced Study)로 유학 떠나기 직전인 5월에 이 논문을 제출한다. 그런데 이런 비범한 도구를 최초로 설계한 논문 제목이 좀 이상하지 않은가? 재미있게도, 위의 논문은 “이러한 특이한 도구를 디자인했으니 보라”고 주장한 논문은 아니다. 위의 논문은 그 당시 수학계에 내리친 청천벽력과 같은 좌절을 튜링이 다시 증명해 보인 작품이다. 그런데 이 논문에서 컴퓨터의 원천 설계도가 슬그머니 드러난다. 아이러니하게도, 좌절을 증명하는 작품 속에 인류의 정보혁명을 이끌 도구의 설계도가 주요 소품으로 등장했던 것이다. 그렇다면, 그 당시 수학계에 내리친 청천벽력과 같은 좌절은 무엇인가? 그것은 1931년, 미국의 수학자 쿠르트 괴델(Kurt Godel, 1906~1978)이 증명한 다음과 같은 사실이었다.

“기계적인 방식으로는 수학의 모든 사실들을 만들어 낼 수 없다.”

이 같은 괴델의 증명이 있기 전까지, 유럽 수학계에서는 기계적인 방식으로 모든 수학적인 사실들을 만들어 낼 수 있을 것이라는 희망을 품고 있었다. 그래서 이러한 기계가 개발되면 수학자들이 고된 짐을 벗을 수 있을 것이라는 꿈에 부풀었었다. 그런데 괴델은 이러한 생각을 하는 이들에게 “그 꿈은 절대 이루어질 수 없으니, 꿈 깨시오”라고 벼락을 내리쳤던 것이다. 튜링은 이 좌절을 새롭게 증명하는 과정에서 간단한 기계부품들을 정의했다. 그 후, 이 부품들로 하나의 특별한 기계를 만들어 보이는데, 그 기계가 바로 컴퓨터였다. 여기서 말하는 컴퓨터는, 오늘날의 컴퓨터와는 아직 거리가 있다. 튜링기계는 수학 원리로 구성된 가상기계였기 때문이다. 기계부품 정의와 궁극의 기계 탄생 그런데 튜링은 그 증명에서 왜 기계부품들을 정의할 필요가 있었을까? 튜링의 증명은 단도직입적이다. 그것은 바로 기계적인 방식만으론 모든 수학적인 사실들이 만들어질 수 없다는 것이다. 튜링은 이 ‘기계적인 방식’이 뭔지를 곧바로 정의해간다. 우선, 레고 블록 세트와 같은 아주 단순한 다섯 종류의 기계 부품들을 정의한다. 그리고 그 부품들로 만든 기계들로 돌릴 수 있는 것만을 ‘기계적인 방식’이라고 정의한다. 그 후, 이 방식으로는 절대 돌릴 수 없는 계산 문제 하나를 선보인다. 그 계산 문제의 답은 참인지 거짓인지 아무도 알 수 없다. 이를 통해 기계적인 방식으로 참인 사실을 모조리 만들어 낼 수 있는 것은 아니라는 결론을 이끌어낸다. 튜링은 이 증명의 중간을 통과하면서 컴퓨터의 설계도를 펼쳐 보인다. 그 증명의 중앙부는 하나의 의문으로 시작한다.

튜링이 정의한 ‘기계적인 방식’이 과연 ‘기계적인 방식’의 전부일까? 튜링이 정의한 기계부품들만 있으면 어떤 기계적인 계산도 척척 해내는 기계를 만들어낼 수 있는 것일까?

튜링은 이 의문에 대해, 그렇다는 증명 대신 기계들의 예를 보여준다. 이 예시들 중 ‘궁극의 기계’라는 특이한 기계를 만들어 보이는데, 튜링은 이 궁극의 기계를 이용해서도 작동시킬 수 없고, 참인지 거짓인지도 알 수 없는 계산문제가 있다는 것을 보인다. 그런데 바로 이 궁극의 기계에 컴퓨터의 원천 설계도가 담기게 된다. 이 궁극의 기계를 소개하기 전에, 우선 튜링이 정의한 기계부품들이 무엇인지 살펴보자. 그 기계부품들은 매우 단순하다. 아래 그림은 기계부품으로 만든 튜링기계의 한 예이다.

기계부품으로 만든 튜링기계의 한 예. 기계의 부품은 테이프, 테이프에 기록되는 기호, 그 기호를 읽고 쓰는 장치, 장치의 상태, 기계의 작동 규칙표로 이루어진다. (가)와 같은 가로줄 하나가 하나의 작동 규칙이고 이 규칙들이 유한개 모여서 작동 규칙표를 이룬다. 박스 안의 시계 바늘은 현재 상태를 가리킨다.

부품들은 총 다섯 가지로 이루어져 있다. 그것은 무한히 많은 칸을 가진 테이프, 테이프에 기록되는 기호들(A, B, C… 등 유한 개), 테이프에 기록된 기호를 읽거나 쓰는 장치, 그 장치의 상태들(Q₁, Q₂ … 등 유한 개), 기계의 작동 규칙표이고, 기계마다 이 다섯 가지 부품이 구체적으로 정해진다. 기계의 작동 규칙은 다음과 같다. 우선 몇 개의 기호들을 테이프에 읽고 쓰게 될 것인지, 장치의 상태들이 몇 개나 되는지, 작동 규칙표는 무엇인지, 테이프의 시작 모습과 읽고 쓰는 장치의 시작 상태, 테이프의 시작 위치가 정해진다. 이렇게 정의된 기계가 작동 규칙표에 정의돼 있는 규칙대로 작동하면서 정해진 계산을 진행하게 되는 것이다. 작동 규칙에 표현되는 기계의 작동은 매우 간단한 일로만 제한된다. 테이프 칸의 기호를 읽고 쓰면서 테이프를 한 칸씩 좌우로 움직여 가는 일만 할 수 있다. 이러한 과정을 거치면서 기계의 상태가 매번 변경된다.

튜링이 만들어 보인 ‘궁극의 기계’도 이렇게 구성돼 있으며, 이 기계에 컴퓨터의 원 설계가 담기게 된다. 이것은 즉, 이 기계에 컴퓨터의 핵심능력(하나의 컴퓨터가 모든 일을 할 수 있는 능력)이 처음으로 등장했다는 뜻이다.  이 궁극의 기계는 두 가지 대담한 설계를 담고 있다. 첫째는, 임의로 정의한 튜링기계(작동 규칙표와 테이프 초기 상태)를 일렬로 된 테이프에 표현할 수 있다는 것이다. 둘째는, 테이프에 표현된 기계의 정의를 이해하고, 그 동작을 그대로 흉내 낼 수 있도록 작동 규칙표를 정의한 것이다. 이는 고정된 작동 규칙표에 따라 테이프에 기록된 임의의 기계를 그대로 흉내 낼 수 있다는 뜻이다.

튜링은 1943년, 플라워스와 공동으로 세계 최초의 연산 컴퓨터 ‘콜로서스’를 제작했다. 사진은 영국 브래츨리 파크에 재건된 콜로서스. <출처: (CC) MaltaGC at wikipedia.org>

튜링은 이 궁극의 기계를 ‘보편만능기계(Universal Computing Machine)’라고 불렀다. 필요한 계산을 수행하는 튜링기계를 그 기계의 테이프에 입력하면, 입력된 튜링기계의 작동을 그대로 흉내 내주기 때문이다. 튜링은 이 기계로 자신이 정의한 모든 기계적인 계산을 해낼 수 있었다.

현대 컴퓨터의 모델이 된 튜링기계.

보편만능기계, 현대 컴퓨터의 시초 오늘날의 컴퓨터는 바로 튜링의 보편만능기계를 그대로 구현한 것이다. 이쯤에서 현대 컴퓨터를 살펴보자. 거기에는 튜링이 정의한 기계 부품들이 고스란히 구현돼 있다. 테이프는 메모리칩으로, 테이프에 읽고 쓰는 장치는 메모리칩과 입출력 장치로 발전했으며, 작동 규칙표는 중앙처리장치(CPU)로 발전했다. 만일 실행시키고 싶은 계산이 있다면, 그것의 작동 규칙표(소프트웨어)를 만들어 메모리에 넣어주기만 하면 된다. 그러면 컴퓨터는 그 소프트웨어의 정의대로 일을 수행할 것이다. 이렇듯, 현대 컴퓨터는 튜링이 정의한 기계적인 방식으로 동작할 수 있는 모든 프로그램을 실행시킬 수 있는 보편 만능의 기계다. 또한, 튜링의 이론은 현대 컴퓨터뿐만 아니라, 로봇의 설계 등에도 큰 도움을 주고 있다. 하지만, 아직 인류가 알지 못하는 문제가 있다. 그것은 바로 튜링의 기계를 능가하는 컴퓨터의 등장이 가능할지 여부다. 튜링이 정의한 기계적인 방식을 넘어서는 컴퓨터가 가능할까? 아직까지는 가능하다고도, 불가능하다고도 증명된 바가 없다. 그러나 누가 알겠는가. 1936년, 튜링이 현대 컴퓨터의 근본적인 디자인을 선보인 지 1백 년 후인 2036년쯤, 또 다른 24세의 학생이 어느 구석에서 튜링의 기계를 능가하는 컴퓨터를 암시하는 디자인을 슬쩍 펴보이는 일이 생길지.