앨런 튜링과 부정적 사고의 힘

알고리즘은 어디에나 존재하게 되었습니다. 알고리즘은 우리의 통근 경로를 최적화하고, 결제를 처리하며, 인터넷 트래픽의 흐름을 조정합니다. 정확한 수학적 용어로 표현할 수 있는 모든 문제에는, 적어도 원리상으로는 그것을 풀 수 있는 알고리즘이 있는 듯합니다.

하지만 그렇지 않습니다. 겉보기에는 단순한 일부 문제는 알고리즘으로 결코 풀 수 없습니다. 선구적인 컴퓨터 과학자 앨런 튜링은 거의 한 세기 전, 현대 컴퓨터 과학을 출범시킨 계산의 수학적 모형을 정립한 바로 그 논문에서 그러한 “계산 불가능한” 문제의 존재를 증명했습니다 (새 탭에서 열림).

튜링은 직관에 어긋나는 전략으로 이 획기적인 결과를 증명했습니다. 그는 그것을 풀려는 모든 시도를 그저 거부하는 문제를 정의했습니다.

이론 컴퓨터 과학을 연구하는 매사추세츠 공과대학교의 대학원생 라훌 일랑고 (새 탭에서 열림)는 “나는 당신에게 무엇을 하는지 묻고, তারপর ‘아니, 나는 다른 일을 할 거야’라고 말하는 셈입니다”라고 말했습니다.

튜링의 전략은 뛰어난 역사를 지닌 대각선 논법이라는 수학적 기법에 기반했습니다. 다음은 그의 증명 뒤에 있는 논리를 단순화해 설명한 것입니다.

문자열 이론

대각선 논법은 각각 0 또는 1이 될 수 있는 비트 문자열을 다루는 평범한 문제를 푸는 영리한 요령에서 비롯됩니다. 길이가 모두 같은 이런 문자열 목록이 주어졌을 때, 목록에 없는 새로운 문자열을 만들 수 있을까요?

가장 직관적인 전략은 가능한 모든 문자열을 차례로 살펴보는 것입니다. 길이가 각각 5비트인 문자열 다섯 개가 있다고 해 봅시다. 먼저 목록에서 00000을 찾습니다. 없다면 멈추면 됩니다. 있다면 00001로 넘어가 같은 과정을 반복합니다. 충분히 단순하지만, 긴 문자열로 이루어진 긴 목록에서는 느립니다.

대각선 논법은 빠진 문자열을 비트 하나씩 만들어 가는 대안적 접근법입니다. 목록의 첫 번째 문자열의 첫 번째 비트에서 시작해 그것을 뒤집습니다. 그러면 그것이 새 문자열의 첫 번째 비트가 됩니다. 다음으로 두 번째 문자열의 두 번째 비트를 뒤집어 새 문자열의 두 번째 비트로 사용하고, 목록 끝에 도달할 때까지 반복합니다. 뒤집은 비트들 덕분에 새 문자열은 원래 목록의 모든 문자열과 적어도 한 자리에서 달라집니다. (또한 이 비트들은 문자열 목록을 가로지르는 대각선을 이루며, 여기서 이 기법의 이름이 나왔습니다.)

메릴 셔먼/Quanta Magazine

대각선 논법은 목록의 각 문자열에서 비트 하나만 살펴보면 되므로, 다른 방법보다 훨씬 빠른 경우가 많습니다. 하지만 이 기법의 진정한 힘은 무한과 얼마나 잘 어울리는가에 있습니다.

매사추세츠 공과대학교의 이론 컴퓨터 과학자 라이언 윌리엄스 (새 탭에서 열림)는 “이제 문자열은 무한할 수 있고, 목록도 무한할 수 있습니다. 그래도 작동합니다”라고 말했습니다.

이 힘을 처음 활용한 사람은 집합론이라는 수학 하위 분야의 창시자인 게오르크 칸토어였습니다. 1873년 칸토어는 대각선 논법을 이용해 어떤 무한은 다른 무한보다 더 크다는 것을 증명했습니다. 60여 년 뒤 튜링은 칸토어의 대각선 논법을 계산 이론에 맞게 변형해, 뚜렷이 반대하는 듯한 성격을 부여했습니다.

한계 게임

튜링은 어떤 알고리즘도 풀 수 없는 수학 문제, 즉 입력과 출력은 잘 정의되어 있지만 입력에서 출력으로 가는 확실한 절차는 없는 문제의 존재를 증명하고자 했습니다. 그는 입력이 0과 1로 이루어진 어떤 문자열이든 될 수 있고 출력은 0 또는 1인 결정 문제에만 집중함으로써 이 모호한 과제를 더 다루기 쉽게 만들었습니다.

어떤 수가 소수인지 판별하는 일은 결정 문제의 한 예입니다. 수를 나타내는 입력 문자열이 주어졌을 때, 그 수가 소수라면 올바른 출력은 1이고 아니라면 0입니다. 또 다른 예는 컴퓨터 프로그램에 문법 오류, 즉 문법적 실수에 해당하는 오류가 있는지 검사하는 것입니다. 여기서 입력 문자열은 서로 다른 프로그램의 코드를 나타냅니다. 모든 프로그램은 이런 방식으로 표현할 수 있는데, 컴퓨터에 저장되고 실행되는 방식이 바로 이것이기 때문입니다. 목표는 코드에 문법 오류가 있으면 1을, 없으면 0을 출력하는 것입니다.

알고리즘이 문제를 푼다고 하려면 가능한 모든 입력에 대해 올바른 출력을 내야 합니다. 단 한 번이라도 실패한다면 그 문제를 위한 범용 알고리즘이 아닙니다. 보통은 먼저 풀고 싶은 문제를 정한 뒤 그것을 푸는 알고리즘을 찾으려 합니다. 풀 수 없는 문제를 찾던 튜링은 이 논리를 뒤집었습니다. 그는 가능한 모든 알고리즘의 무한한 목록을 상상하고, 대각선 논법을 사용해 목록의 모든 알고리즘을 좌절시킬 고집스러운 문제를 구성했습니다.

특정한 물건을 염두에 두고 시작하는 대신, 답하는 사람이 각 질문에 아니라고 말할 구실을 만들어 내는 조작된 스무고개 게임을 상상해 보세요. 게임이 끝날 무렵, 그 사람은 오직 결여된 특성들로 정의되는 물건을 묘사하게 됩니다.

튜링의 대각선 논법 증명은 질문들이 가능한 알고리즘의 무한한 목록을 따라가며 반복해서 “이 알고리즘은 우리가 계산 불가능함을 증명하려는 문제를 풀 수 있는가?”라고 묻는 이 게임의 한 형태입니다.

윌리엄스는 “일종의 ‘무한 질문’입니다”라고 말했습니다.

게임에서 이기기 위해 튜링은 모든 알고리즘에 대한 답이 아니오가 되는 문제를 만들어야 했습니다. 이는 첫 번째 알고리즘이 틀린 답을 내게 만드는 특정 입력 하나, 두 번째 알고리즘을 실패하게 만드는 또 다른 입력 하나 등을 찾아내야 한다는 뜻이었습니다. 그는 최근 쿠르트 괴델이 “이 명제는 증명될 수 없다”와 같은 자기지시적 진술이 수학의 토대에 문제를 일으킨다는 것을 증명하는 데 사용한 것과 비슷한 요령으로 이런 특수한 입력을 찾아냈습니다.

핵심 통찰은 모든 알고리즘, 즉 프로그램이 0과 1의 문자열로 표현될 수 있다는 점이었습니다. 이는 오류 검사 프로그램의 예에서처럼, 한 알고리즘이 다른 알고리즘의 코드를 입력으로 받을 수 있음을 뜻합니다. 원칙적으로 알고리즘은 자기 자신의 코드까지도 입력으로 받을 수 있습니다.

이 통찰을 바탕으로 튜링의 증명에 나오는 것과 같은 계산 불가능한 문제를 정의할 수 있습니다. “알고리즘의 코드를 나타내는 입력 문자열이 주어졌을 때, 그 알고리즘이 자기 자신의 코드를 입력으로 받았을 때 0을 출력하면 1을 출력하고, 그렇지 않으면 0을 출력하라.” 이 문제를 풀려고 하는 모든 알고리즘은 적어도 하나의 입력에서 틀린 출력을 냅니다. 바로 자기 자신의 코드에 해당하는 입력입니다. 이는 이 뒤틀린 문제가 어떤 알고리즘으로도 전혀 풀릴 수 없음을 뜻합니다.

부정으로 할 수 없는 것

컴퓨터 과학자들은 아직 대각선 논법을 끝내지 않았습니다. 1965년 유리스 하르트마니스와 리처드 스턴스는 튜링의 논증을 변형해, 계산 가능한 모든 문제가 동등하게 만들어진 것은 아니라는 사실, 즉 어떤 문제들은 본질적으로 다른 문제보다 더 어렵다는 것을 증명했습니다 (새 탭에서 열림). 이 결과는 계산 문제의 난이도를 연구하는 계산 복잡도 이론 분야를 출범시켰습니다.

하지만 복잡도 이론은 튜링의 반대 전략이 지닌 한계도 드러냈습니다. 1975년 시어도어 베이커, 존 길, 로버트 솔로베이는 복잡도 이론의 많은 미해결 문제가 대각선 논법만으로는 결코 해결될 수 없다는 것을 증명했습니다 (새 탭에서 열림). 그중 가장 중요한 것은 유명한 피 대 엔피 문제로, 해답을 쉽게 검증할 수 있는 모든 문제가 적절히 기발한 알고리즘으로도 쉽게 풀리는지를 묻습니다.

대각선 논법의 맹점은 그것을 강력하게 만드는 높은 수준의 추상화에서 직접 비롯됩니다. 튜링의 증명은 실제로 등장할 수 있는 어떤 계산 불가능한 문제도 다루지 않았습니다. 대신 그런 문제를 즉석에서 만들어 냈습니다. 다른 대각선 논법 증명도 마찬가지로 현실 세계와 거리가 멀기 때문에, 현실의 세부 사항이 중요한 질문을 해결할 수 없습니다.

윌리엄스는 “그들은 거리를 두고 계산을 다룹니다”라고 말했습니다. “나는 바이러스를 다루지만 어떤 글러브 박스를 통해 그것에 접근하는 사람을 상상합니다.”

대각선 논법의 실패는 피 대 엔피 문제를 푸는 일이 긴 여정이 될 것이라는 초기 징후였습니다. 그러나 그 한계에도 불구하고 대각선 논법은 복잡도 이론가들의 도구 상자에서 여전히 핵심 도구 가운데 하나입니다. 2011년 윌리엄스는 이 기법을 다른 수많은 기법과 함께 사용해, 특정한 제한된 계산 모형이 극도로 어려운 몇몇 문제를 풀 수 없다는 것을 증명했습니다 (새 탭에서 열림). 이는 연구자들을 25년간 피해 온 결과였습니다. 피 대 엔피 문제를 해결하는 것과는 거리가 멀었지만, 그래도 중요한 진전을 나타냈습니다.

무언가가 가능하지 않음을 증명하고 싶다면, 그저 아니라고 말하는 힘을 과소평가하지 마세요.