알고리즘이라는 말은 일상에서 흔히 접할 수 있다. 미디어에서 알고리즘의 대명사처럼 언급되는 유튜브의 추천 알고리즘은 사용자의 시청 이력과 선호도를 기반으로 수많은 콘텐츠 가운데 사용자가 관심 있어 할 영상을 제안하는 데 활용된다. 이를 통해 유튜브는 사용자가 더 오랫동안 영상을 시청하도록 유도함으로써 큰 성공을 거두고 있다. 유튜브의 사례는 오늘날 알고리즘의 역할과 상업적 가치를 잘 보여준다.
알고리즘은 컴퓨터 과학의 핵심적인 개념이지만 꼭 그에 국한되는 것은 아니다. 사전적으로 이는 어떤 문제를 해결하거나 목표를 달성하기 위한 일련의 절차를 의미한다. 라면을 끓이는 방법이나 옷을 입는 순서 역시 알고리즘으로 이해할 수 있다. 다만 이러한 과정들이 너무나 익숙하고 자연스러워 특별한 알고리즘이라고 인식하기 어려울 뿐이다.
20세기 영국의 수학자인 앨런 튜링은 알고리즘의 개념에 대한 역사에서 가장 중요하면서도 흥미로운 인물이라 할 수 있다. 그는 영화 '이미테이션 게임'을 통해 대중들에게도 비교적 널리 알려져 있다. 영화는 주로 1940년대 제2차 세계 대전 중 연합군의 암호해독 작업에서 튜링의 활약상을 그리고 있지만, 튜링이 수학계에 등장하는 시기는 그보다 이전인 1930년대 중반이다.
당시 독일의 저명한 수학자 힐베르트는 수리논리학이라는 분야에서 몇 가지 중요한 질문을 던졌다. 수학을 하나의 게임이라고 생각하면, 수리논리학은 이 게임의 규칙에 대해 다룬다고 볼 수 있다. 축구 선수가 규칙을 익히는데 훈련 시간을 할애하지 않듯이, 수학자들도 이 분야에 대개는 별 관심을 두지 않는다.
힐베르트는 수학이라는 게임의 본질이 공리에서 시작하여 추론규칙을 적용하여 새로운 옳은 명제를 끌어내는 것이라고 생각했다. 튜링이 관심을 가진 힐베르트의 질문은 주어진 명제가 공리와 추론규칙만을 사용하여 증명 가능한지를 판별하는 일반적인 절차, 즉 알고리즘이 존재하는지에 대한 것이었다. 증명이 가능한 명제도 있고, 그렇지 않은 명제도 있는 가운데 그들을 구분해 낼 보편적인 방법을 묻는 것이었다.
1936년 튜링은 이 질문에 대한 답을 담은 논문을 발표했다. 그의 결론은 그런 알고리즘은 존재하지 않는다는 것이었다. 이 결과는 수리논리학이라는 수학자들조차 쓸모없다고 생각하는 분야의 불가능성 정리, 즉 무언가를 할 수 없다는 결론을 담은 정리에 해당한다. 그러니 그 결론의 실제적인 쓸모를 찾기는 어렵다고 할 수 있다.
그러나 논문에 부정적인 것만이 들어있는 것은 아니었다. 가능한 모든 알고리즘을 다 검토해도 안 된다는 결론을 내리려면 알고리즘이라는 것의 범주를 수학적으로 명확히 할 수 있어야 한다. 이것이 바로 힐베르트의 질문에 숨겨져 있던 또 다른 심오한 질문이었다.
튜링은 논문에서 마치 사람이 연필과 지우개를 들고 노트를 넘기면서 계산을 하는 듯한 모습을 닮은 가상의 기계를 수학적으로 정의한다. 실제 기계가 아니라 논문 속의 추상적 개념인 이 기계는 명시적으로 기술된 절차를 실행하는 기계였다. 이 정의를 통해 계산과 알고리즘 같은 개념이 일상어 수준을 넘어 엄밀한 학문적 개념으로 변신했다.
이러한 것들은 당시에 지구상에서 얼마 안되는 소수의 사람들만이 고민하던 순수한 수리논리의 문제였다. 그러나 오늘날 튜링 머신이라 불리는 논문 속 가상의 기계는 머지않아 현실에서 실제 기계가 탄생하는데 영향을 끼치게 된다. 그 기계가 바로 컴퓨터이고, 튜링의 논문은 컴퓨터 과학이라는 새로운 분야를 탄생시켰다.
이철희 고등과학원 수학난제연구센터 연구원
ⓒ 맛있는 뉴스토마토, 무단 전재 - 재배포 금지