계산만하면 계산기지 그게 컴퓨터니?

앞선 글들에서는 숫자를 0과 1로 표현해 덧셈과 뺄셈을 수행하는 회로를 구현해보았다. 만약 사진을 0과 1로 표현한다면, 그 사진을 편집할 수 있는 회로도 만들어볼 수 있을 것이다.

하지만 이런 회로들만으로는 우리가 익숙하게 사용하는 ‘컴퓨터’라고 부르기엔 어딘가 부족함이 느껴진다. 컴퓨터와 다른 도구들 사이에는 근본적인 차이가 있다. 가위는 ‘자르는 것’, 컵은 ‘담는 것’처럼 하나의 명확한 역할로 정의할 수 있지만, 컴퓨터는 이런 식으로 단순하게 정의할 수 없다. 컴퓨터에는 다른 도구들과는 다른, 더 본질적인 특성이 있는 것 같다.

그렇다면 무엇을 만들어야 컴퓨터를 만들었다고 할 수 있을까? 이 시리즈의 목표는 컴퓨터를 직접 만들어보는 것이었지만 사실 우리는 컴퓨터가 무엇인지도 명확히 정의하지 않았다. 이번 글에서는 컴퓨터가 무엇인지 정의하고 지금까지 배운 내용이 모여 어떻게 컴퓨터가 구성되는지 살펴보자.

계산의 본질을 찾아서

컴퓨터와 다른 도구들 사이의 근본적인 차이가 무엇인지 알아보려면 한 수학자의 아이디어부터 살펴봐야 한다. 영국의 앨런 튜링이 1936년에 발표한 ‘계산 가능한 수’라는 논문에서 제안한 튜링 머신이 바로 그 출발점이다.

튜링이 이 개념을 제안한 배경에는 당시 수학계의 중요한 문제가 있었다. 다비트 힐베르트가 제기한 무시무시한 이름의 ‘결정 문제(Entscheidungsproblem)‘는

주어진 수학 명제가 참인지 거짓인지를 기계적으로 판단할 수 있는가?

라는 질문이었다. 튜링은 이 문제를 해결하기 위해 먼저 ‘계산이란 무엇인가’를 정의해야 했다. 그가 택한 방법은 계산을 수행하는 가상의 기계를 설계하고, 이 기계가 수행할 수 있는 것이 곧 계산이다라고 정의하는 것이었다. 이 기계가 바로 튜링 머신이다.

튜링 머신의 구조

튜링 머신은 세 가지로 구성된다:

테이프: 기호가 적힌 긴 띠
헤드: 테이프 위의 기호를 읽고 쓰며, 좌우로 한 칸씩 이동
제어 장치: 현재 상태와 규칙에 따라 헤드의 동작을 결정

아래는 테이프의 각 비트를 반전시키는 튜링 머신이다. 재생 버튼을 눌러 동작을 확인해보자.

현재 상태	읽은 기호	다음 상태	쓸 기호	이동

초기 상태: q0 / 정지 상태: q_halt / 빈 칸: _ / 실행 전 테이프 클릭으로 값 수정 가능

규칙 세 줄만으로 비트 반전이 가능하다. 그렇다면 더 복잡한 계산은 어떨까? 아래는 이진수 덧셈을 수행하는 튜링 머신이다. 111₂ + 10₂ = 1001₂가 계산되는 과정을 확인해보자. (규칙 출처)

현재 상태	읽은 기호	다음 상태	쓸 기호	이동

초기 상태: q0 / 정지 상태: q_halt / 빈 칸: _ / 실행 전 테이프 클릭으로 값 수정 가능

읽기, 쓰기, 이동. 이 단순한 동작의 반복만으로 덧셈까지 가능하다. 튜링의 통찰은 바로 이것이었다: 이 단순한 기계로 계산 가능한 모든 것을 표현할 수 있다. 하지만 이대로면 여느 도구들과 다를 바가 없다. 비트를 반전시키거나 덧셈을 하는 특수한 도구일 뿐이다.

보편 튜링 머신

위의 튜링 머신들은 각각 비트 반전, 덧셈이라는 고정된 작업만 수행할 수 있다. 새로운 작업을 하려면 새로운 기계를 만들어야 한다.

하지만 튜링은 한 가지 더 나아간다. 테이프에 프로그램(다른 튜링 머신의 규칙들)을 적어 넣으면, 그 프로그램에 해당하는 튜링 머신처럼 동작하는 기계를 만들 수 있다. 이것이 보편 튜링 머신(Universal Turing Machine) 이다. 덧셈 규칙을 넣으면 덧셈기가 되고, 곱셈 규칙을 넣으면 곱셈기가 된다.

아래 시뮬레이터에서 제어 장치의 규칙을 직접 수정할 수 있다. 비트를 반전시키는 프로그램을 전부 0으로 만들거나 1로 만드는 프로그램으로 바꿔보자. 규칙의 쓰기 값(세 번째 열)만 바꾸면 된다.

현재 상태	읽은 기호	다음 상태	쓸 기호	이동

초기 상태: q0 / 정지 상태: q_halt / 빈 칸: _ / 실행 전 테이프 클릭으로 값 수정 가능

핵심은 기계는 그대로 두고 규칙만 바꾸면 된다는 것이다. 기계가 수행할 논리를 데이터처럼 다룰 수 있다는 이 발상이 하드웨어와 소프트웨어의 분리, 그리고 오늘날 프로그래밍의 출발점이 되었다.

컴퓨터의 정의

위키피디아에서는 컴퓨터를 이렇게 정의한다:

컴퓨터는 산술 또는 논리 연산의 일련의 과정을 자동으로 수행하도록 프로그래밍할 수 있는 기계이다.

서론에서 가위는 ‘자르는 것’, 컵은 ‘담는 것’으로 정의할 수 있지만 컴퓨터는 그렇게 정의할 수 없다고 했다. 이제 그 이유가 분명해진다. 컴퓨터의 본질은 특정 기능이 아니라 프로그램에 따라 어떤 계산이든 수행할 수 있다는 점에 있다. 지금까지 만든 회로들에 부족했던 것이 바로 이 프로그램 가능성이다.

마무리

위에서 직접 조작한 시뮬레이터도 보편 튜링 머신의 구현체다. 하지만 테이프와 헤드라는 모델은 이론적으로는 완벽해도, 실제 전자 회로로 만들기에는 적합하지 않다. 다음 글에서는 튜링의 아이디어를 논리 게이트와 회로로 실현할 수 있도록 설계된 폰 노이만 구조를 살펴보자.