오늘날 우리가 사용하는 컴퓨터, 스마트폰, 심지어 손목 위의 스마트워치는 겉모습과 크기가 천차만별이지만, 근본적으로는 모두 동일한 원리로 움직입니다. 메모리에서 데이터를 읽고, 정해진 규칙에 따라 연산한 뒤, 다시 결과를 저장하는 과정입니다.
그렇다면 "컴퓨터란 정확히 무엇인가?" 혹은 "기계가 계산할 수 있는 문제와 영원히 계산할 수 없는 문제의 경계는 어디인가?"라는 질문을 던져본 적이 있으신가요?
1930년대 중반까지만 해도 '컴퓨터'라는 단어는 기계가 아니라 계산을 직업으로 삼는 인간 계산원을 뜻했습니다. 이 관념을 완전히 깨부수고, 복잡한 톱니바퀴나 정밀 부품 하나 없이 오직 종이 테이프와 연필이라는 단순한 상상 속 장치만으로 현대 소프트웨어와 범용 컴퓨터의 수학적 정의를 완성한 인물이 바로 영국의 천재 수학자 앨런 튜링(Alan Turing)이었습니다.
난공불락의 수학적 질문: 결정 문제의 벽
1936년, 스물네 살의 청년 튜링은 당대 수학계를 뒤흔들던 거대한 난제와 마주했습니다. 독일의 위대한 수학자 다비트 힐베르트가 던진 '결정 문제(Entscheidungsproblem)'였습니다.
질문의 핵심은 단순했습니다. "어떤 수학적 명제가 주어졌을 때, 그것이 참인지 거짓인지를 기계적인 절차(알고리즘)를 따라 단계적으로 판별해 낼 수 있는 만능 공식이 존재하는가?"
이 질문에 답하기 위해서는 먼저 '기계적인 계산 절차'가 도대체 무엇인지를 엄밀하게 정의해야만 했습니다. 당시 사람들은 기계식 계산기를 떠올리며 톱니바퀴의 회전이나 물리적 레버를 생각했지만, 튜링은 물질의 형태에 얽매이지 않고 계산이라는 행위의 본질만을 극단적으로 추상화했습니다.
무한한 테이프와 헤드: 튜링 머신의 네 가지 요소
튜링은 인간 계산원이 격자무늬 공책에 숫자를 적고 지우며 계산하는 모습을 머릿속으로 단순화했습니다. 그렇게 탄생한 사고 실험 모델이 바로 '튜링 머신(Turing Machine)'입니다.
튜링 머신은 물리적으로 만들어진 기계가 아니라, 오직 네 가지 요소로 구성된 가상의 수학적 기계였습니다:
무한한 길이의 테이프: 일정한 크기의 칸(셀)들로 나뉘어 양옆으로 끝없이 뻗어 있는 종이 테이프입니다. 현대 컴퓨터의 '메모리(RAM)'에 해당합니다.
읽기/쓰기 헤드: 테이프의 특정 칸 하나를 가리키며, 그 칸에 적힌 기호를 읽거나 새 기호를 덮어쓰고, 테이프를 왼쪽이나 오른쪽으로 한 칸씩 움직일 수 있는 장치입니다.
상태 기록기: 기계가 현재 어떤 상태(State)에 있는지를 나타내는 작은 표시판입니다. '준비', '덧셈 중', '종료'처럼 유한한 개수의 상태 중 하나를 가집니다.
동작 규칙표(전이 함수): "만약 현재 상태가 A이고 읽은 기호가 1이라면, 기호를 0으로 바꾸고 테이프를 오른쪽으로 한 칸 옮긴 뒤 상태를 B로 바꾸어라"와 같이 적힌 규칙 목록입니다. 이것이 바로 현대 컴퓨터의 '프로그램(알고리즘)'입니다.
놀랍게도 튜링은 이 단순한 네 가지 요소만 갖추면, 덧셈과 곱셈은 물론이고 인간이 논리적으로 풀어낼 수 있는 모든 수학적 계산을 완벽하게 흉내 낼 수 있음을 수학적으로 증명해 냈습니다.
기계 하나로 모든 기계를 대신하다: 보편 튜링 머신
튜링 머신의 진정한 혁신은 '보편 튜링 머신(Universal Turing Machine, UTM)'이라는 개념에서 폭발했습니다.
이전까지 인류가 만든 모든 계산 도구는 특정한 한 가지 목적을 위해서만 존재했습니다. 덧셈 계산기는 덧셈 톱니바퀴로 만들어졌고, 직조기는 직조 전용 기계였습니다. 다른 계산을 하려면 기계 자체를 완전히 새로 조립해야 했습니다.
그러나 튜링은 기발한 역발상을 내놓았습니다. "동작 규칙표 자체를 기호로 변환하여 테이프에 데이터처럼 적어두면 어떨까?"
보편 튜링 머신은 테이프에 적힌 규칙(프로그램)을 읽어 들여, 그 규칙이 지시하는 가상의 튜링 머신인 척 스스로를 둔갑시킵니다. 체스 게임 규칙을 테이프에 적어 넣으면 체스 기계가 되고, 세금 계산 규칙을 적어 넣으면 장부 정리 기계로 변신하는 것입니다.
하드웨어는 단 하나만 고정해 두고, 테이프에 어떤 프로그램을 입력하느냐에 따라 무한한 역할을 수행하는 '현대 범용 소프트웨어 컴퓨터'의 청사진이 여기서 완벽하게 정립되었습니다.
기계가 결코 풀 수 없는 문제: 정지 문제의 한계
튜링은 자신의 기계를 바탕으로 힐베르트의 결정 문제를 통쾌하게 격파했습니다. 바로 컴퓨터 과학 역사상 가장 유명한 '정지 문제(Halting Problem)'입니다.
"어떤 임의의 프로그램과 입력값이 주어졌을 때, 이 프로그램이 계산을 언젠가 끝마치고 멈출지(정지), 아니면 영원히 무한 루프에 빠져 헛돌지를 사전에 100% 완벽하게 판별해 주는 검사 프로그램을 만들 수 있을까?"
튜링은 귀류법을 통해 이러한 만능 검사 프로그램은 수학적으로 결코 존재할 수 없음을 증명했습니다. 만약 그런 판별 기계가 존재한다고 가정하면, 그 기계의 판단을 정반대로 뒤집는 역설적인 프로그램을 만드는 순간 논리적 모순이 발생하기 때문입니다.
결국 기계가 수행하는 알고리즘에는 논리적으로 풀 수 없는 명백한 한계가 존재한다는 사실이 밝혀졌습니다. 컴퓨터가 신적인 전지전능함을 가질 수는 없다는 사실을, 컴퓨터의 개념이 탄생하던 바로 그 순간에 튜링이 못 박아 둔 셈입니다.
종이 위의 수식이 실리콘으로 살아나다
튜링 머신은 금속 톱니나 구리 전선으로 만들어진 물리적 장치가 아니었습니다. 그러나 그것은 기계식 장치의 마찰과 오차에 갇혀 있던 인간의 연산을 순수한 논리의 영역으로 끌어올렸습니다.
0과 1이라는 단순한 기호의 나열, 상태의 변화, 그리고 메모리를 오가는 헤드의 움직임만으로 세상의 모든 정보 처리를 설명할 수 있다는 그의 통찰은 이후 폰 노이만과 에커트, 모클리 같은 공학자들에게 직접적인 설계 지침이 되었습니다.
오늘날 우리가 브라우저를 열고, 문서를 편집하며, 게임을 즐기는 모든 순간은 90년 전 앨런 튜링이 머릿속으로 무한히 풀려나가는 종이 테이프 위에 0과 1을 새겨 넣으며 꿈꾸었던 가상 기계의 규칙 안에서 한 치의 오차도 없이 실행되고 있습니다.
핵심 요약
앨런 튜링은 수학적 결정 문제를 풀기 위해 계산이라는 행위를 무한한 테이프, 헤드, 상태, 규칙표로 단순화한 '튜링 머신'을 고안했습니다.
테이프에 규칙 자체를 데이터로 기록해 어떤 기계로든 변신할 수 있는 '보편 튜링 머신'은 현대 범용 컴퓨터와 소프트웨어의 개념적 모태가 되었습니다.
프로그램이 무한 루프에 빠질지 사전에 판별할 수 없다는 '정지 문제'의 증명을 통해 알고리즘이 가진 수학적 한계를 명확히 규명했습니다.
0 댓글