앨런 튜링 Alan Mathison Turing

이 글은 Crash Course의 Computer Science를 보고 정리한 글입니다.

앨런 튜링은 현대의 컴퓨테이션을 강조하는 많은 이론적 개념을 공식화한 사람으로 컴퓨터 과학의 아버지라고 불린다.

 

Alan Mathison Turing은 1912년 런던에서 태어났다. 그는 조기 교육에서 수학과 과학에 대한 놀라운 적성을 보여주었다.

처음 컴퓨터 과학이라고 부르게 된 것은 1935년 케임브리지의 King's College에서 석사 과정을 밟으며 시작되었다. 그때 그는 독일 수학자 David Hilbert가 고안한 Entscheidungsproblem(= Decision problem ; 의사 결정 문제)을 풀기 시작했다. 이것은 형식 논리학적으로 쓰인 문장을 입력으로 받아들여 항상 정확하게 "예" 또는 "아니오"라는 대답을 생성하는 알고리즘을 찾는 문제이다.

이러한 알고리즘이 존재한다면, 우리는 그것을 사용하여 답을 알고 싶어 하는 다른 많은 수학적인 질문에 답을 찾을 수 있을 것이다. 따라서 이 알고리즘이 존재한다면, 우리는 그것을 알고 싶어 할 것이다.

 

미국의 수학자 Alonzo Church는 1935년에 이 문제에 대한 해결책을 제시했다. 그는 람다 미적분학(Lambda Calculus)이라는 수학적 표현 체계를 개발했다. 또한 그런 보편적인 알고리즘이 존재할 수 없음을 보여주었다.

람다 미적분은 어떤 계산을 나타낼 수는 있었지만, 거기에 수학 기술을 적용하고 이해하기가 어려웠다.

 

거의 비슷한 시기에 대서양의 건너편에서 앨런 튜링은 의사 결정 문제를 해결하기 위한 자신의 접근 방식을 제시했다. 그는 가상의 컴퓨팅 머신을 제안했다. 현재는 이것을 튜링 머신(Turing Machine)이라고 부른다.

튜링 머신은 단순하면서도 강력한 계산의 수학적 모델을 제공했다. 완전히 다른 수학을 사용하지만, 그것들은 계산 능력면에서 람다 미적분과 기능적으로 동일하다. 그러나 그들의 상대적인 단순성은 급성장하는 컴퓨터 과학 분야에서 훨씬 인기가 있었다.

사실, 튜링 머신은 매우 단순한 이론적인 계산 장치이다. 부호를 저장하는 무한히 긴 메모리 테이프가 장착돼있고, 그 테이프의 부호들을 읽고 쓰거나 수정할 수 있는 읽기/쓰기 헤드라고 불리는 장치가 장착되어 있다. 또한 기계의 현재 상태에 대한 정보를 저장할 수 있는 상태 변수도 있다. 그리고 기계가 하는 일을 설명하는 일련의 규칙도 있다.

일단 헤드가 현재 부호와 상태를 읽으며, 규칙은 테이프에 부호를 작성할 수 있다. 읽기/쓰기 헤드를 왼쪽 또는 오른쪽으로 한 지점 또는 다른 지점으로 이동하도록 하는 등의 동작의 조합으로 기계의 상태를 변경할 수 있다.

 

예를 들면, 제로(zero)로 끝나는 문자열을 읽는 튜링 머신이 있다고 하자. 이 튜링 머신으로 1의 개수가 짝수인지의 여부를 계산해보자. 만약 1의 개수가 짝수이면 기계는 테이프에 1을 기록하고, 홀수이면 0을 기록한다.

먼저 튜링 머신 규칙을 정의해야 한다. (1) 상태가 짝수이고 테이프의 현재 기호가 1인 경우, 기계 상태를 홀수로 업데이트하고 헤드를 오른쪽으로 이동한다. (2) 반면 상태가 짝수이고 현재 기호가 0인 경우, 이는 우리가 문자열의 끝에 도달했다는 것을 의미하고, 그 경우 테이프에 1을 쓰고 상태를 Halt로 바꾼다. 이것은 튜링 머신이 계산을 끝냈음을 의미한다.

튜링 머신이 홀수 상태에 있을 때도 규칙이 필요하다. (3) 테이프의 기호가 1인 경우, 기계 상태를 짝수로 업데이트하고 헤드를 오른쪽으로 이동하고, (4) 0인 경우에는 테이프에 0을 쓰고 상태를 Halt로 바꾼다.

마지막으로 시작 상태를 정의해야 한다. 시작 상태는 짝수로 설정하겠다.

 

이것은 컴퓨터 프로그램과 비슷하며, 간단한 예를 입력해서 실행해 보도록 하겠다. 테이프에 110을 저장한다고 가정해보자. 여기에 두 개의 1이 있다. 즉, 1이 짝수 개가 있는 것을 의미한다. 처음 보는 숫자는 1이다. 이것은 첫 규칙과 일치한다. 따라서 상태를 홀수로 업데이트하고, 읽기/쓰기 헤드를 오른쪽으로 한 지점 이동한다.

이제 다른 테이프의 숫자 1이 있다. 따라서 상태를 다시 짝수로 설정하고 헤드를 오른쪽으로 이동시키는 세 번째 규칙을 실행한다.

이제 0을 읽고 현재 상태는 짝수이므로 두 번째 규칙을 실행한다. 테이프에 1을 쓰는 것이다. 1이 짝수 개가 있었으니 1을 쓰고, 마침내 기계가 멈춘다.

이것이 튜링 머신이 작동하는 방법이다.

 

이 예제로는 튜링 머신이 대단해 보이지 않을 수 있다. 하지만 앨런 튜링은 이 간단한 가상 기계가 충분한 시간과 메모리를 주면 어떤 계산이든 수행할 수 있음을 보여줬다. 이것은 범용 컴퓨터의 간단한 예제이지만, 그러나 충분한 규칙 상태와 테이프로 무엇이든 만들 수 있다. 이것이 바로 컴퓨팅 모델로서의 강력한 아이디어인 이유이다.

 

Hilbert의 결정 문제에 답하기 위해 Turing은 이 새로운 튜링 머신을 전산 퍼즐에 적용해 보았다. 정지 문제(Halting problem)는 "튜링 머신에 설명과 테이프로부터의 입력이 주어지면 영원히 실행될 것인가, 또는 멈출 것인가?" 하는 문제로 프로그램을 실행하지 않고 언제 중단될지 알아낼 방법을 찾는 것이다. 이것은 일부 프로그램이 실행하는 데 몇 년이 걸릴 수 있어서 프로그램을 실행하기 전에 알고 기다리는 것이 유용할 것이기 때문이다.

 

불행히도 Turing은 논리적인 모순을 통해 정지 문제가 실제로 풀리지 않는다는 증거를 제시했다.

프로그램에 대한 설명과 테이프에 입력값을 넣는 가상 튜링 머신을 상상해보자. Yes면 멈추고 No면 계속하는 것으로 하자. 이 기계를 "H for Halt"라고 하자. 튜링이 이 H에 정지동작을 결정할 수 없는 프로그램이 있다면 정지 문제는 해결이 불가능하다고 추론했다. 답을 찾기 위해 튜링은 H 우에 구축된 다른 튜링 머신을 만들었다. 만약 H가 프로그램이 중단되었다고 말하면, 영원히 반복하는 새로운 기계를 만들 것이다. 중단되지 않았다고 답하면, No와 Halt를 출력하는 새로운 기계를 만들 것이다. 이것들은 지금 H가 말하는 것과 정반대의 일을 하는 기계를 만들고 있는 것이다. 프로그램이 중단되지 않으면 멈추고, 프로그램이 멈추면 무한 반복한다. 이 논쟁을 위해 또 앞에 새로운 기계 스플리터(splitter)를 추가해야 한다. 하나의 입력만 받아서 H안의 프로그램의 입력으로 통과시킨다. 이 새로운 기계를 Bizzaro라고 부르자.

Bizzaro에 입력으로 스스로의 설명을 전달해보자. 이것은 Bizzaro가 스스로를 평가할 것을 요구받을 때 무엇을 해야 할지 H에게 묻는 것을 의미한다. 그러나 H가 Bizzaro가 멈춘다고 말하면 Bizzaro는 무한 루프에 들어가서 멈추지 않는다. 그리고 H가 Bizarro가 멈추지 않는다고 말하면 Bizzaro는 No와 Halt를 출력한다. 따라서, H는 답이 없으므로 정지 문제를 올바르게 결정할 수 없다. 이것은 역설이지만 이 역설이 의미하는 바는 튜링 머신으로는 정지 문제를 해결할 수 없다는 것을 보여준다.

 

앞서 Turing이 튜링 머신으로 어떤 계산이든 수행할 수 있다는 것을 증명해냈다고 했다. 따라서 정지 문제에 대한 이 해법은 모든 문제가 계산으로 해결할 수 있는 것은 아니라는 것을 증명한다. 간단하게 말하면, Church와 Turing은 시간이나 메모리가 아무리 많아도 컴퓨터의 능력에는 한계가 있음을 보여준다. Turing과 Church에 의한 게산의 한계를 정해보려는 경쟁적인 노력에 의해, 일반적으로 계산 능력을 형식화하려고 하는 것을 Church-Turing 명제라고 부른다.

 

1936년, 튜링은 겨우 24세였고, 사회생활을 시작했다. 1936년부터 1938년 동안, 프린스턴 대학에서 박사 학위를 받았다. 졸업 후 Church의 인도 하에 캠브릿지로 돌아왔다. 1년 후인 1939년에 영국은 제2차 세계 대전에 참전했고, 튜링의 천재성은 전쟁에 빠르게 적용되었다. 사실 1년 전 그는 이미 영국 정부 법규 기관과 사이퍼 학교에서 아르바이트를 하고 있었다. 이 기관은 Bletchley Park에 기반을 둔 영국의 암호 해독 조직이었다.

 

튜링의 주요 노력 중 하나는 독일 통신을 해독하는 방법을 알아내는 것이었다. 특히 애니그마 기계는 간단히 말하면, 텍스트를 뒤섞었다. 예를 들어 Hello라는 글자를 타이핑하면 문자 Xwdbj가 출력되는 식이다. 이 과정을 암호화(Encryption)이라고 한다. 문자를 뒤섞는 스크램블링은 무작위가 아니다. 이 동작은 애니그마 기계의 맨 위에 있는 일련의 명령 가능한 회전 장치에 의해 정의되었다. 각 스크램블링은 26개의 회전 위치가 있다. 또, 기계 앞면에는 글자의 짝을 바꿀 수 있는 플러그 보드가 있었다. 총 수십억 개의 설정이 가능했다. 만약 애니그마 기계를 가지고 있고, 회전장치와 플러그 보드 설정 방법을 안다면, Xwdbj를 입력했을 때 Hello가 출력될 것이다. 다시 말하면, 메시지를 해독(Decrypted) 한 것이다. 물론 독일 군대는 애니그마 설정을 공개하지 않았고, 동맹국들은 수십억의 회전장치 및 플러그 보드의 조합으로 암호를 해독해야 했다. 손으로 모두 확인할 수밖에 없었다.

 

튜링은 폴란드의 초기 암호 해독가로 일하면서 특수 목적의 전자식 컴퓨터를 고안해냈다. 이 컴퓨터를 Bombe라고 불렀으면, 주어진 암호화된 메시지에 대해 많은 애니그마 조합을 시도했다. 주어진 암호화 메시지에 대해 Bombe가 인코딩한 설정 방법을 스스로 발견하면, 말이 안 되는 조합은 폐기하고 기계는 다른 조합을 시도하기 위해 계속 움직였다. 그래서 Bombes는 가능한 애니그마 설정의 수를 크게 줄이기 위해 사용되었다. 이것으로 인해 암호 해독가들은 가장 가능할 만한 해답을 찾기 위해 디코딩된 텍스트 조각에서 일반적인 독일어 단어와 같은 것을 찾으려 했다.

 

정기적으로 독일군은 누군가가 통신을 해독하고 있는 것으로 의심하고, 수수께끼 기계를 업그레이드하는 것처럼 더 많은 조합을 만들어서 심지어 완전히 새로운 암호화 기계를 만들기도 했다. 전쟁을 통틀어 Bletchley Park의 튜링과 그의 동료들은 끊임없이 이 메커니즘을 없애고 해독된 독일 통신에서 얻은 정보는 이러한 노력이 전쟁을 단축했다고 주장하는 많은 역사가들과 함께 많은 전쟁터에서 동맹군을 우위로 만들었다.

 

전쟁 후 튜링은 아카데미아로 돌아갔고,  Manchester Mark 1과 같은 많은 초기의 전자 컴퓨팅에 기여했다. 그러나 그의 가장 유명한 전쟁 이후 공헌은 1956년까지 그 이름을 얻지 못했던 새로운 분야인 인공지능(Artificial Intelligence) 분야이다.

1950년에 튜링은 컴퓨터가 인간과 동등하거나 적어도 인간과 구별할 수 없을 만큼 강력한 능력을 지닌 미래를 내다볼 수 있었다. 튜링은 컴퓨터가 인간을 속여서 인간이라고 믿게 만들 수 있다면, 지능형이라고 부를 자격이 있다고 가정했다. 이것은 튜링 테스트(Turing Test)라 불리는 간단한 테스트의 기반이 되었다.

 

당신이 목소리로 직접 대화가 아닌 방법으로 다른 두 사람과 대화하고 있다고 상상해보자. 대신, 입력된 메모를 앞뒤로 보낸다. 원하는 질문을 하고, 대답을 얻을 때 두 사람 중 하나는 컴퓨터이다. 이때, 어느 것이 인간이고 어떤 것이 컴퓨터인지 알 수 없다면 컴퓨터가 튜링 테스트에 합격했다고 한다. 이 테스트의 최신 버전을 완전 자동화된 공개 튜링 테스트로 컴퓨터에게 사람인지를 구분할 수 있도록 짧은 보안 문자를 알리는 테스트이다. 이것은 자동화된 시스템이 웹 사이트에 스팸을 게시하는 일을 하지 못하도록 인터넷에서 자주 사용된다.

 

또한, 튜링은 영국과 세계 대부분에서 동성애가 불법이었던 시기에 동성애자였다. 1952년 그의 집에 있었던 강도 사건에 대한 조사에서, 그의 성적 취향이 당국에 밝혀졌고 심한 외설로 기소당했다. 그는 유죄 판결을 받았고 집행 유예 또는 성적 취향을 억압하기 위한 호르몬 치료를 하는 수감 사이의 선택이 주어졌다. 그는 부분적으로 학업을 계속하기 위해 후자를 선택했으나 분위기와 성격이 바뀌었다. 정확한 상황은 알 수 없지만, 튜링이 1954년에 음독자살을 했다는 것이 가장 널리 받아들여지고 있다. 그때 그의 나이 41세였다.

 

컴퓨터 과학 이론에 대한 튜링의 공헌을 인정하여 많은 것들이 명명되었다. 그러나 아마 컴퓨터 과학 분야에서 그것들 중 가장 권위 있는 것은 튜링상(Turing Award) 일 것이다. 물리학, 화학 또는 기타 과학 분야의 노벨상과 같다.

 

인생이 짧았음에도 앨런 튜링은 컴퓨터 과학자 1세대에게 영감을 불어넣었으며 오늘날 우리가 즐기는 디지털 시대를 가능하게 하는 핵심 토대를 마련했다.