앨런 튜링(Alan Turing)

앨런 튜링은 1912년 런던에서 태어나 1931년 케임브리지 킹스 칼리지에 들어갔습니다. 그 무렵 수학의 기초⁠(basics)⁠는 흔들리고 있었습니다. 1928년 힐베르트는 논리식(정확히는 1차 논리⁠(first-order logic)⁠의 식)이 주어지면 그것이 증명되는지를 기계적으로 가려내는 방법이 있느냐는 '결정 문제'를 내놓았고, 1931년 괴델은 모순이 없고 자연수⁠(natural number)⁠의 셈을 담을 만큼 강한 형식 체계⁠(formal system)⁠에는 참이지만 그 체계 안에서 증명할 수 없는 명제가 있음을 보였습니다(불완전성 정리⁠(incompleteness theorem)⁠). 남은 것은 '기계적인 방법'이라는 말 자체였습니다. 이 말에 정확한 뜻을 준 사람이 스물세 살의 튜링이었고, 그 정의는 오늘날 어떤 컴퓨터가 원리상 무엇을 계산할 수 있고 무엇을 계산할 수 없는지를 가르는 기준이 되었습니다.

나이 세 ·

그의 아버지는 인도 행정청의 관리였고, 부모가 인도에 머무는 동안 튜링은 형과 함께 영국의 위탁 가정에서 자랐습니다. 1926년 도싯의 셔본 학교에 입학하던 날은 마침 총파업으로 기차가 멈춘 때라, 열세 살의 그는 100킬로미터 가까운 길을 자전거로 달려 학교에 갔습니다. 고전 교육을 중시하던 학교는 과학에만 빠진 이 학생을 걱정했지만, 그는 한 학년 위의 크리스토퍼 모컴과 천문학과 화학을 함께 공부하며 처음으로 마음이 통하는 친구를 얻었습니다. 1930년 2월 모컴이 결핵으로 갑자기 세상을 떠나자 튜링은 마음이 몸과 어떻게 이어져 있는지를 오래 붙들고 생각했고, 그런 생각을 적은 글을 모컴의 어머니에게 보내기도 했습니다. 기계가 생각할 수 있느냐는 훗날의 물음은 이 무렵의 물음과 멀지 않습니다.

그가 들어간 1930년대의 케임브리지는 20여 년 전 러셀과 수학자이자 철학자 앨프리드 노스 화이트헤드가 『수학 원리』로 수학을 논리 위에 다시 세우려 한 곳이었고, G. H. 하디와 J. E. 리틀우드가 소수⁠(prime number)⁠의 분포를 미적분⁠(calculus)⁠과 복소수⁠(complex number)⁠ 함수⁠(function)⁠로 연구하는 해석적 정수론⁠(number theory)⁠을 이끌었으며, 킹스 칼리지에는 경제학자 존 메이너드 케인스가 있었습니다. 튜링은 1933년 천문학자 아서 에딩턴의 강의에서, 측정값들이 왜 종 모양의 분포로 모이는지에 관한 이야기를 듣고 그 까닭을 스스로 증명해 보기로 했다고 전합니다.

그는 먼저 확률론으로 실력을 보였습니다. 1934년 학부를 마치며 중심극한정리⁠(central limit theorem)⁠, 곧 서로 영향을 주지 않는 작은 우연들을 많이 더하면 그 합의 분포가 종 모양의 정규분포⁠(normal distribution)⁠에 가까워진다는 정리를 스스로 증명했는데, 핀란드의 수학자 야를 발데마르 린데베리가 1922년에 이미 증명한 결과였습니다. 그래도 논증의 독창성을 인정받아 1935년 스물두 살에 킹스 칼리지의 펠로가 되었습니다. 같은 해 봄 수학자 맥스 뉴먼의 수학 기초론 강의에서 결정 문제를 들은 튜링은 '기계적인 절차'라는 말을 글자 그대로 받아들였습니다. 출발점은 기계가 아니라 종이 위에서 계산하는 사람이었습니다. 그 사람이 하는 일을 끝까지 쪼개면 칸이 나뉜 테이프, 한 칸씩 읽고 쓰며 오가는 머리, 그리고 유한한 규칙표만 남습니다. 이것이 튜링 기계입니다.

1936년 논문 「계산 가능한 수⁠(computable number)⁠에 대하여, 결정 문제에의 응용과 함께」에는 세 가지 발견이 들어 있었습니다. 첫째, 규칙표도 기호의 나열이니 테이프에 적을 수 있고, 따라서 다른 기계의 규칙표를 읽어 그 기계가 할 일을 한 걸음씩 대신하는 보편 기계가 있습니다. 기계마다 따로 배선하지 않고 프로그램을 바꿔 넣는다는 컴퓨터의 생각입니다. 둘째, 기계는 유한한 규칙표로 적히니 자연수로 번호를 붙일 수 있을 만큼, 곧 셀 수 있을 만큼만 있고, 그래서 기계가 소수점 아래 자릿수를 하나씩 계속 적어 낼 수 있는 실수(계산 가능한 수)도 셀 수 있을 만큼뿐입니다. 실수⁠(real number)⁠ 전체는 셀 수 없을 만큼 많으니, 대부분의 실수는 어떤 기계로도 계산할 수 없습니다. 셋째, 칸토어의 대각선 논법⁠(diagonal argument)⁠을 기계들의 목록에 적용하면, 임의의 기계를 받아 그 기계의 행동을 미리 판정해 주는 기계는 있을 수 없습니다. 튜링 자신은 '이 기계가 숫자를 끝없이 적어 내는가'를 물었고, 오늘날 '언젠가 멈추는가'로 적는 정지 문제⁠(halting problem)⁠는 1950년대에 다듬어진 같은 논증의 모양입니다. 이 사실을 논리식으로 옮기면 결정 문제의 답은 '아니오'입니다.

같은 무렵 프린스턴의 논리학자 알론조 처치가 함수를 만들고 적용하는 규칙만으로 계산을 적는 체계인 람다 계산⁠(lambda calculus)⁠으로 같은 답을 조금 먼저 냈고, 튜링은 자기 기계로 계산할 수 있는 것과 람다 계산으로 정의할 수 있는 것이 정확히 같다는 부록을 붙였습니다. 겉모습이 전혀 다른 정의들이 한곳에 모이자, 이것이 '계산할 수 있음'의 올바른 뜻이라는 처치–튜링 논제⁠(Church–Turing thesis)⁠가 받아들여졌습니다. 처치 쪽 정의에 회의적이던 괴델도 튜링의 분석은 설득력 있다고 여겼습니다. 튜링은 1936년 가을 프린스턴으로 건너가 처치 밑에서 박사 학위를 받았고, 폰 노이만이 권한 조수 자리를 사양하고 1938년 여름 영국으로 돌아왔습니다.

논문은 처음에는 많이 읽히지 않았습니다. 그래도 처치는 1937년 서평에서 '튜링 기계'라는 이름을 처음 썼고, 뉴욕의 논리학자 에밀 포스트도 1936년 거의 같은 기계 모형을 따로 내놓았습니다. 그가 머문 프린스턴에서는 대학의 수학과와 막 생긴 고등연구소가 한 건물을 함께 쓰고 있었고, 폰 노이만은 이 논문을 눈여겨본 사람의 하나였습니다. 로스앨러모스에서 일한 물리학자 스탠리 프랭클은 뒤에, 폰 노이만이 1943–44년 무렵 자기에게 이 논문을 꼼꼼히 읽으라고 권하며 그 근본적인 중요성을 강조했다고 회고했습니다. 프린스턴에서 쓴 박사 논문 「서수⁠(ordinal)⁠에 기초한 논리 체계」(1938)에서 튜링은 한 체계로 증명할 수 없는 참을 새 공리⁠(axiom)⁠로 더해 가는 탑을 쌓고, 그 탑의 층에 무한을 넘어서도 이어지는 순서 번호인 서수를 붙였습니다. 또 정지 문제처럼 기계로 풀 수 없는 물음에 답을 알려 주는 가상의 '신탁'을 가진 기계를 도입했습니다. 이 신탁 기계⁠(oracle machine)⁠는 문제들의 어려움을 서로 견주는 상대적 계산 가능성⁠(relative computability)⁠ 이론의 출발점이 되었습니다.

케임브리지로 돌아온 튜링은 1939년 초 철학자 루트비히 비트겐슈타인의 수학 기초론 강의에 참석해, 모순이 있는 체계가 왜 문제인지를 두고 그와 맞섰습니다. 그러는 사이 전쟁이 다가왔습니다. 영국 정부의 암호 학교는 런던 북쪽 버킹엄셔의 시골 저택 블레츨리 파크로 옮겼고, 튜링은 1938년부터 그 일을 일부 거들다가 영국이 독일에 선전 포고한 이튿날인 1939년 9월 4일 정식으로 합류했습니다. 출발점은 폴란드였습니다. 1932년 말 폴란드의 수학자 마리안 레예프스키는 순열⁠(permutation)⁠의 수학으로, 글자를 칠 때마다 돌아가는 배선 바퀴(회전자)로 글자를 뒤섞는 독일 군용 암호 기계 에니그마의 배선을 알아냈고, 동료들과 함께 설정을 찾는 기계 '봄바'를 만들었습니다. 1939년 7월 바르샤바 근교에서 폴란드 암호국은 이 성과를 영국과 프랑스에 넘겨주었습니다. 블레츨리에는 수학자뿐 아니라 언어학자, 체스 선수, 십자말풀이 명수가 모였고, 전쟁 막바지에는 일하는 사람이 1만 명 가까이 되었는데 그 4분의 3쯤이 여성이었습니다.

블레츨리에서 튜링은 폴란드 수학자들의 앞선 성과를 이어받아, 암호문⁠(ciphertext)⁠ 속에 들어 있으리라 짐작되는 평문⁠(plaintext)⁠ 조각과 모순되는 에니그마 설정을 기계적으로 지워 나가는 봄베⁠(bombe)⁠를 설계했습니다. 첫 봄베 '빅토리'는 1940년 3월에 설치되었고, 동료 고든 웰치먼이 더한 '대각선 판'이 탐색을 크게 줄였습니다. 튜링은 가장 어렵다던 독일 해군의 에니그마를 맡은 8호 막사를 이끌었습니다. 그가 고안한 '밴버리즘⁠(Banburismus)⁠'이라는 절차에는 베이즈 정리⁠(Bayes' theorem)⁠가 숨어 있습니다. 두 가설(이를테면 '이 두 전문은 같은 설정으로 암호화되었다'와 '아니다')을 견줄 때, 증거 하나는 두 가설의 승산을 가능도⁠(likelihood)⁠비만큼 곱합니다. 가능도비⁠(likelihood ratio)⁠는 그 증거가 첫 가설 아래에서 나올 확률⁠(probability)⁠을 둘째 가설 아래에서 나올 확률로 나눈 값입니다. 튜링은 이 배수⁠(multiple)⁠들을 곱해 나가는 대신 그 상용로그를 더해 나갔습니다. 배수 10을 1'반(ban)', 로그로 그 10분의 1인 배수 $10^{0.1} \approx 1.26$을 1'데시반⁠(deciban)⁠'이라 불렀습니다. 이를테면 가능도비가 2인 증거는 약 3데시반을 보탭니다. 점수가 문턱⁠(threshold)⁠을 넘으면 판정을 내렸습니다. 그의 통계⁠(statistics)⁠ 조수였던 I. J. 굿은 전쟁 뒤 이 생각을 '증거의 무게⁠(weight of evidence)⁠'라는 이름으로 정리했고, 증거 하나가 평균적으로 보태는 무게가 오늘날의 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠입니다.

1941년 10월 튜링과 웰치먼을 비롯한 해독 책임자 네 사람은 인력과 기계가 모자라 해독이 늦어지고 있다며 처칠 총리에게 직접 편지를 썼고, 처칠은 '오늘 당장 처리할 것(Action this day)'이라 적어 그들이 원하는 것을 최우선으로 모두 주라고 지시했습니다. 대서양에서 유보트의 위치를 읽어 내는 일이 수송 선단의 목숨을 좌우하던 때였습니다. 1942년 튜링은 독일 최고 사령부의 텔레프린터 암호('터니')를 손으로 푸는 방법을 내놓았고, 이 암호를 기계로 풀기 위해 우체국 연구소의 기술자 토미 플라워스가 진공관 1,600개짜리 기계 콜로서스⁠(Colossus)⁠를 지어 1944년 초부터 가동했습니다. 1942년 11월부터 이듬해 3월까지 튜링은 미국에 건너가 미 해군의 봄베 제작을 살피고 벨 연구소의 음성 암호 장치를 검토했으며, 돌아와서는 핸슬로프 파크에서 음성 암호기 '딜라일라'를 직접 설계했습니다. 1946년 전쟁 중의 공로로 대영 제국 훈장(OBE)을 받았지만 무슨 일을 했는지는 비밀이었고, 블레츨리의 이야기는 1970년대에 들어서야 세상에 알려지기 시작했습니다.

전쟁이 끝나자 그는 보편 기계⁠(universal machine)⁠를 실제로 짓고 싶었습니다. 1946년 초 테딩턴의 국립 물리 연구소에 프로그램을 기억 장치에 담는 컴퓨터 ACE의 상세한 설계를 냈지만 제작이 늦어졌고, 1948년 맨체스터 대학으로 옮겨 그곳의 초기 컴퓨터를 다루었습니다. 1949년 6월 케임브리지의 학회에서 발표한 세 쪽짜리 「큰 루틴 확인하기」에서는 프로그램의 몇 곳에 '여기서는 이것이 참'이라는 단언을 붙이고 끝남은 줄어드는 양으로 보이는 방법을 선보였는데, 이 발표는 오래 잊혔고 같은 생각이 20년 뒤 호어 논리⁠(Hoare logic)⁠로 다시 나왔습니다. 1950년 『마인드』에 실은 「계산 기계와 지능」은 "기계는 생각할 수 있는가?"라는 물음을, 글로만 대화하며 상대가 사람인지 기계인지 가려내는 모방 게임으로 바꾸어 물었습니다. 그는 50년쯤 뒤에는 보통의 질문자가 5분 동안 묻고도 70% 넘게 맞히지 못하게 되리라고 예측했습니다. 1952년 논문 「형태 발생⁠(morphogenesis)⁠의 화학적 기초」에서는 서로 반응하며 퍼지는 두 물질을 생각했습니다. 퍼짐만 있으면 열방정식⁠(heat equation)⁠처럼 고르게 섞일 것 같지만, 반응이 알맞은 모양이고 두 물질이 퍼지는 빠르기가 충분히 다르면 고른 상태가 오히려 불안정해져 점이나 줄무늬가 저절로 생길 수 있음을 보였습니다. 해바라기 씨앗의 배열에 피보나치 수가 나타나는 까닭도 연구했고, 마라톤을 2시간 46분에 뛴 수준급 장거리 주자이기도 했습니다.

이 시기의 그는 생각이 기계보다 늘 앞서 있었습니다. 1948년 국립 물리 연구소에 낸 보고서 「지능을 가진 기계」에서는 무작위로 이어진 단순한 소자들의 그물이 훈련을 거치며 쓸모 있는 기계가 되어 가는 '비조직 기계⁠(unorganized machine)⁠'를 그렸는데, 연구소장이 학생의 과제물 같다고 여겨 발표되지 않았고 1968년에야 출판되었습니다. 오늘날 신경망⁠(neural network)⁠의 먼 선구로 읽히는 글입니다. 같은 해 경제학자 데이비드 챔퍼나운과 체스 프로그램(게임 트리⁠(game tree)⁠ 탐색)을 짰지만 돌릴 컴퓨터가 없어서, 1952년 동료와 둔 대국에서는 튜링이 규칙표를 손으로 따라 계산하며 수를 두었습니다. 국립 물리 연구소의 작은 시험기 파일럿 ACE는 1950년 5월에야 처음 돌았고, 맨체스터에서 그는 1951년 나온 상업용 컴퓨터 페란티 마크 1의 프로그래밍 안내서를 썼습니다. 같은 해 왕립학회 회원으로 뽑혔습니다.

형태 발생 논문은 발표된 뒤 오래 생물학자들에게 거의 잊혀 있었습니다. 1990년 프랑스 보르도의 연구진이 화학 반응 속에서 두 물질의 확산 속도⁠(velocity)⁠ 차이로 저절로 생겨나는 점무늬를 실험으로 처음 뚜렷하게 확인했고, 그 뒤 '튜링 무늬⁠(Turing pattern)⁠'는 물고기의 줄무늬나 동물의 털 무늬, 손가락이 생겨나는 과정을 설명하는 모형으로 연구되고 있습니다.

1952년 1월 튜링은 집에 든 도둑을 신고했다가, 수사 과정에서 열아홉 살 청년 아널드 머리와의 관계를 스스로 밝혔습니다. 당시 잉글랜드에서 남성 사이의 성관계는 범죄였고(1967년에야 잉글랜드와 웨일스에서 21세 이상 사이의 사적인 관계에 한해 처벌 대상에서 빠졌습니다), 그는 '중대한 풍기 문란'으로 기소되어 3월 유죄를 인정했습니다. 감옥 대신 1년간 여성 호르몬을 투여받는 보호 관찰을 받아들였고, 보안 인가를 잃어 정부의 암호 업무에서도 멀어졌습니다. 1954년 6월 맨체스터 근교 윌름슬로의 집에서 청산가리 중독으로 숨진 채 발견되었습니다. 검시 법정은 자살로 판단했지만, 사고였을 가능성을 제기하는 연구자도 있습니다. 1983년 앤드루 호지스의 전기 『앨런 튜링: 에니그마』가 나오면서 그의 삶 전체가 널리 알려졌습니다. 2009년 영국 총리가 정부를 대표해 사과했고, 2013년 여왕의 이름으로 사면이 내려졌으며, 2017년에는 같은 법으로 처벌받은 수많은 사람을 사후에 사면하는 조항이 흔히 '앨런 튜링 법'이라 불리며 시행되었습니다. 2021년부터 영국의 50파운드 지폐에 그의 얼굴이 실려 있고, 미국 계산기 학회(ACM)가 1966년부터 주는 컴퓨터 과학의 가장 이름난 상도 그의 이름을 딴 튜링상입니다. 2014년 영화 「이미테이션 게임」은 그의 이야기를 널리 알렸지만 많은 사실을 극적으로 바꾸었습니다.

이어지는 곳. 1943년 초 미국에 머물던 튜링은 벨 연구소에서 섀넌과 생각하는 기계에 대해 이야기를 나누었다고 전합니다. 러셀의 역설, 괴델의 정리, 튜링의 정지 문제는 모두 자기 자신에 대해 묻고 답을 뒤집는 같은 모양의 논증입니다(자기 참조⁠(self-reference)⁠와 대각선). 계산할 수 있느냐에서 빨리 계산할 수 있느냐로 물음을 옮기면 P 대 NP 문제⁠(P versus NP problem)⁠가 되고, 테이프에 쓰지 못하고 읽기만 하는 기계는 유한 오토마톤⁠(finite automaton)⁠이 됩니다. 촘스키가 문법을 층층이 나눈 촘스키 위계⁠(Chomsky hierarchy)⁠의 맨 위층이 튜링 기계이고, 프로그램도 자료처럼 기억 장치에 담는다는 저장 프로그램⁠(stored program)⁠의 생각은 1945년 폰 노이만이 설계를 정리한 EDVAC 보고서와 나란히 갑니다. 기계가 생각할 수 있느냐는 물음은 매카시가 이름 붙인 인공지능⁠(artificial intelligence)⁠이 되어 로젠블랫의 퍼셉트론⁠(perceptron)⁠에서 오늘날의 신경망까지 이어지고, 블레츨리의 해독 이야기는 모듈러 연산⁠(modular arithmetic)⁠과 RSA 암호⁠(RSA cryptosystem)⁠로 이어지는 암호의 역사 한가운데에 있습니다.

관계.

• 영향을 받음 쿠르트 괴델 — 괴델의 1931년 불완전성 정리가 남긴 물음, 곧 '기계적인 방법'이란 무엇인가에서 튜링의 1936년 논문이 출발했고, 괴델은 튜링의 분석을 계산 가능성⁠(computability)⁠의 가장 설득력 있는 정의로 받아들였습니다.
• 영향을 받음 다비트 힐베르트 — 힐베르트가 1928년 내놓은 결정 문제에 '그런 기계적 절차는 없다'는 답을 준 것이 튜링 기계의 첫 쓰임이었습니다.
• 영향을 받음 게오르크 칸토어 — 기계는 셀 수 있을 만큼만 있다는 관찰과, 그 목록에 대각선 논법을 적용하는 정지 문제의 증명은 칸토어의 방법을 그대로 가져온 것입니다.
• 영향을 줌 존 폰 노이만 — 프린스턴에서 튜링에게 조수 자리를 권했던 폰 노이만은 1936년 논문의 보편 기계가 저장 프로그램 컴퓨터⁠(stored-program computer)⁠의 바탕이라고 동료들에게 강조했습니다.
• 영향을 줌 클로드 섀넌 — 1943년 벨 연구소에서 두 사람은 생각하는 기계에 대해 이야기를 나누었고, 섀넌은 1956년 내부 상태가 둘뿐인 보편 튜링 기계⁠(universal Turing machine)⁠에 관한 논문을 썼습니다.
• 영향을 줌 노엄 촘스키 — 촘스키가 문법을 네 층으로 나눌 때 가장 넓은 층, 곧 제한 없는 문법이 만드는 언어가 튜링 기계가 알아보는 언어입니다.

연표.

• 1926년 셔본 학교에 들어가다
• 1931년 케임브리지 킹스 칼리지에 들어가다
• 1935년 중심극한정리를 스스로 증명한 논문으로 킹스 칼리지의 펠로가 되다
• 1936년 「계산 가능한 수에 대하여」로 튜링 기계를 정의하고 결정 문제에 답하다
• 1938년 프린스턴에서 처치 밑에서 박사 학위를 받고 영국으로 돌아오다
• 1939년 블레츨리 파크에서 에니그마 해독을 시작하다
• 1940년 첫 봄베 '빅토리'가 블레츨리에서 돌기 시작하다
• 1941년 동료 해독 책임자들과 처칠 총리에게 직접 편지를 쓰다
• 1942년 미국으로 건너가 미 해군의 봄베와 벨 연구소의 음성 암호를 살피다
• 1946년 국립 물리 연구소에 저장 프로그램 컴퓨터 ACE의 설계를 내다
• 1948년 맨체스터 대학으로 옮기다
• 1950년 「계산 기계와 지능」에서 모방 게임을 제안하다
• 1951년 왕립학회 회원이 되다
• 1952년 형태 발생 논문을 내고, 같은 해 '중대한 풍기 문란'으로 기소되다
• 1954년 6월 윌름슬로의 집에서 숨진 채 발견되다