[Chapter 1] Welcome Abroad - 튜링 머신과 추상화

컴퓨터 공학에 있어 위대한 업적을 남긴 인물을 꼽아야 한다면, 누군가는 앨런 튜링이라는 인물을 떠올릴 것이다. 그런 의미에서 앨런 튜링이라는 인물이 고안해낸 튜링 머신에 대한 개념을 간단히라도 알고 넘어갈 필요가 있다. 또한 컴퓨터 공학도라면 반드시 알고 있어야 하는 추상화라는 개념도 제대로 이해하는 것이 중요하다. 추상화는 컴퓨터 공학뿐 아니라 모든 공학 분야에서 급격한 기술의 진보를 이끌어 낸 핵심적인 아이디어라 말해도 과언이 아닐 것이다.

 

1. 튜링 머신 (Turing Machine)

1-1. 튜링 머신 (Turing Machine)

튜링 머신에 대해 본격적으로 알아보기 전에, 기본적으로 알고 있어야 할 배경지식이 있다. 모든 컴퓨터들은, 그것이 핸드폰 단말기이든 일반 PC이든 슈퍼 컴퓨터이든, 충분한 시간과 메모리만 주어진다면 정확히 똑같은 것들을 계산해낼 수 있다는 것이다. 다만 현실에서는 기기마다 처리 속도와 메모리 용량이 다르기에 같은 것을 계산하더라도 계산 속도가 다를 뿐이다. 

 

이러한 아이디어를 기억한 상태로 튜링 머신을 한 번 바라보자. 튜링 머신이란 '어떠한 연산이든 수행 가능한 장치의 수학적 모델'을 의미하며, 1937년에 앨런 튜링이라는 사람에 의해 고안되었다. 수학적 모델이라는 것은 쉽게 말해서 현실에 존재하는 실제 장치가 아니라 머릿속에서만 고안해낸 가상의 이론적 장치임을 의미한다. 또한 어떠한 연산이든 수행 가능하다는 말은, 어떠한 종류의 연산(덧셈, 뺄셈, 혹은 훨씬 더 복잡한 임의의 연산)을 떠올리든 그 연산을 수행할 수 있는 튜링 머신이 존재함을 의미한다. 이쯤에서 위에서 설명한 배경지식을 떠올려 보자. 튜링 머신에서 중요한 건 '어쨌든 계산이 가능하다'는 것이지, 그 계산을 수행하는 '속도'나 '성능'이 아니다.

 

그러면 튜링 머신은 어떻게 동작하길래 어떠한 연산이든 수행이 가능하다는 것일까? 하지만 아쉽게도 이는 본 포스팅의 범위를 넘어서는 내용이다. 호기심 가득한 독자를 위해 간단히만 동작 원리를 소개하겠으나, 자세한 내용은 오토마타 이론을 직접 공부해서 알아보기를 권장한다.

 

※ 튜링 머신의 동작 방식

매 순간 특정 상태에 놓여 있는 튜링 머신은, 무한한 길이의 테이프 위에 있는 문자들을 하나씩 읽으면서 동작하게 된다. 한 문자를 읽고 나면 현재 상태를 무엇으로 바꿀지, 읽은 문자의 왼쪽으로 움직일지 오른쪽으로 움직일지, 읽은 문자가 쓰여 있던 곳에 무슨 문자를 새로 써줄지를 결정한다. 즉, 현재 상태와 현재 읽고 있는 문자에 대해 다음 상태, 움직이는 방향, 새로 쓸 문자를 모두 정의해주고, 종료 상태(튜링 머신이 더 이상 동작하지 않고 동작을 종료하게 되는 상태)가 무엇인지까지만 정의해주면 그 튜링 머신의 동작 방식이 완전히 결정되는 것이다. 이는 프로그램의 코드가 무엇인지에 따라 해당 프로그램의 동작 방식이 완전히 결정되는 것과 마찬가지이다.

---

1-2. 범용 튜링 머신 (Universal Turing Machine)

튜링 머신의 확장된 개념으로, '모든 튜링 머신들을 구현하고 실행시킬 수 있는 또 하나의 튜링 머신'을 의미한다. 이게 무슨 말일까? 일반적인 튜링 머신은 입력값을 받고 그것을 가지고 연산을 수행한 뒤 결괏값을 내놓는다. 여기서 중요한 아이디어가 하나 있다. 바로 튜링 머신 자체도 그 동작 방식을 코드로 정의하기 때문에 그 코드에 해당하는 문자열을 입력값으로 튜링 머신에 넣을 수 있다는 것이다. 즉 범용 튜링 머신이란 튜링 머신(의 동작 방식을 정의하는 코드)과 일반적인 입력값을 입력으로 받아서 연산을 수행할 수 있는 튜링 머신을 의미한다. 다음 그림을 보자.

 

▲ 덧셈을 수행하는 튜링 머신, 곱셈을 수행하는 튜링 머신, 일반적인 입력값(a, b, c)를 범용 튜링 머신 U에 입력시키고 있다.

 

범용 튜링 머신에는 중요한 특성이 하나 있다. 바로 '프로그래밍이 가능하다(Programmable)'는 것이다. 즉, 원하는 튜링 머신과 입력값을 넣어줌으로써 내가 원하는 동작을 수행하게끔 프로그래밍 가능하다는 것이다. 뭔가 익숙하지 않은가? 그렇다. 이렇게 가상의 이론적 장치로만 생각하던 범용 튜링 머신을 실제로 구현한 것이 바로 오늘날의 컴퓨터이다. 컴퓨터는 범용 튜링 머신에 대응하고, 우리가 컴퓨터의 메모리에 집어넣어 동작하도록 하는 프로그램은 범용 튜링 머신에 입력되는 튜링 머신에 대응하는 것이다.

 

2. 추상화 (Abstraction)

2-1. 추상화 (Abstraction)

추상화는 공학도로서 꼭 알고 있어야 하는 아주 중요한 아이디어이다. 필자 나름대로 쉽게 정의하자면, 추상화는 '내부적인 자세한 내용들은 숨겨두고 핵심적인 내용들만 드러내어 복잡성은 최소화하고 효율성은 향상시키는 기법'이다. 예를 들어, 우리는 자동차의 핸들을 오른쪽으로 돌리면 차가 오른쪽으로 움직인다는 사실을 알고 있다. 그러나 자동차의 핸들을 오른쪽으로 돌릴 때 자동차 내부적으로 무슨 일이 일어나는지는 잘 알지 못한다. 만약 그런 것까지 알아야 한다면 누가 자동차를 쓰겠는가? 운전자에게 필요한 것(핸들을 오른쪽으로 돌리면 오른쪽으로 움직인다)만 드러냄으로써 차를 사용하는 사람에게 복잡한 내용은 감추고 사용의 편의를 증진시키는 것이다.

 

이제 우리가 공부할 내용에 추상화를 적용시켜 보자. 지난 포스팅에서는 CPU를 이루는 가장 작은 단위의 부품으로서 MOS 트랜지스터를 알아보았고, 그보다 한층 윗단계의 부품으로서 게이트까지 알아보았다. 우리는 이렇게 한 단계 한 단계 위로 올라가면서 CPU가 어떻게 만들어지는지 이해함으로써, 프로그램의 실행이 컴퓨터 내부적으로 어떠한 원리에 의해 이뤄지는지까지 알아볼 것이다. 그 과정에서 추상화는 매우 중요하다. 왜일까?

 

MOS 트랜지스터의 구체적인 동작 원리를 이해했다면, 우리는 이제 MOS 트랜지스터가 1과 0의 신호에 따라 스위치처럼 동작한다는 사실만 기억하면 된다. 또한 OR 게이트가 MOS 트랜지스터로 어떻게 구현되었는지 이해했다면, 이제 OR은 1의 신호가 하나라도 입력되면 1의 신호를 출력하는 게이트라는 사실만 기억하면 된다. 즉 차례차례 추상화를 하며 윗단계로 올라가는 것이다. 인간은 개념의 복잡성을 견뎌내는 능력에 한계가 있기에, 복잡성을 최소화시키고 효율적인 발상을 하기 위해 추상화가 반드시 필요하다.

---

2-2. 우리가 공부하게 될 추상화 계층 (Abstraction Layer)

우리는 아래 그림에서 설명하는 단계로 차례차례 추상화하며 공부해 나갈 것이다. 화살표가 의미하듯, 위로 올라갈수록 추상화 단계가 높아진다고 생각하면 된다. 각 단계에 대한 설명은 그 아래의 표에 나타나 있다.

 

 

추상화 단계	의미
Problems	우리가 풀고자 하는 현실의 문제를 의미한다. EX) 여러 숫자들을 크기 순서대로 정렬
Algorithms	문제를 풀기 위해 사용하는 알고리즘(혹은 자료구조)을 의미한다. EX) 퀵 정렬, 버블 정렬
Language	알고리즘을 구현하는 데 사용하는 프로그래밍 언어를 의미한다. EX) C 언어 (고급 언어), 어셈블리어 (저급 언어)
Instruction Set Architecture (ISA)	컴퓨터가 이해할 수 있는 0과 1로 이루어진 기계어 체계를 의미한다. EX) Intel x86
Microarchitecture (Processor, CPU)	특정 ISA의 명령어를 읽고 해석하여 동작하는 장치를 의미한다. EX) Pentium 4
Circuits	CPU를 구현하는 데 사용되는 논리 회로들을 의미한다. EX) Carry-lookahead adder (덧셈을 수행하는 논리 회로의 한 종류)
Devices	논리 회로들을 구현하는 데 사용되는 작은 부품들을 의미한다. EX) MOS 트랜지스터, 게이트

 

※ Instruction Set Architecture (ISA)

CPU가 이해할 수 있는 0과 1로 이루어진 기계어 체계를 말한다. 그리고 이러한 기계어를 인간이 쉽게 이해할 수 있도록 바꾼 언어가 바로 프로그래밍 언어이다. ISA도 어찌 됐든 CPU가 이해할 수 있는 언어여야 하므로 합의된 체계와 규칙을 가지고 있다. 물론 ISA마다 그 체계와 규칙이 다르다. 예를 들어 명령어의 종류와 개수, 자료형의 종류와 개수, 번지지정방식의 종류와 개수가 각기 다르다. 한편 ISA의 체계와 규칙을 이해하면 인간이 컴퓨터로 하여금 원하는 동작을 수행하게끔 할 수 있다는 측면에서, ISA를 인간과 컴퓨터 사이의 인터페이스라고 부르기도 한다.

 

※ Microarchitecture (Processor, CPU)

특정 ISA의 명령어를 읽고 해석하여 해당 명령어가 요구하는 동작을 수행하는 물리적인 장치를 의미한다. 각 CPU는 딱 하나의 ISA만 이해가 가능하도록 설계가 되지만, 서로 다른 CPU가 동일한 ISA를 사용할 수는 있다. 그러나 동일한 ISA를 이해하는 CPU라 하더라도 구현 방식이 다르다면 비용, 성능, 전력 소모 등의 특성에서 차이가 나게 된다. 이건 마치 모델이 각기 다른 여러 자동차들의 경우 자동차 안에서 보이는 기본적인 인터페이스(브레이크, 전진/후진 기능, 좌/우회전)는 같지만 제조사마다 비용, 성능, 전력 소모의 정도가 조금씩 다른 것과 마찬가지이다.

 

※ Circuits, Devices

여기서도 CPU와 동일하게 성능, 비용, 전력 소모의 측면에서 저울질이 존재한다. 값이 나가도 더 빠르게 덧셈을 수행할 수 있는 논리 회로를 사용하느냐, 아니면 덧셈 작업이 조금 느려도 저렴한 논리 회로를 사용하느냐의 문제를 예로 들 수 있다.