컴퓨터를 전공한다는 것 3편 - 계산이론 (상)

컴퓨터를 전공한다는 것 3편 - 계산이론 (상)

2020, Jul 16    

드디어 마지막 편이다. 다시 한번 1편에서 정리했던 과목 목록을 가져와 보자.

  1. 컴퓨터 시스템 : 디지털시스템설계, 컴퓨터 SW시스템 개론, 컴퓨터 네트워크, 컴퓨터구조, 운영체제
  2. 프로그래밍, 개발방법론 : 프로그래밍과 문제해결, 객체지향프로그래밍, 소프트웨어설계방법
  3. 수학 : 미적분학, 선형대수학, 이산수학, 확률과 통계
  4. 계산이론 : 데이터구조, 알고리즘, 프로그래밍언어론, 오토마타 & 형식언어

우리는 지난 글들을 통해 현대 컴퓨터가 어떻게 작동하는지 그 시스템을 이해했고, 그 시스템 위에서 작동한 프로그램을 효율적으로 만드는 방법도 배웠다. 이제 당신은 당신 앞에 놓여 있는 컴퓨터가 어떤 놈인지 잘 알게 되었다. 그런데 그 컴퓨터라는 개념은 누가 처음 생각해냈고, 처음 만들었을까? 또 도대체 어떤 기반이 있었기에 이렇게 대단한 기계를 만들 수 있었던 것이고, 컴퓨터와 컴퓨팅에 관한 학문은 어떤 과정을 통해 발전했을까? 이번 글을 다 읽고 나면 이 질문에 대한 답은 물론이고, 이러한 내용을 컴퓨터공학과에서 어떻게 가르치며, 또 배워야 하는지도 알게 될 것이다. 자 그러면 시작해 보자.

계산이론의 시작

2014년 개봉한 이미테이션 게임이라는 영화는 영국의 수학자이자 전산학자 앨런 튜링 (Alan Turing) 의 삶을 기초로 제작되었다. 그 당시 고3이었음에도 꿋꿋이 영화를 보러 갔는데, 나름 재미있었던 기억이 난다. 이 글을 쓰기 위해 다시 찾아보니 실제로 평가도 굉장히 좋았다.

로튼토마토 토마토미터가 90%, 팝콘지수도 91퍼다. 세기의 명작 쇼생크 탈출이 90%고 라라랜드가 93퍼니, 이미테이션 게임의 완성도 역시 나무랄 바가 없는 것이다. 그럼에도 사실 난 이 영화를 별로 좋아하진 않는데, 튜링의 삶을 상당 부분 왜곡하고 또 그의 삶이나 업적에서 정작 중요한 내용은 다루지 않았기 때문이다. 물론 영화의 만듦새나 흥행을 위한 결정이었겠지만, 2020년 컴퓨터과학도가 되어 이 영화를 다시 떠올리자니 아쉬움이 앞서는 건 어쩔 수 없다.

아무튼, 이 영화에게 가장 불만인 점은 튜링이 마치 현대 컴퓨터의 원형을 만든 것처럼 묘사된 것이다. 영화에서 그와 동료들은 독일군의 암호기계 애니그마에서 생성된 암호를 해독하기 위해 기계장치를 고안하는데, 이를 마치 우리가 흔히 말하는 “컴퓨터”인 것 처럼 묘사했다. 또한 그 기계가 튜링의 천재적인 능력 덕분에 만들어진 것처럼 이야기했는데, 실상은 굉장히 다르다. 일단 영화에서 나온 기계는 튜링 스스로가 정의한 “컴퓨터”의 정의와 전혀 부합하지 않는 암호풀이 기계에 불과하다. 애초에 설계 자체도 튜링이 한 것이 아니라 폴란드의 암호해독기계를 기반으로 이루어졌던 기계다. 실제로 그가 현대 컴퓨터의 원형을 고안한 것은 사실이지만, 영화처럼 기계적으로 작동하는 실체화된 컴퓨터를 만들지는 않았다. 그렇다면 대체 그는 무엇을 했길래 컴퓨터의 원형을 만들었다고 평가받는 것일까?

이 질문에 답하기 위해서는 튜링이 암호해독기계를 만들었던 1940년대에서 300년을 더 거슬러 올라가야 한다. 17세기 독일의 위대한 수학자이자 철학자 고트프리트 라이프니츠 (Gottfried Leibiniz) 는 미적분을 발명한 것으로 유명하지만, 이진법을 발명하기도 했다. 또한 그는 이진법을 토대로 사칙연산이 가능한 최초의 기계식 계산기를 고안하기도 했다. 그는 여기서 그치지 않고 수학적 논리를 다룰 수 있는 계산기를 꿈꾸었다. 그런데 여기서 그는 사람들이 쓰는 “자연어”가 수학적, 논리적 명제를 기술하는 데 크나큰 문제가 있음을 발견했다. 그의 앞길을 가로막은 것은 바로 자연어의 애매모호함과 중의성이었다. 쉽게 말해서 이런 것이다. 나는 어제 과제를 다 한 학생을 만났다. 라는 문장이 있을 때, 이 문장은 두 가지 방식으로 해석 가능하다.

  • 나는 “어제 과제를 다 한 학생” 을 오늘 만났다.
  • 나는 “과제를 다 한 학생”을 어제 만났다.

이렇게 단순한 문장조차 여러 방식으로 해석 가능한 상황에서, 컴퓨터가 알아들을 수 있는 “중의적이지 않은, 확실한 의미를 가지는” 문장을 자연어로 쓰는 것은 불가능함을 쉽게 알 수 있다. 라이프니츠는 이 문제를 해결하기 위해 애매모호함이 없는 언어를 연구하는 등 논리학의 발전에 힘썼다. 아쉽게도 그의 작업은 제대로 출판되지 않아 200년 가까이 잊혀졌지만, 다행히 후대의 수학자들 역시 같은 문제에 관심을 가지고 꾸준히 연구한 덕에 라이프니츠의 꿈 - 수학적 논리를 다룰 수 있는 계산기 - 는 점점 현실에 가까워졌다.

이후 20세기에 이르러 수학자 다비드 힐베르트 (David Hilbert) 는 이 문제를 보다 확실하게 정의했다. 그가 결정문제(Entscheidungsproblem) 라 이름붙인 이 문제는 다음과 같이 풀어 설명할 수 있다.

주어진 일차 논리 문장이 참인지 거짓인지 결정하는 알고리즘이 존재하는가?

여기서 “일차논리”는 그냥 학부에서 배우는 일반적인 수학, 논리 명제라고 생각하면 되고, 알고리즘은 정해진 일련의 문제 해결 단계라고 보면 된다. 그렇다면 이 문제는 다음과 같이 더 쉽게 쓸 수도 있다.

다음과 같은 기계를 상상해 보자. 이 기계에 수학적 명제를 입력하고 손잡이를 내리면 특정한 계산을 수행해 그 결과값으로 입력한 명제가 참인지 거짓인지 여부를 알려준다. 이 기계를 만들 수 있는가?

이 시점에서 이 단락의 제목: 계산이론의 시작 으로 돌아가 보자. 확실히 이 문제는 무엇인가 계산하는 것과 관련되었다. 그리고 이 문제를 풀기 위해 수많은 수학자들이 달려들었다. 결과적으로 이 문제는 풀렸다. 앨런 튜링과 알론조 처치 (Alonzo Church) 는 1936~37년 각자의 방법으로 그러한 기계를 만들 수 없다 는 것을 증명했고, 이 결론에서 지금의 계산이론, 더 나아가 컴퓨터과학이 시작되었다.

이제 대충 왜 이런 구구절절한 내용을 설명했는지 감이 올 것이다. 어떤 학문을 배울 때 그 학문의 역사를 아는 것이 굉장히 중요하다는 데 동의하지 않을 사람은 거의 없을 것이다. 당신의 물리학과 학부생이라면 아이작 뉴턴에르윈 슈뢰딩거 의 이름을 모를 수는 없을 것이며, 가우스페르마의 업적을 공부하지 않고 정수론을 이해하는 것은 불가능할 것이다. 컴퓨터과학도 마찬가지다. 컴퓨터가 무엇인지, 어떻게 작동하는지 제대로 알기 위해서는 컴퓨터, 컴퓨팅과 관련된 학문이 어떻게 시작되었고 발전되었는지, 그리고 이를 위해 평생을 바친 학자들의 삶을 알아야 한다. 일단 잠깐 이야기했던 튜링의 업적부터 따라가 보자.

컴퓨터의 이론적 토대 - 오토마타 & 형식언어

튜링과 그의 기계

위에서 언급했듯이, 튜링은 힐베르트의 결정문제를 풀었다. 물론 힐베르트의 기대가 무색하게 그 결론은 “불가능”이었지만 말이다. 그는 어떻게 이 문제를 풀어낸 것일까? 그리고 이 문제를 푼 것이 어떻게 컴퓨터과학의 시작으로 이어진 것일까?

이 문제에 답하기 위해서는 다시 한 발짝 뒤로 가야 한다. 사실 결정문제를 최초로 푼 사람은 튜링이 아니다. 그보다 앞서 천재 수학자 쿠르트 괴델(Kurt Gödel) 가 이미 힐베르트를 좌절시켰다. 튜링이 결정문제를 자신만의 방법으로 풀기 5년 전, 그는 수학원론, 그리고 관련된 시스템 내에서 형식적으로 결정불가능한 명제들에 관하여 (On Formally Undecidable Propositions of Principia Mathematica and Related Systems) 라는 책에서 그 유명한 불완전성 원리의 증명을 제시했다.

불완전성 정리를 한마디로 정리하자면 이렇다. 모든 사실이 증명가능하지는 않다. 좀 더 풀어쓰자면 이렇다.

수학에서 페아노 공리계를 포함하는 포함하는 모든 논리 체계는 참인 일부 명제를 증명할 수 없다.

여기서 페아노 공리계란 수학에서 자연수 체계를 정의하는 공리계다. 우리가 수학을 하는 데 1, 2, 3… 이런 가장 기본적인 숫자를 빼놓을 수는 없고, 그렇기에 수학 논리체계에 가장 기본적으로 포함되는 공리계라고 생각하면 된다. 그런데 이 “페아노 공리계”를 포함하는 논리 체계에서 모든 참인 사실을 증명할 수 없으므로, 다시 말해 논리 체계가 불완전하므로, 불완성정 정리라는 이름을 붙인 것이다.

아무튼 불완정성 정리로 힐베르트를 위시한 수많은 수학자들이 꿈꾸던 완벽한 논리 체계라는 꿈은 산산조각났다. 힐베르트가 상상하던 기계는 당연히 정해진 논리 체계를 기반으로 돌아가야 하는데, 애초에 그 논리 체계부터가 불완전할 수밖에 없다는 사실이 증명된 것이다. 그리고 괴델이 만들어낸 이 위대한 업적은 5년 후 튜링에 의해 살짝 변형되어 인류에 엄청난 변화를 만들어내는 시발점이 되었다.

괴델보다 여섯 살 어린 튜링은 1935년 케임브리지 대학에서 막스 뉴먼 (Max Newman) 에게 괴델의 불완전성 정리와 관련된 강의를 듣게 된다. 아마 그는 그 강의에서 큰 감명을 받은 것 같다. 그는 불완정성 정리를 자신만의 방법으로 증명해 1936년 박사 학위 논문으로 발표했는데, 힐베르트가 말한 기계라는 단어에 더욱 초점을 맞춘 증명이었다. 그 증명 과정을 아주 간략하게 설명하자면 다음과 같다.

  1. 자동 기계장치를 정의한다.
  2. 우리가 상상할 수 있는 모든 기계장치는 그 정의대로 만들어질 수 있다고 설명한다.
  3. 그 기계가 풀 수 없는 문제가 있음을 증명한다.

도대체 튜링은 이 기계를 어떻게 정의한 것일까? 그리고 왜 그렇게 정의했을까? 튜링은 아마 기계의 설계와 관련해서 괴델로부터 많은 통찰을 얻었을 것이다. 괴델의 증명의 근간을 이루는 “증명불가능하지만 참인 사실”은 무한이라는 개념과 밀접하게 연관되어 있다. 튜링은 자신이 정의하려는 기계와 무한을 연관시키려고 노력했다. 다시 말해, 기계와 관련해서 무한한 것이 무엇인지 고민했다. 그리고 그는 기계의 실행은 무한할 수 있음을 생각해 냈다. 기계는 유한하지만, 이는 물리적인 한계 때문이다. 기계가 마모되거나 낡지 않는 가상 공간에 똑같은 행동을 영원히 반복하는 기계를 만든다면, 분명 그 기계는 영원히 돌아간다고 이야기 할 수 있다.

괴델이 무한과 관련해 증명할 수 없는 명제를 찾아낸 것처럼, 튜링 역시 무한한 기계의 실행과 관련해 기계가 풀 수 없는 문제를 찾으려 했다. 그는 아마 이렇게 생각하지 않았을까. “기계가 다른 기계의 무한한 실행을 어떻게 판단하지? 그러기 위해서는 어떠한 기계의 작동을 글로 적어서 다른 기계가 읽게 할 수 있으면 되지 않을까?”. 그는 단순한 부품들로 구성되었지만 상상할 수 있는 모든 계산이 가능한 가상의 기계를 정의했다. 그리고 이 정의를 따라 만들어진 어떤 특정한 행동을 하는 기계에 대해 글로 적어 넣으면 그 기계의 행동을 따라할 수 있는 기계 - 보편 기계 (Universal Machine) - 를 설계했다. 물론 이 보편 기계 역시 튜링의 정의를 따라 구현할 수 있다.

여기까지 내용을 다시 정리하자면, 튜링은 상상할 수 있는 모든 기계장치를 커버하는 기계의 정의내리고, 이 기계를 입력받을 수 있는 기계를 설계했다. 그리고 이런 이론적 바탕 위에서 그는 다른 기계를 입력으로 받아 그 기계가 영원히 동작할지 아니면 멈출지 판단하는 기계를 만드는 것은 불가능하다 는 것을 증명했다. 그만의 방법으로 힐베르트의 결정문제를 증명하는 데 성공한 것이다.

보편 기계와 컴퓨터

튜링이 위 증명을 위해 정의한 가상 기계를 사람들은 튜링 기계 (Turing machine)이라고 부른다. 그리고 지금 존재하는 모든 컴퓨터의 구조는 튜링 기계를 기반으로 하고 있다. 정확히 말하자면 보편 튜링 기계를 기반으로 한다. 보편 튜링 기계는 다른 기계의 행동을 입력으로 받아 그 기계의 행동을 따라할 수 있다. 여기서 “다른 기계”를 소프트웨어, “보편 튜링 기계”를 이를 실행하는 하드웨어, 즉 컴퓨터라고 하면 지금 우리가 쓰는 컴퓨터와 정확히 대응한다.

튜링 이후의 수학자들과 전산학자들은 튜링 기계라는 이론적 토대 위에서 컴퓨터의 구조를 설계했고, 1950년대 존 폰 노이만 (John von Neumann) 이 설계한 폰 노이만 구조는 아직까지도 바뀌지 않고 모든 컴퓨터에서 쓰이고 있다. 결국 지금 컴퓨터를 쓰는 우리 모두는 튜링의 박사 논문에게 빚을 지고 있는 것이다.

다양한 오토마타, 그리고 형식언어

튜링은 그가 정의내린 기계로 상상할 수 있는 모든 계산을 할 수 있다고 이야기했다. 그렇다면 상상할 수 있는 모든 계산을 할 수 없는 기계도 있지 않을까? 당연히 그렇다. 사람들은 계속해서 다양한 가상 기계들을 설계해 왔고, 이들을 오토마타라고 불렀다. 유한 오토마타 (Finite Automata), 푸쉬다운 오토마타 (Pushdown Automata) 등이 대표적인데, 이들은 튜링 머신보다 약한 계산 능력을 가졌고 풀 수 있는 문제의 범위가 작다.

다양한 오토마타와 풀 수 있는 문제의 범위. 튜링 머신이 가장 강려크하다

또한 각각의 오토마타로 풀 수 있는 문제의 범위를 형식 언어의 형태로 정의하기도 하는데, 형식 언어를 통해 우리는 애매모호함 없이 각 오토마타의 능력을 파악할 수 있다. 쉽게 말해 이런 것이다: 푸쉬다운 오토마타로는 어떤 특정한 문자열 집합 A를 생성할 수 없지만, 튜링 머신으로는 생성할 수 있다. 언어학자이자 철학자 노엄 촘스키(Noam Chomsky) 는 형식 언어들을 촘스키 계층이라는 이름으로 분류했는데, 촘스키 계층의 각 단계는 각각의 오토마타와 대응된다.

이 과목에서는 이러한 다양한 오토마타와 형식언어들을, 가장 간단한 것부터 튜링 머신까지 배운다. 이를 통해 학생들은 컴퓨터와 컴퓨팅 이론이 어떻게 발전했는지 배우게 되고, 계산 이론의 한 갈래인 계산가능성(Computability) 이론을 접하게 된다. 계산가능성 이론은 그냥 지금까지 설명한 내용에 대한 것이다. 어떤 특정한 오토마타가 어떤 문제는 계산 가능하고, 또 더 어려운 문제는 계산 불가능하고, 뭐 이러한 성질들을 연구하는 분야다.

쓰다 보니 단 한 과목을 소개하는데도 분량이 넘쳐버렸는데, 그만큼 이 과목이 중요함을 방증한다. 내가 무엇인가 공부하면서 처음으로 경외감을 느꼈던 것도 오토마타와 계산가능성 이론을 공부하면서였다. 사실 컴퓨터공학/과학과의 커리큘럼은 대부분 응용에 맞춰져 있고, 나 역시 지금 응용분야를 연구하고 있다 (이는 계산이론과 같은 순수 컴퓨터과학의 영역을 수학자들이 상당 부분 해결하기 있기 때문이기도 하다). 그럼에도 컴퓨터를 공부했다는 사람이 컴퓨터의 역사를 모른다는 것은 어불성설이고, 응용 분야에 종사하더라도 기초를 탄탄히 한 사람과 그렇지 않은 사람의 차이는 굉장히 클 것이다. 이 과목이 대부분의 학교에서 전공필수로 포함되어 있는 것도 그래서이지 않을까 싶다.

하편에서는…

어쩌다 보니 글이 길어졌다. 하편에서는 계산가능성 이론의 또다른 갈래이자 “소프트웨어”의 이론적 토대를 만든 프로그래밍 언어론. 그리고 마지막으로 컴퓨터를 어떻게 효율적으로 쓸지 알려주는 알고리즘과 자료구조에 대해 이야기하겠다.

관련 포스팅

컴퓨터를 전공한다는 것 1편 - 컴퓨터 시스템

컴퓨터를 전공한다는 것 2편 - 프로그래밍과 개발방법론

컴퓨터를 전공한다는 것 3편 - 계산이론 (하)

참고문헌

출처:

  1. 튜링의 1935년. 이광근. https://ropas.snu.ac.kr/~kwang/memo/turing1935.pdf
  2. Wikipedia. Max Newman. https://en.wikipedia.org/wiki/Max_Newman#Early_academic_career
  3. Wikipedia. Alan Turing. https://en.wikipedia.org/wiki/Alan_Turing