튜링상을 아시나요?

매년 가을, 노벨상 수상자가 발표되는 때가 되면 대한민국은  몸살을 앓는다. 우리는 왜 노벨상을 받지 못하느냐는 핀잔이다. 누구를 향한 핀잔인지 모를 수많은 기사들이 하루 이틀 시끄럽다가 잠잠해지고 만다. 내가 노벨상이라는 것을 알고 난 뒤, 오늘날까지 끝없이 반복되는 연례행사이다. 과학분야 중에 물리학, 화학분야, 그리고 생리 의학분야에 주어지는 상이다. 알고 있듯이 비과학 분야로 경제학상과 평화상이 있다. 

우리나라에서는 주로 컴퓨터공학이라고 더 알려진 컴퓨터 관련 학문은 국내에 도입되면서 여러 형태로 뿌리를 내렸다. 컴퓨터과학은 유럽에서는 정보학(informatics)으로 미국에서는 컴퓨터과학(computer science)으로서 학문의 뿌리를 내렸다. 물론 전자공학에서도 세부분야로 컴퓨터공학으로 분리하여 세분화되어 있기도 하다. 이제는 국제적으로 컴퓨터학(computer science and engineering)으로 통일되어 가는 모양새이고 좀 더 진화된 형태로 분야가 더 다양하고 더 세분화되어 간다. 그 중심에 컴퓨터과학이라는 핵심어가 들어 있다. 과학의 꽃은 물리학이요, 물리학의 근간은 수학이다. 수학분야도 노벨상은 없지만 예전의 필즈상, 요즘에는 평생 업적을 기리는 아벨상이 '수학의 노벨상'이라는 위엄을 갖추고 있다. 컴퓨터 과학도 과학의 한 분야인데, 이 분야의 노벨상과 같은 권위 있는 상이 없을까?

컴퓨터과학 분야에서 가장 권위 있는 상은 튜링상(Turing Award)이다. 튜링상은  컴퓨터 기계 학회, ACM(Associate of Computing Machinery)이 해마다 컴퓨터 분야에 업적을 남긴 사람에 시상하는 상이다. 이 상은 컴퓨터과학의 노벨상이라고도 불린다. 영국의 수학자, 논리학자, 암호학자였던 앨런 튜링은 컴퓨터과학의 아버지라고 부른다. 그가 컴퓨터과학자가 아닌 수학자였다. 그러나 그의 연구가 현대 디지털 컴퓨터의 기본원리를 제시했다. 그는 컴퓨터 과학의 선구적 인물이며 알고리즘과 계산 개념을 튜링 기계(Turing Machine)라는 추상 모델을 통해 형식화하여 컴퓨터 과학의 발전에 지대한 공헌을 했다. 그의 공덕을 기리어 튜링상이라고 한다.

1966년부터 수여한 튜링상은 54년 동안 71명에게 주어졌으며, 2인 공동수상 12회 3인 공동수상 3회, 38회의 단독 수상이었다. 요즘 뜨거운 사회적 관심사가 되고 있는 인공지능, 그중에서 딥러닝에 기여한 3명의 학자가 2018년도에 이 상을 받았다. 힌턴, 벤지오, 러쿤 교수이다. 그리고 작년 2020년 수상자는 제프리 울먼 스탠퍼드대 명예교수와 알프레드 에이호 컬럼비아대 교수가 받았다. 두 사람에게 주어진 상금은 100만 달러, 한화로 약 11억이 주어졌다.

이 중에 울먼 교수의 제자 두 명이 1997년 검색엔지는 개발했다. 이에 울먼 교수는 두 학생의 창업을 독려했고 실패하면 언제든지 돌아와 박사과정 마쳐도 된다고 했다. 실패할 용기를 준 것이다. 세르게이 브린과 래리 페이지라는 이름의 이 학생들은 스타트업 '구글'을 창업한 학생들이었다. 이 기업은 알다시피 세계 최대의 기업, 최고의 기업이 되었다.

1912년 런던에서 태어난 튜링은 어려서부터 총명하여 읽기를 3주 만에 배우는가 하면 계산과 퍼즐에 뛰어났다고 한다. 영국 케임브리지 대학교에서 공부하고 미국 프린스턴 대학교에서 박사 후 과정으로 연구를 하였다. 영국으로 돌아온 튜링은 대학에서 연구하면서 튜링 기계의 개념을 발표했다. 튜링 기계는 일종의 기계로 계산하는 시뮬레이션 모델이라고 할 수 있다. 그는 암호학에도 뛰어난 능력을 가지고 있었으며 세계 2차 대전 당시 독일군의 암호를 풀어 연합군의 승리에 기여를 했다. 그가 대학에서 연구를 할 때, 당시 수학계에서 관심이 있던 연구주제가 있었다.

앨런 튜링(1912-1954)

1928년 독일의 수학자 데이비드 힐베르트(David Hilbert)는 많은 수학적 문제들에 대해 명제들을 찾고 또한 그것들을 기계적인 방법으로 증명할 수 있을까 하는 의문을 제시했다. 독일의 빈대학에서 수학했지만 세계 2차 대전의 탄압을 피해 미국으로 건너간 수학자였던 쿠르트 괴델(Kurt Godel)은 이것이 불가능하다는 것을 증명했다. 1931년에 발표된 유명한 괴델의 불완전성의 원리이다. 한마디로 '기계적인 방식으로는 수학의 모든 사실들을 만들어 낼 수 없다'라는 것을 증명했다. 당시 유럽 수학계가 수학이 모든 사실을 만들어 낼 수 있다는 생각을 가졌는데 이와 같은 일련의 연구들은 실망감을 안겨 주었다. 하지만 여기서 말한 '기계적인 방식'에 대한 구체적인 예를 가지고 발표한 연구가 있었고 이 '기계적 방식'에서 보여준 모델이 오늘날의 컴퓨터의 뿌리가 되었다. 튜링이 박사학위를 마치고 미국으로 건너가기 전에 발표한 논문에서, 이 '기계적인 방식'을 구현한 '기계부품'을 정의했다. 이것이 '튜링 기계(Turing Machine)'이라는 수학원리로 구성된 '가상 기계'이다.  이 기계로 주어진 문제에서 답을 정할 수 없는 것을 보인다. 괴델의 불완전성을 이 기계로 증명한 것이다.

쿠르트 괴델(1906-1978)

튜링기계는 다섯 개의 부품으로 이루어져 있다. 이 부품들로 만들어진 기계들로 돌릴 수 있는 것만을 '기계적인 방식'이라고 정의한다. 이 방식으로 절대 돌릴 수 없는 계산문제 하나를 보인다. 그 계산 문제는 답이 참인지 거짓인지 아무도 알 수 없다. 이를 통해 기계적인 방식으로 참인 사실을 모조리 만들어 낼 수 있는 것이 아니라는 결론을 보여준다.

이제 그 부품에 대해 알아보자. 그것은 무한히 많은 칸을 가진 테이프, 테이프에 기록괴는 기호들(a, b, c 등 유한 개), 테이프에 기록된 기호를 읽거나 쓰는 장치, 그 장치의 상태들(S1, S2,... 등 유한 개), 기계의 작동 규칙표이고 기계마다 이 다섯 가지 부품이 구체적으로 정해진다. 기계의 작동 규칙은 다음과 같다. 우선 몇 개의 기호들을 테이프에 읽고 쓰게 될 것인지, 장치의 상태들이 몇 개가 되는지, 작동 규칙표는 무엇인지, 테이프에 시작 모습과 읽고 쓰는 장치의 시작 상태, 테이프의 시작 위치가 정해진다. 이렇게 정의된 기계가 작동 규칙표에 정의돼 있는 규칙대로 작동하면서 정해진 계산을 진행하게 되는 것이다. 실제로 이들의 움직임은 오토마타라 하고 쉽게 말해서 손으로 따라가면서 실행시킬 수 있다. 그래서 '손퓨터'라 해도 무방할 것이다.

튜링기계(Turing Machine) 부품들

그럼 이를 활용해서 주어진 입력 문자열에서 'abc'라는 문자열을 찾는 기능을 설계해 보자. 즉 규칙표를 이와 같은 기능을 할 수 있도록 설계하는 것이다. 이를 프로그램이라고 한다.

주어진 입력 테이프에 주어진 문자열이 있다고 하고 상태는 초기상태 S0에서 문자열이 찾아지면 도달하는 상태 S$가 있다. 약속된 규칙표를 따라 다음 상태를 따라가면 'abc'라는 문자열을 있으면 상태 S$에 도달한다. 그림에서 보면 처음 a를 읽으면 초기상태 S0에서 S1으로 이동한다. S1에서 다시 문자 a를 읽으면 계속 S1에 머문다. 그리고 문자 b를 읽으면 상태 S2로 이동한다. S2에서 문자 c를 읽으면 문자열을 찾은 상태 S$로 간다. 이 의미는 찾고자 하는 'abc'문자열을 찾았다는 의미이다. 그리고 다시 문자열이 계속되면 초기상태로 가서 문자열을 찾는 작업을 계속 진행하게 된다.

문자열 'abc' 찾는 튜링기계 규칙표

이를 수행하는 오토마타 다이어그램을 그려보면 다음과 같다.

문자열 'abc' 찾는 오토마타

이 기계적인 방식의 계산도구는 튜링이 암호 문제를 풀 때 만든 계산기로 활용되었고 오늘날 디지털 컴퓨터를 만든 때 원리로 활용하였다. 이 튜링기계에서 한문자를 읽고 처리하는 것을 명령어라고 한다. 오늘날 디지털 컴퓨터에서는 1초당 몇 개의 명령어를 처리하는지(IPS, Instruction Per Second)를 나타내는데, 속도가 점점 빨라져서, MIPS(밉스, million instructions per second)라는 단위를 사용한다. 즉 초당 100만 개의 명령을 수행할 수 있는 능력을 말한다. 2016년도에 시장에 나온 인텔에서 만든 프로세서가 317,900 밉스(MIPS)이다. 일초에 317,900 x 100만 개의 명령어를 처리할 있는 속도다. 위와 같은 규칙표가 주어지고 현대 프로세서가 가지는 속도만 가진다면 웬만큼 긴 규칙도 순식간에 해치울 것이다. 

'현대 컴퓨터가 할 수 있는 일은 튜링기계도 할 수 있다'라고 말한다. 튜링기계의 의미와 가치를 말해주는 명제다.