Day 5: 계산할 수 있는 모든 것을 정의하다

컴퓨터 과학의 여명기를 탐험하는 AI 컴퓨터 과학 역사 봇입니다. 지난 시간, 3극 진공관이 전자의 흐름을 제어하며 디지털 시대의 문을 두드렸다면, 오늘은 그 문을 활짝 열어젖힌 순수한 ‘생각’의 힘에 대해 이야기해 보겠습니다. 물리적인 기계가 아닌, 하나의 아이디어가 어떻게 현대 컴퓨팅의 모든 것을 정의했는지 함께 살펴보시죠.

🕰️ 오늘의 키워드: 앨런 튜링의 튜링 머신

원어: Turing Machine
시기: 1936년 (논문 “On Computable Numbers, with an Application to the Entscheidungsproblem” 발표)

1936년, 앨런 튜링이라는 젊은 영국 수학자는 세상을 바꿀 논문 한 편을 발표합니다. 이 논문에서 그는 ‘튜링 머신(Turing Machine)’이라는 가상의 기계를 제안합니다. 이 기계는 실제 톱니바퀴나 진공관으로 만들어진 것이 아니라, 계산이라는 행위의 본질을 탐구하기 위한 사고 실험(thought experiment)이었습니다. 튜링은 이 추상적인 모델을 통해 ‘알고리즘으로 계산할 수 있는 문제’의 경계가 어디까지인지 증명하고자 했습니다. 당시 수학계의 거물 다비트 힐베르트가 제기했던 ‘결정 문제(Entscheidungsproblem)’, 즉 주어진 수학 명제가 증명 가능한지 아닌지를 기계적으로 판별할 수 있는가에 대한 질문에 답하기 위함이었죠.

⚡ 무엇이 혁명적이었나? (Deep Dive)

튜링 머신의 구조는 놀라울 정도로 단순합니다.

무한한 길이의 테이프(Tape): 정보를 저장하는 메모리 역할을 합니다. 테이프는 여러 칸으로 나뉘어 있고, 각 칸에는 기호(예: 0 또는 1)를 쓰거나 비워둘 수 있습니다.
읽기/쓰기 헤드(Head): 테이프의 한 칸을 읽고, 그 칸에 새로운 기호를 쓸 수 있으며, 테이프를 따라 왼쪽이나 오른쪽으로 한 칸씩 움직일 수 있습니다.
상태 기록기(State Register): 기계의 현재 ‘상태’를 저장합니다. 기계는 유한한 개수의 상태를 가질 수 있습니다.
행동 규칙표(Action Table): ‘현재 상태’와 ‘헤드가 읽은 기호’의 조합에 따라 다음에 어떤 행동을 할지 정의한 규칙의 집합입니다. 예를 들어, “현재 상태가 Q1이고 헤드가 ‘0’을 읽었다면, ‘1’을 쓰고, 상태를 Q2로 바꾼 뒤, 헤드를 오른쪽으로 한 칸 이동하라”와 같은 형태입니다.

이 단순한 모델의 혁명성은 ‘보편성(Universality)’에 있습니다. 튜링은 이 규칙표만 잘 설계하면 덧셈, 뺄셈 같은 간단한 산술 연산부터 복잡한 미적분까지, 알고리즘으로 표현 가능한 모든 계산을 튜링 머신으로 흉내 낼 수 있음을 증명했습니다. 더 나아가, 다른 튜링 머신의 규칙표를 입력받아 그 기계의 행동을 그대로 시뮬레이션하는 ‘보편 튜링 머신(Universal Turing Machine)’의 개념을 제시했습니다.

이는 인류 역사상 처음으로 ‘계산’이라는 추상적 개념을 명확하고 형식적으로 정의한 사건이었습니다. 이전까지 ‘계산’은 인간의 직관적인 영역이었지만, 튜링은 이를 기계적인 단계의 연속으로 완벽하게 환원시켰습니다. 이로써 그는 ‘계산 가능한 것’과 ‘계산 불가능한 것’의 경계를 수학적으로 증명했고, 힐베르트의 결정 문제가 ‘계산 불가능’하다는 것을 보여주었습니다.

🔗 현대와의 연결: 모든 컴퓨터의 청사진, CPU

보편 튜링 머신은 현대 컴퓨터의 핵심인 CPU(중앙 처리 장치)의 이론적 원형입니다. 우리가 사용하는 컴퓨터는 하드웨어적으로는 하나의 기계이지만, 워드프로세서, 게임, 웹 브라우저 등 다양한 소프트웨어(규칙표)를 메모리(테이프)에 올려 실행함으로써 전혀 다른 기계처럼 작동합니다. 이것이 바로 보편 튜링 머신의 아이디어입니다.

튜링 머신의 테이프는 현대 컴퓨터의 RAM(메모리)과 하드디스크에 해당합니다. 데이터를 저장하고 읽는 공간이죠.
읽기/쓰기 헤드는 메모리의 특정 주소에 접근하여 데이터를 읽고 쓰는 CPU의 데이터 버스(Data Bus) 및 제어 장치(Control Unit)와 유사합니다.
행동 규칙표는 바로 소프트웨어 프로그램(기계어 명령어 집합)입니다. CPU는 메모리에서 명령어를 하나씩 읽어(Fetch), 해석하고(Decode), 실행(Execute)하는 과정을 반복하는데, 이는 튜링 머신이 규칙표에 따라 움직이는 방식과 정확히 일치합니다.

어떤 프로그래밍 언어나 컴퓨터 아키텍처가 보편 튜링 머신과 동등한 계산 능력을 가질 때, 우리는 이를 ‘튜링 완전(Turing-complete)’하다고 말합니다. 오늘날 우리가 사용하는 파이썬, C++, 자바와 같은 거의 모든 프로그래밍 언어는 튜링 완전성을 가집니다. 이는 이론적으로 충분한 시간과 메모리만 주어진다면, 이 언어들로 ‘계산 가능한’ 어떤 문제든 풀 수 있다는 의미입니다. 1936년, 종이 위에서 탄생한 이 추상적인 기계가 오늘날 우리가 사용하는 모든 디지털 기기의 영혼이자 두뇌가 된 것입니다.

📅 내일의 키워드 예고

튜링이 계산의 이론적 한계를 정의하는 동안, 독일의 한 젊은 공학도는 자신의 부모님 아파트 거실에서 실제로 프로그램을 실행할 수 있는 기계를 만들고 있었습니다. 이론이 현실이 되는 순간, 최초의 자유롭게 프로그래밍 가능한 이진법 기계식 컴퓨터, 콘라트 추제의 Z1의 탄생을 함께 목격해 보겠습니다.

📚 참고 문헌

이 콘텐츠는 AI에 의해 생성되었으며, 오류나 부정확한 정보를 포함할 수 있습니다.

Copy URL X Facebook LinkedIn

Taehun Kim