Skip to content
←

Split View: 보편 개념으로서의 계산 — 무엇이 단단하고 무엇이 과장인가

|

보편 개념으로서의 계산 — 무엇이 단단하고 무엇이 과장인가

들어가며 — 한 문구에 숨은 두 가지 다른 주장

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의 강의는 과소평가되기 쉬운 바로 그 이유로 시간을 들일 가치가 있습니다. 견고한 지반 위에 머물며, 누군가 우주로 손을 뻗기 전에 이미 얼마나 많은 것이 진짜로 거기 있는지를 보여 줍니다. 모델 독립성, 확고한 한계, 깊은 동등성 말입니다.

참고 자료

Computation as a Universal Concept — What Holds Up and What Is Overclaimed

Introduction — Two Very Different Claims Hide in One Phrase

A short course called "Computation as a universal and fundamental concept," taught by Tim Roughgarden, has been making the rounds. The title invites a big, almost metaphysical reading: that computation is the stuff the universe is somehow made of, that everything from galaxies to neurons is really a program running.

Read the actual material and it is something more modest and, honestly, more solid. It is a careful tour of computability and complexity theory: Turing's 1936 result, the halting problem, why some problems yield to clever algorithms while others resist, and P versus NP. Roughgarden is a complexity theorist — now at the Institute for Advanced Study, after years at Stanford and Columbia — and the course stays on firm mathematical ground. No prior background is required.

So the phrase "universal and fundamental" turns out to hide two very different claims. One is precise, provable, and genuinely deep. The other is a sweeping metaphysical thesis that is fascinating but slippery. Keeping them apart is the whole point of this post.

What the Course Actually Argues

The course opens with a deceptively simple question — is there anything computers cannot do? — and answers it with Turing's work from 1936, a decade before real computers existed. Turing's imaginary machine came with a shock: there are problems no algorithm can ever solve, no matter how much time or hardware you throw at them. The halting problem — will this program eventually stop, or loop forever? — is provably beyond the reach of any computer.

That word "provably" matters. This is not "too slow" or "not enough memory." It is a mathematical wall, in the same family as Gödel's incompleteness. The course traces the lineage through Hilbert, Gödel, and von Neumann as history rather than legend, showing two research traditions — one about what algorithms can achieve, one about their limits — slowly converging.

From there it pivots to a subtler question: among the problems computers can solve, which can they solve quickly? Some collapse under a single clever idea, like Dijkstra's shortest paths or Karatsuba's fast multiplication. Others, like the Traveling Salesman Problem, stubbornly resist. And a startling discovery ties thousands of these hard problems together: through NP-completeness, they are the same problem wearing different costumes.

All of it converges on P versus NP, which the course calls — accurately — the most important open question in computer science and one of the great unsolved problems in mathematics. One stretch is framed as "two worlds we might live in": a world where hard-looking problems are secretly easy, and the one we probably inhabit, where they are not. The course closes by asking what the answer would mean for cryptography, AI, and quantum computing.

Where "Universal" Actually Earns Its Meaning

Strip away the marketing and there is a real reason to call computation universal, and it arrives in two flavors.

The first is model-independence. Turing machines, Church's lambda calculus, register machines, and every other reasonable model of an "effective procedure" turn out to compute exactly the same set of functions. Church and Turing reached this from opposite directions in 1936 and landed in the same place. That coincidence is the content of the Church-Turing thesis, and it is why computation is a concept and not just a gadget: the same computation runs on silicon, on paper, on dominoes, or on a cellular automaton as simple as Wolfram's Rule 110, which is Turing-complete. Substrate does not matter. That is deep and not at all obvious.

The second is NP-completeness — universality of a different kind, internal to computation itself. Scheduling, chip layout, puzzle solving, countless unrelated-looking problems are provably equivalent: a genuinely fast algorithm for any single one of them would be a fast algorithm for all of them at once. That is not a metaphor or an analogy. It is a theorem, and it is astonishing that the world is arranged this way.

And uncomputability is what keeps "fundamental" honest rather than grandiose. The halting problem draws a line that no future hardware, no quantum trick, and no budget will ever cross. A field that can prove its own permanent limits — not guess at them, prove them — has earned the word.

Where It Gets Overclaimed

None of the above says the universe is a computer, or that your mind is software. Those are separate, much larger claims, and the course makes neither of them. The slide from the provable version to the metaphysical one is where careful thinking usually goes to die.

The broadest version — digital physics — has a long pedigree: Konrad Zuse's "Calculating Space" (1969), John Wheeler's "it from bit," Wolfram's principle of computational equivalence, and more recently his physics project modeling the universe as a rewriting system. These are serious, imaginative ideas. But "everything is computation" has a failure mode: if every conceivable observation is equally compatible with the universe computing, then the claim predicts nothing and rules out nothing. A statement that cannot be wrong is not a theory; it is a framing.

The honest middle ground is the physical Church-Turing thesis: the claim that any physical process can be simulated by a Turing machine. That one is genuinely falsifiable — build a physical device that computes something uncomputable, a real hypercomputer, and the thesis is dead. Notably, quantum computers do not do this; they compute the same functions a Turing machine can, sometimes dramatically faster, which is a claim about efficiency, not about computability. Deutsch's 1985 work put this physical version on the map, and it earns respect precisely because it takes a risk.

The same discipline applies to minds. That computation is a powerful lens for cognition — the computational theory of mind — is a productive research program. That the brain literally is nothing but computation is a contested philosophical position, not a theorem. Multiple-realizability, the good idea that one function can run on different hardware, does not license the leap to "biology and mind are only computation." A lens that reveals a great deal is not the same as a claim that reality is made of the lens.

Conclusion

The version of "computation is universal and fundamental" that you can actually defend is the one the course teaches: model-independence, absolute uncomputability, the hidden equivalence of hard problems, and the open question of P versus NP. As a developer this is worth internalizing, because it tells you which walls are permanent — uncomputable problems, and almost certainly NP-hard ones — and which are merely current.

The grander story, that reality itself is computation, is worth reading with one question in hand: does this version make a risky prediction, or is it a metaphor elastic enough to absorb any result? The physical Church-Turing thesis passes that test. "The universe is a computer, full stop" usually does not, and that is not a small difference.

Roughgarden's course is worth your time for exactly the reason it is easy to undersell. It stays on the solid ground and lets you see how much is genuinely there — model-independence, hard limits, deep equivalences — before anyone reaches for the cosmos.

References