들어가며 — 한 문구에 숨은 두 가지 다른 주장
Tim Roughgarden이 가르치는 "보편적이고 근본적인 개념으로서의 계산(Computation as a universal and fundamental concept)"이라는 짧은 강의가 요즘 화제입니다. 제목은 거의 형이상학적인 큰 독해를 부추깁니다. 계산이란 우주가 어떤 식으로든 그것으로 이루어진 재료이며, 은하부터 뉴런까지 실은 돌아가고 있는 프로그램이라는 식으로 말입니다.
그런데 실제 내용을 읽어 보면 훨씬 절제되어 있고, 솔직히 더 단단합니다. 계산 가능성과 복잡도 이론을 차분히 훑는 강의입니다. 튜링의 1936년 결과, 정지 문제, 어떤 문제는 영리한 알고리즘에 무너지고 어떤 문제는 저항하는 이유, 그리고 P 대 NP. Roughgarden은 복잡도 이론가이고(스탠퍼드와 컬럼비아를 거쳐 지금은 고등연구소(Institute for Advanced Study)에 있습니다), 강의는 시종 견고한 수학적 지반 위에 머뭅니다. 사전 지식은 필요하지 않습니다.
그래서 "보편적이고 근본적"이라는 문구는 사실 아주 다른 두 주장을 품고 있습니다. 하나는 정확하고 증명 가능하며 진짜로 깊습니다. 다른 하나는 매혹적이지만 미끄러운 형이상학적 명제입니다. 이 둘을 갈라 두는 것이 이 글의 전부입니다.
강의가 실제로 말하는 것
강의는 짐짓 단순한 질문으로 문을 엽니다. 컴퓨터가 할 수 없는 일이 있을까? 그리고 진짜 컴퓨터가 나오기 십 년 전인 1936년, 튜링의 작업으로 답합니다. 튜링의 상상 속 기계는 충격적인 사실을 함께 들고 왔습니다. 시간과 하드웨어를 아무리 쏟아부어도 어떤 알고리즘도 결코 풀 수 없는 문제가 있다는 것입니다. 이 프로그램이 언젠가 멈출까, 아니면 영원히 돌까를 묻는 정지 문제는 어떤 컴퓨터로도 풀 수 없음이 증명되어 있습니다.
"증명되어 있다"는 대목이 중요합니다. 이것은 "너무 느리다"거나 "메모리가 부족하다"가 아닙니다. 괴델의 불완전성과 같은 계열에 속하는 수학적 벽입니다. 강의는 힐베르트, 괴델, 폰 노이만으로 이어지는 계보를 전설이 아니라 역사로 다루면서, 알고리즘이 무엇을 할 수 있는가를 좇던 전통과 그 한계를 좇던 전통이 서서히 한 지점으로 수렴하는 과정을 보여 줍니다.
거기서 강의는 더 미묘한 질문으로 방향을 틉니다. 컴퓨터가 풀 수 있는 문제들 가운데, 어떤 것을 빠르게 풀 수 있는가? 어떤 문제는 다익스트라의 최단 경로나 카라추바의 빠른 곱셈처럼 하나의 영리한 착상에 무너집니다. 외판원 문제 같은 다른 문제는 완강히 저항합니다. 그리고 놀라운 발견이 이 어려운 문제 수천 개를 하나로 묶습니다. NP-완전성을 통해, 그것들은 서로 다른 옷을 입은 같은 문제입니다.
이 모든 것이 P 대 NP로 수렴합니다. 강의는 이를 정확하게 컴퓨터 과학에서 가장 중요한 미해결 문제이자 수학의 위대한 난제 중 하나라고 부릅니다. 한 대목은 "우리가 살고 있을지 모르는 두 세계"라는 틀로 제시됩니다. 어려워 보이는 문제가 실은 쉬운 세계, 그리고 우리가 아마도 살고 있을, 그렇지 않은 세계입니다. 강의는 그 답이 암호학과 AI, 양자 컴퓨팅에 무엇을 의미할지 물으며 마무리됩니다.
'보편'이라는 말이 실제로 값을 하는 지점
과장을 걷어내면, 계산을 보편적이라 부를 진짜 이유가 있습니다. 그리고 그것은 두 갈래로 옵니다.
첫째는 모델 독립성입니다. 튜링 기계, 처치의 람다 계산, 레지스터 기계, 그 밖의 모든 합리적인 "실효적 절차" 모델은 정확히 같은 함수 집합을 계산하는 것으로 드러납니다. 처치와 튜링은 1936년 정반대 방향에서 출발해 같은 자리에 도달했습니다. 그 우연의 일치가 바로 처치-튜링 논제의 내용이고, 계산이 하나의 장치가 아니라 하나의 개념인 이유입니다. 같은 계산이 실리콘 위에서도, 종이 위에서도, 도미노 위에서도, 심지어 울프럼의 규칙 110처럼 단순한 세포 자동자 위에서도 돌아갑니다. 규칙 110은 튜링 완전합니다. 바탕 물질은 중요하지 않습니다. 이것은 깊고 결코 자명하지 않은 사실입니다.
둘째는 NP-완전성이며, 이는 계산 자체의 내부에 있는 다른 종류의 보편성입니다. 스케줄링, 칩 배치, 퍼즐 풀이 등 서로 무관해 보이는 수많은 문제가 증명 가능하게 동등합니다. 그중 단 하나에 대한 진짜로 빠른 알고리즘은 곧 그 전부에 대한 빠른 알고리즘입니다. 이것은 비유나 유비가 아닙니다. 정리이고, 세계가 이렇게 짜여 있다는 것 자체가 놀랍습니다.
그리고 계산 불가능성은 "근본적"이라는 말을 거창함이 아니라 정직함으로 지켜 줍니다. 정지 문제는 미래의 어떤 하드웨어도, 어떤 양자 트릭도, 어떤 예산도 결코 넘지 못할 선을 긋습니다. 자기 자신의 영구적 한계를 추측이 아니라 증명해 내는 분야는, 그 단어를 쓸 자격을 얻은 것입니다.
어디서부터 과장이 되는가
위의 어떤 것도 우주가 컴퓨터라거나 당신의 마음이 소프트웨어라고 말하지 않습니다. 그것들은 별개의, 훨씬 큰 주장이며 강의는 둘 다 하지 않습니다. 증명 가능한 판본에서 형이상학적 판본으로 미끄러지는 바로 그 지점에서 대개 신중한 사고가 죽습니다.
가장 넓은 판본인 디지털 물리학은 긴 계보를 가집니다. 콘라트 추제의 "계산하는 공간(Rechnender Raum)"(1969), 존 휠러의 "it from bit", 울프럼의 계산적 동등성 원리, 그리고 더 최근에는 우주를 재작성 시스템으로 모델링하는 그의 물리 프로젝트까지. 진지하고 상상력 넘치는 발상들입니다. 하지만 "모든 것은 계산이다"에는 고장 모드가 있습니다. 생각할 수 있는 모든 관측이 우주가 계산한다는 주장과 똑같이 양립한다면, 그 주장은 아무것도 예측하지 않고 아무것도 배제하지 않습니다. 틀릴 수 없는 진술은 이론이 아니라 하나의 프레임일 뿐입니다.
정직한 중간 지대는 물리적 처치-튜링 논제입니다. 어떤 물리적 과정이든 튜링 기계로 시뮬레이션할 수 있다는 주장입니다. 이것은 진짜로 반증 가능합니다. 계산 불가능한 것을 계산하는 물리 장치, 즉 진정한 초계산기를 만들면 이 논제는 죽습니다. 주목할 점은 양자 컴퓨터가 이 일을 하지 못한다는 것입니다. 양자 컴퓨터는 튜링 기계가 계산할 수 있는 것과 같은 함수를 계산하며, 다만 때때로 극적으로 더 빠릅니다. 이것은 효율에 관한 주장이지 계산 가능성에 관한 주장이 아닙니다. 도이치의 1985년 작업이 이 물리적 판본을 무대에 올렸고, 위험을 감수하기 때문에 존중받습니다.
같은 규율이 마음에도 적용됩니다. 계산이 인지를 보는 강력한 렌즈라는 것, 즉 마음의 계산 이론은 생산적인 연구 프로그램입니다. 반면 뇌가 문자 그대로 계산 외에는 아무것도 아니라는 것은 정리가 아니라 논쟁 중인 철학적 입장입니다. 하나의 함수가 서로 다른 하드웨어에서 돌아갈 수 있다는 좋은 착상인 다중 실현 가능성은, "생물학과 마음은 오직 계산일 뿐"이라는 도약을 허가하지 않습니다. 많은 것을 드러내는 렌즈가, 실재가 그 렌즈로 만들어졌다는 주장과 같지는 않습니다.
마치며
실제로 옹호할 수 있는 "계산은 보편적이고 근본적이다"의 판본은 강의가 가르치는 그것입니다. 모델 독립성, 절대적 계산 불가능성, 어려운 문제들의 숨은 동등성, 그리고 P 대 NP라는 미해결 질문. 개발자로서 이것은 새겨 둘 가치가 있습니다. 어떤 벽이 영구적인지(계산 불가능한 문제, 그리고 거의 확실히 NP-난해한 문제), 어떤 벽이 그저 현재의 것인지를 알려 주기 때문입니다.
실재 자체가 계산이라는 더 큰 이야기는 손에 질문 하나를 쥐고 읽을 가치가 있습니다. 이 판본은 위험한 예측을 하는가, 아니면 어떤 결과든 흡수할 만큼 늘어나는 비유인가? 물리적 처치-튜링 논제는 그 시험을 통과합니다. "우주는 컴퓨터다, 끝"은 대개 통과하지 못하며, 그 차이는 작지 않습니다.
Roughgarden의 강의는 과소평가되기 쉬운 바로 그 이유로 시간을 들일 가치가 있습니다. 견고한 지반 위에 머물며, 누군가 우주로 손을 뻗기 전에 이미 얼마나 많은 것이 진짜로 거기 있는지를 보여 줍니다. 모델 독립성, 확고한 한계, 깊은 동등성 말입니다.
참고 자료
- Ergo — Computation as a Universal and Fundamental Concept (Tim Roughgarden): https://ergo.org/courses/computation-as-a-universal-and-fundamental-concept
- Hacker News 토론: https://news.ycombinator.com/item?id=48861213
- Tim Roughgarden — 강의와 홈페이지: https://timroughgarden.org/
- Stanford Encyclopedia of Philosophy — The Church-Turing Thesis: https://plato.stanford.edu/entries/church-turing/
- Clay Mathematics Institute — 밀레니엄 문제 (P 대 NP): https://www.claymath.org/millennium-problems/
- Stephen Wolfram — A New Kind of Science (온라인): https://www.wolframscience.com/nks/
현재 단락 (1/24)
Tim Roughgarden이 가르치는 "보편적이고 근본적인 개념으로서의 계산(Computation as a universal and fundamental concept)"이라는 ...