여러분은 컴퓨터를 어떻게 이용하시나요? 우리는 게임을 하거나, 발표 준비를 한다거나, 궁금한 것을 검색하고 싶을 때는 어김없이 컴퓨터를 활용해요. 컴퓨터로 할 수 있는 일은 무수히 많으니까요.

조금 이상하지 않나요? 우리 주변 대부분의 기계들은 한 가지 기능만을 갖추고 있어요. 청소기는 청소를 하고, 세탁기는 빨래를 하죠. 에어컨은 우리를 시원하게 하고, 식기세척기는 설거지를 해줘요. 하지만 컴퓨터만이 너무 많은 기능을 가지고 있죠.

사실 컴퓨터도 단 하나의 역할만을 수행하기 위해 탄생했어요. 바로 ‘계산’이죠.

컴퓨터라는 명칭은 ‘계산하다’라는 뜻을 가진 라틴어 ‘콤푸라레’(Computare)에서 유래되었다.

우리가 컴퓨터를 통해 하는 모든 일들은 사실 모두 계산이에요. 컴퓨터는 계산이라는 단 하나의 기능만을 수행하는 기계니까요. 검색 엔진과 카카오톡, 심지어 배틀그라운드도 컴퓨터가 하는 계산의 일종이라는 거에요.

조금 혼란스럽죠? 우리 우선 계산이 무엇인지에 대해 알아봐요.

계산 그 자체, 튜링 머신 🎰

우리가 만약 컴퓨터의 아버지 앨런 튜링에게 “계산이 뭐에요?” 라고 묻는다면, 그는 분명 이렇게 대답할 거에요.

“계산이란 컴퓨터가 할 수 있는 일이다”

컴퓨터는 계산을 하는 기계인데, 계산이 컴퓨터가 할 수 있는 일이라니. 이렇게 보면 단순한 말장난 같은데요. 튜링의 대답은 가상의 기계, 튜링머신을 통해 이해할 수 있어요.

1936년, 튜링은 「결정 문제에 대한 적용과 관련한 계산 가능한 수에 관하여」라는 논문을 발표했어요. 이 논문에서 튜링은 현대 컴퓨터의 최초 모델을 설계했는데, 그것이 바로 ‘튜링 머신’이죠. 튜링 머신은 긴 테이프에 쓰인 여러 기호들을 일정한 규칙에 따라 바꾸는 기계에요. 이렇게만 보면 어떤 기계인지 잘 감이 안잡히죠?

튜링 머신은 네 가지 요소로 이루어져 있어요.

먼저, 0이나 1로만 이루어진 테이프에 헤드를 위치시켜요. 헤드는 튜링 머신의 현재 상태와 작동 규칙 표에 따라 테이프 위를 움직이고, 0을 1로 혹은 1을 0으로 바꾸기도 해요.

이게 튜링 머신의 작동 원리 전부입니다. 굉장히 간단하죠?

보다 구체적인 이해를 위해 튜링 머신을 활용하여 ‘3+1=4’라는 간단한 계산을 함께 해보죠.

위 튜링 머신은 주어진 데이터에 1을 더하는 튜링 머신이에요. 이를 ‘+1 튜링머신’이라고 해보죠. 우리는 또한 테이프에 3을 기록했어요. 튜링 머신이 알아들을 수 있게 3개의 1로 말이죠. 자, 이제 튜링머신을 작동시켜 봅시다!

헤드는 작동 규칙 표에 따라 행동한다는 거 기억하죠? 그럼 이제 작동 규칙 표의 첫 번째 줄을 해석해 보죠.

“튜링 머신의 현재 상태가 A일 때 0을 만난다면 오른쪽으로 이동하고 상태를 A로 유지해라”

현재 상태가 A이니까, 헤드를 오른쪽으로 한 칸 이동시키면 되겠네요! 다음 칸에 적힌 숫자도 0이니, 한번 더 오른쪽으로 이동하면 되겠어요.

헤드를 두 번 이동시키니 기호 1을 만났어요. 상태가 A일 때 기호 1을 만난다면 해야할 행동은 작동 규칙 표 두 번째 줄에 정리되어 있군요!

“튜링 머신의 현재 상태가 A일 때 1을 만난다면 오른쪽으로 이동하고 상태를 B로 바꿔라”

작동 규칙 표에 따라 이동하면, 튜링 머신의 상태는 아래 그림과 같아집니다.

현재 상태가 B일 때 1을 만났으므로, 작동 규칙 표의 세 번째 규칙을 따라야 할 것 같아요!

“튜링 머신의 현재 상태가 B일 때 1을 만난다면 오른쪽으로 이동하고 상태를 B로 유지해라”

 기록기가 처음 1을 만난 후에도 테이프에는 두 개의 1이 더 적혀있으니, 작동 규칙표에 따라 B의 상태를 유지한 채 오른쪽으로 이동합니다.

마침내 우리의 목표 지점에 도달했어요. B의 상태에서 0을 만났으니, 마지막으로 네 번째 규칙을 따라볼까요?

“튜링 머신의 현재 상태가 B일 때 0을 만난다면 0을 1로 바꾸고 오른쪽으로 이동해라. 상태는 A로 바꾸고, 작동을 멈춘다”

튜링 머신은 세 개의 1 옆에 위치한 0을 1로 바꿈으로써 3+1=4라는 덧셈 계산을 완벽하게 수행했네요! 이제 튜링 머신이 어떻게 작동하는지 확실히 알았죠?

계산의 정의에 대해 이야기하는데 왜 자꾸 튜링 머신만 설명하냐구요? 왜냐면 튜링이 이 튜링 머신을 통해서 계산을 정의했거든요. 튜링머신이 작동하는 과정, 그 자체가 바로 ‘계산’이라는 것이죠.

계산 = 튜링 머신

우리가 예시로 본 간단한 덧셈뿐만 아니라 곱셈, 미분, 적분, 더 나아가 검색, 배틀그라운드 등등은 전부 이러한 방식으로 수행될 수 있어요. 물론 배틀그라운드를 실행하는 튜링 머신의 작동 규칙 표는 어마어마하게 길고 복잡하겠지만요.

현재 우리가 사용하는 컴퓨터는 전부 튜링 머신의 원리를 바탕으로 만들어졌어요. 그렇다면 이제 튜링의 대답이 이해가 가죠?

“계산이란 컴퓨터가 할 수 있는 일이다”

계산이란 튜링 머신이 하는 일, 그 자체인데, 컴퓨터가 튜링 머신을 바탕으로 만들어졌으니 계산이란 컴퓨터가 할 수 있는 일이 되는 것이죠.

그런데 여기서 한 가지 의문이 들어요. 우리가 예시로 본 ‘+1 튜링 머신’은 주어진 값에 1을 더하는 한 가지 계산밖에 하지 못해요. 그런데 우리는 컴퓨터로 검색도 하고, 게임도 하고, 시간도 확인하지 않나요? 검색과 게임, 전화가 하나의 계산이라면 컴퓨터라는 튜링 머신이 최소한 세 가지 계산을 할 수 있어야 해요. 어떻게 이런 일이 가능한 것일까요?

1. 두 가지 튜링 머신의 작동 규칙 표를 보편 튜링 머신이 이해할 수 있도록 숫자 코드로 변환한다.
2. 다른 튜링 머신의 숫자 코드를 테이프에 차례로 적어둔다.
3. 보편 튜링 머신의 헤드가 이를 읽고 숫자 코드에 해당하는 튜링 머신을 흉내내어 계산을 수행한다.

그림을 보면 더 이해하기 쉬울 거에요.

보편 튜링 머신의 작동 규칙 표는 보편 튜링 머신으로 하여금 숫자 코드로 쓰여진 다른 튜링 머신을 흉내내도록 해요. 보편 튜링 머신의 헤드가 ‘+1 튜링 머신’의 숫자 코드를 읽으면, 보편 튜링 머신은 잠시동안 데이터의 1을 더하는 튜링 머신이 되는 거죠. 그 상태로 뒤이어 적힌 ‘3’에 1을 더하는 계산을 수행하는 거에요.

하지만 여기서 그치지 않아요. 헤드가 이동하며 ‘‘×3 튜링 머신’의 숫자 코드를 읽으면, 보편 튜링 머신은 다시 데이터의 3을 곱하는 튜링 머신으로 탈바꿈해요. 그 상태로 ‘2’에 3을 곱하는 계산을 수행하는 것이죠.

어때요, 이해가 가나요?

정리하자면, 보편 튜링 머신은 헤드가 어떤 숫자 코드를 읽느냐에 따라 어떤 튜링 머신이든 될 수 있다는 거예요. 이런 원리로 다양한 계산을 연속적으로 수행하는 것이 가능한 거죠.

이제 우리가 어떻게 컴퓨터 하나로 그렇게 많은 일을 할 수 있는지 잘 알았죠?

정리 📝

지금까지의 내용을 정리하자면,

‘계산’은 ‘튜링 머신’의 작동 방식이며, 모든 현대 컴퓨터는 보편 튜링 머신의 작동 방식을 따른다

정도가 되겠네요.

드디어 우리 맨 처음 질문에 대한 답을 찾을 수 있게 되었어요.

‘최초의 컴퓨터는 배틀그라운드를 실행시킬 수 있는가’

힌트는 바로 ‘보편 튜링 머신’이에요. 80년 전 최초의 컴퓨터 z3든, 최신형 슈퍼컴퓨터든 간에 모든 현대적 컴퓨터는 ‘보편 튜링 머신’의 방식으로 작동해요. 최초의 컴퓨터든 슈퍼컴퓨터든 할 수 있는 계산은 완전히 똑같다는 것이죠.

결국 우리가 궁금했던 배틀그라운드도 현재 우리 집 컴퓨터에서 실행할 수 있다면, 80년 전 구식 컴퓨터로도 실행할 수 있는 것이랍니다! 로딩에는 1억년쯤 걸리겠지만요.

마무리

이번 레터에서는 튜링이 정의한 계산과 튜링 머신에 대해서 알아봤어요. 평소에 생각하던 계산과는 조금 다르죠? 언제나 유익한 시간이 되었길 바라요. 더 궁금한 점이 있다면 아래 피드백 란에 남겨주세요! 다음 콘텐츠 주제에 대한 요청도 언제나 환영이랍니다~😝