앨런 튜링(Alan Turing)은 1과 0으로 이루어진 스트림을 처리하는 기계가 '어떤 문제든' 해결할 수 있다고 증명한 적은 없습니다. 흔히 오해하기 쉬운 부분이지만, 튜링이 입증한 것은 그보다 더 정교하고 중요한 내용입니다.
1936년, 튜링 머신의 탄생
앨런 튜링은 1936년에 발표한 논문 『계산 가능수와 결정문제에의 응용(On Computable Numbers, with an Application to the Entscheidungsproblem)』에서, 계산 가능한(computable) 모든 연산을 수행할 수 있는 이론적 계산 장치를 소개했습니다. 바로 오늘날 우리가 아는 튜링 머신(Turing Machine)입니다.
튜링 머신이란?
튜링 머신은 무한한 길이의 테이프에 기호를 읽고 쓰며 단순한 규칙에 따라 동작하는 가상의 계산 모델입니다. 이 모델은 다음과 같은 핵심 통찰을 제공했습니다.
- 보편성(Universality): 하나의 튜링 머신이 다른 모든 튜링 머신의 동작을 흉내 낼 수 있습니다. 이것이 현대 범용 컴퓨터의 이론적 토대가 되었습니다.
- 계산의 한계: 튜링은 동시에 '풀 수 없는 문제'도 존재함을 보였습니다. 대표적인 예가 정지 문제(Halting Problem)로, 임의의 프로그램이 종료되는지를 판별하는 일반적 방법은 존재하지 않습니다.
현대 컴퓨터 과학에 남긴 유산
튜링의 1936년 논문은 디지털 컴퓨터의 이론적 기초를 확립한 걸작으로 평가받습니다. 오늘날 우리가 사용하는 모든 컴퓨터와 프로그래밍 언어는 '튜링 완전(Turing Complete)'이라는 개념 위에서 작동하며, 이는 곧 튜링 머신과 동등한 계산 능력을 지녔다는 의미입니다.
요약하자면, 튜링은 1과 0을 처리하는 기계가 만능이라고 선언한 것이 아니라, 무엇이 계산 가능하고 무엇이 불가능한지를 정의함으로써 컴퓨터 과학이라는 학문의 초석을 놓았습니다.
