다시 김도형의 홈 페이지로
`전자계산일반' 수강생 여러분, 안녕하십니까? 제2주 강의를 시작하겠습니다. 이번 주 강의의 주제는 컴퓨터를 이용해서 풀 수 있는 문제의 범위가 어디까지인가 하는 것입니다.
요즘은 우리나라에서도 웬만한 경우에는 거의 모든 사람들이 스스로 원하기만 한다면 컴퓨터에 쉽게 접근할 수 있는 환경이 구축되고 있고, 사회적으로는 마치 컴퓨터를 모르면 당장 낙오자로 도태할 것 같은 분위기가 팽배해 있습니다. 컴퓨터에 대한 관심이 계속 높아가는 이 때에, 공상 소설의 관점이 아니라 과학적인 관점에서 컴퓨터의 능력과 가능성을 고찰해 보는 일은 중요하다고 생각됩니다.
컴퓨터는 세상의 모든 문제를 풀 수 있다고 생각하십니까? 아마도 당장 부정적인 대답이 돌아올 법 합니다. 그렇습니다. 우리가 일상 생활에서 끊임없이 만나는 정서적 문제가 컴퓨터에 의해 해결될 수 있으리라고는 생각되지 않습니다. (설령 먼 미래라고 하더라도 말이죠.)
그러면 문제의 정의를 다소 제한해 봅시다. 수학적으로 엄밀히 기술되는 문제들은 예외없이 컴퓨터에 의해 풀 수 있을까요? 질문이 이렇게 되면 앞서의 질문보다는 대답하기가 훨씬 신중해질 것 같습니다. ^^
답을 말씀드리지요. "풀 수 없습니다!" 이러한 결론이 내려지기까지의 역사를 살펴보는 것이 아마 도움이 될 것입니다.
컴퓨터 능력의 한계에 관한 많은 연구 결과는 20세기초에 수리논리학(mathematical logics) 분야에서 수행된 것입니다. 따라서 우리가 지금 사용하는 컴퓨터의 능력은 컴퓨터가 발명되기 전부터 충분히 예견되고 있었습니다.
20세기가 시작될 무렵, 수학자 Hilbert는 어떤 수학적인 명제가 입력으로 주어질 때 이의 참과 거짓을 알아내는 알고리즘을 찾고자 하는 일종의 `수학 자동화' 연구를 시작하였습니다. 그후 1931년에 이 방면의 연구에서의 금자탑이라고 할 수 있는 쿠르트 괴델(Kurt Godel)의 논문이 발표되었습니다. 즉 그러한 알고리즘은 존재할 수 없음을 증명한 유명한 `불완전성 정리(Incompleteness Theorem)'를 발표한 것입니다. 그의 결과를 간단하게 설명하면, 모든 수학적인 논리 체계에는 그 논리 자체로써는 증명할 수 없는 참인 명제들이 존재한다는 것입니다.
이렇게 일단 풀 수 없는 문제가 존재함이 증명된 후 많은 학자들은 풀 수 있는 문제들에 대한 연구에 몰두하여 여러가지 계산 모델들을 제안하였습니다. 그 예들로는 클레이너(Kleene)가 시작하고 쳐치(Church)가 많이 공헌한 순환함수론(Recursive Function Theory), 역시 쳐치의 람다 산술(Lambda Calculus), 포스트(Post)의 포스트 시스템(Post System), 또 마코프(Markov)의 마코프 알고리즘(Markov Algorithm), 그리고 전산학도들에게 가장 친숙한 앨런 튜링(Alan Turing)의 튜링 기계(Turing Machine) 등이 있습니다.
한마디로 하면 이러한 것들은, `풀 수 있는 문제' 혹은 `알고리즘을 만들어 낼 수 있는 문제' 또는 `컴퓨터를 이용하여 풀 수 있는 문제'의 계산 모델들 중 하나입니다.
이 제안된 계산 모델들은 풀 수 있는 문제의 범위를 결정하는 목적으로 이용되었습니다. (이런 시도는 대개 1935년을 전후하여 된 것으로, 현대적인 컴퓨터가 발명되기 이전에 이미 사람들은 알고리즘으로 풀 수 있는 문제들에 관심을 기울인 것입니다.)
서로 다르게 정의되어 성능면에서도 차이가 있을 걸로 생각되는 여러가지 모델들이 실제로는 계산 능력면에서 동등함이 밝혀졌으며, 이에 근거하여 이 모델들에 의해서 계산될 수 있는 문제들이 바로 알고리즘을 이용하여 풀 수 있는 문제들과 정확히 일치할 것이라는 가정이 있는데, 이를 `쳐치-튜링 논제(Church-Turing Thesis)'라고 합니다. (이 가정은 아직 증명되지 않고 있지만 옳을거라는 심증이 아주 강하기 때문에 가정(conjecture)이라 하지 않고 논제(thesis)라고 합니다.)
전산학과의 교과 과정에서 앞서 언급된 여러 가지 다른 모델들은 제쳐두고 튜링 기계를 특히 중점적으로 언급하는 것은 그것이 현대의 범용 컴퓨터의 이상적인 추상적 모형이기 때문입니다. 어떤 현대의 컴퓨터이든지 튜링 기계의 한 특수한 경우라고 할 수 있지요. 또 현대 컴퓨터 내부에서 이루어지는 계산(computation)과 그 수행은 튜링 기계 내부에서의 동작으로 수학적 모형화시키는 것이 가능합니다. 따라서 어느 문제가 튜링 기계로 해결할 수 없음을 보임으로써 그 문제는 어떤 알고리즘 기계로도, 즉 현대의 최신형 컴퓨터로도 해결할 수 없음을 보여줄 수 있지요.
전산학계는 튜링의 이러한 업적을 기념하여 미국전산학회에서 하나의 상을 제정하여 시상하고 있습니다. 이 상은 `전산학 분야의 노벨상'이라고 불릴만한데, 다름아닌 바로 `튜링 상(Turing Award)'입니다.
다시 김도형의 홈 페이지로