파인만의 컴퓨터 강의를 읽으며 문답한 것들

『파인만의 컴퓨터 강의』를 읽으며 궁금했던 것들을 문답으로 정리했다. 책의 계산이론 부분을 이해하기 위한 메모다.

범용 튜링 기계란?

Q. 범용 튜링 기계란 무엇인가?

다른 튜링 기계의 작동 규칙과 그 기계가 처리할 입력을 받아, 그 기계의 실행을 한 단계씩 흉내 내는 튜링 기계다. 예를 들어 덧셈을 수행하는 기계의 규칙을 입력하면 덧셈 기계처럼 동작하고, 다른 기계의 규칙을 입력하면 그 기계처럼 동작한다. 범용 튜링 기계 자체의 규칙은 바뀌지 않는다.

Q. 기계를 다루는 기계인가?

그렇게 생각해도 좋다. 다만 실제 기계를 조종한다기보다, 다른 기계의 규칙을 기호로 읽고 그 동작을 모의 실행한다는 뜻이다. 기계의 규칙도 입력 데이터로 표현할 수 있다는 점이 중요하다.

Q. 그럼 무엇이든 할 수 있는 기계인가?

여기서 ‘범용’은 모든 튜링 기계를 모사할 수 있다는 뜻이다. 어떤 튜링 기계로도 해결할 수 없는 문제까지 해결한다는 뜻은 아니다. 예를 들어 임의의 프로그램이 언젠가 멈출지 모든 경우에 대해 판정하는 일은 범용 튜링 기계도 할 수 없다.

계산 가능성과 기계의 수

Q. 계산 가능성이란 무엇인가?

어떤 문제에 대해 답을 구하는 명확한 절차가 있는지를 묻는다. 예를 들어 주어진 자연수가 소수인지 판정하는 문제는 모든 입력에 대해 유한한 단계 뒤 답을 내는 절차가 있으므로 계산 가능하다. 반면 임의의 프로그램이 멈출지 항상 판정하는 문제는 계산 불가능하다.

오래 걸리는 문제와 계산 불가능한 문제는 다르다. 아무리 오래 걸려도 모든 입력에 대해 결국 정답을 내는 절차가 있으면 계산 가능하다.

Q. 튜링 기계의 집합은 가산집합인가?

그렇다. 튜링 기계 하나의 상태와 작동 규칙은 유한한 길이의 문자열로 적을 수 있다. 가능한 문자열을 길이순으로 나열한 뒤, 올바른 기계 설명을 골라내면 모든 튜링 기계를 목록에 올릴 수 있다. 서로 다른 기계도 무한히 만들 수 있으므로 튜링 기계의 집합은 가산무한집합이다.

유한상태기계와 오토마타

Q. 유한상태기계와 튜링 기계의 차이는 무엇인가?

둘 다 상태의 개수는 유한하다. 차이는 계산 도중 사용할 수 있는 기억 공간이다. 유한상태기계는 정해진 수의 상태에만 정보를 담는다. 튜링 기계는 읽고 쓸 수 있는 테이프에 표시를 남기며, 필요한 만큼 더 많은 칸을 사용할 수 있다.

Q. 000111처럼 0과 1이 세 개씩 있는지는 유한상태기계도 알아볼 수 있지 않나?

맞다. 개수가 3으로 고정되어 있다면 유한상태기계도 판별할 수 있다. 차이는 하나의 기계로 01, 0011, 000111, 00001111처럼 0이 임의의 개수만큼 나온 뒤 같은 개수의 1이 나오는 모든 경우를 처리할 수 있느냐다. 유한상태기계는 상태 수가 고정되어 있어 임의로 큰 개수를 기억할 수 없다. 튜링 기계는 테이프에 0과 1을 짝지어 표시하며 검사할 수 있다.

Q. 오토마타란 무엇인가?

입력을 읽고 정해진 규칙에 따라 상태를 바꾸는 추상적인 기계다. 단수형은 오토마톤(automaton), 복수형이 오토마타(automata)다. 유한상태기계도 오토마타의 한 종류다. 어떤 기억 장치를 쓰는지에 따라 스택을 쓰는 기계나 테이프를 쓰는 튜링 기계도 구분한다.

왜 이렇게 추상적으로 다룰까?

Q. 실제 컴퓨터보다 훨씬 추상적이라 어렵다.

실제 컴퓨터의 부품을 걷어내고 ‘무엇을 기억할 수 있으며, 그 기억으로 무엇을 할 수 있는가’만 남겼기 때문이다. 처음에는 상태는 현재 단계, 규칙은 다음 행동, 테이프는 읽고 쓰는 기억 공간으로 연결해 보면 된다.

Q. 컴퓨터공학보다 수학에 가까운 것 같다.

이 부분은 컴퓨터공학 중에서도 수학과 논리학에 가까운 계산이론이다. 실제 프로그램의 구현 방법보다, 계산이 가능한 조건과 불가능한 이유를 따진다. 기계를 단순화해야 이런 주장을 명확히 설명하고 증명할 수 있다.

Q. 그럼 계산이론의 목적은 ‘구현할 수 있나’보다 ‘원리적으로 가능한가’를 묻는 것인가?

계산 가능성을 다루는 부분에서는 그렇다. 먼저 답을 구하는 절차가 존재하는지 묻는다. 절차가 있다면 얼마나 많은 시간과 메모리가 필요한지 따지는 문제로 이어지고, 그다음 실제 컴퓨터에서의 구현을 생각할 수 있다.

엔지니어에게도 필요한가?

Q. 엔지니어도 오토마타를 알아야 할까?

기본 개념은 유용하다. 로그인 흐름, 주문 상태, 네트워크 프로토콜처럼 현재 상태와 입력에 따라 다음 행동이 달라지는 시스템을 설계할 때 도움이 된다. 모든 엔지니어가 오토마타 정리를 직접 증명하거나 튜링 기계를 설계할 필요까지는 없다.

Q. 컴파일러 개발자라면 알아야겠네?

그렇다. 소스 코드에서 키워드와 숫자 같은 토큰을 구분하는 과정은 유한상태기계로 이해할 수 있다. 괄호와 블록처럼 중첩된 구조를 분석할 때는 스택이 필요하다. 그래서 컴파일러를 공부할 때 유한상태기계, 문법, 파서의 관계가 중요하다.

메모리와 통신

Q. 메모리와 통신은 유사한가?

정보를 기록하고 다시 읽는다는 관점에서는 유사하다. 통신은 정보를 다른 곳으로 보내고, 메모리는 정보를 나중에 읽을 수 있도록 보관한다. 이를 통신은 공간을 건너 정보를 전달하고, 메모리는 시간을 건너 정보를 전달한다고 생각할 수 있다. 두 경우 모두 정보가 바뀌거나 손상될 수 있어 오류를 검출하고 고치는 방법이 중요하다.

허프만 코딩

Q. 허프만 코딩이란 무엇인가?

자주 나오는 기호에는 짧은 비트열을, 드물게 나오는 기호에는 긴 비트열을 주는 압축 방법이다. 예를 들어 A가 4번, B가 2번, C와 D가 각각 1번 나온다면 A=0, B=10, C=110, D=111로 표현할 수 있다. 기호 8개를 모두 2비트씩 쓰면 16비트가 필요하지만, 이 코드로는 14비트가 필요하다.

어느 코드도 다른 코드의 시작 부분이 아니므로 비트를 앞에서부터 읽으며 기호를 구분할 수 있다. 이런 코드를 접두어 코드라고 한다. 허프만 코딩은 출현 횟수가 가장 적은 두 기호를 차례로 묶어 나무를 만들고, 나무의 경로를 코드로 사용한다.

Q. 사용할 때 주의할 점은?

• 복원하는 쪽도 코드표를 알아야 한다. 위의 14비트는 코드표를 전달하거나 저장하는 비용을 제외한 값이므로, 짧은 데이터에서는 전체 크기가 오히려 늘 수 있다.
• 자주 나오는 기호가 짧아져 평균 코드 길이가 줄어드는 것이다. 드문 기호의 코드는 더 길어질 수 있다.
• ‘최적’은 주어진 출현 횟수에 대해 기호별 접두어 코드 중 길이가 최소라는 뜻이다. 모든 압축 방법 중 언제나 가장 작다는 뜻은 아니다.

Q. 길이가 다른 코드를 이어 붙이면 디코딩할 때 문제가 있지 않나?

그럴 수 있다. A=0, B=01, C=1이라면 01은 B 하나로도, A 다음 C로도 읽힌다. 0이 01의 접두어이기 때문이다. 허프만 코드는 어떤 코드도 다른 코드의 접두어가 아니게 만들어 이 모호함을 피한다. 다만 접두어 조건이 전송 중 비트가 바뀌거나 빠지는 오류까지 막아 주지는 않는다.

예측 코딩과 LLM

Q. 예측 코딩은 LLM과 비슷한 개념인가?

앞의 정보를 보고 다음에 올 것을 예측한다는 점에서 닮았다. 예측 코딩은 다음 값을 예상한 뒤 실제 값과의 차이를 기록한다. 예를 들어 다음 숫자를 102로 예상했는데 실제 값이 103이라면 차이 +1을 기록할 수 있다. 예측이 잘 맞으면 차이를 짧게 표현하기 쉽다.

LLM도 앞의 토큰을 보고 다음 토큰의 확률을 예측한다. 그런 예측을 압축에 이용할 수도 있지만, 원문을 정확히 복원하려면 인코더와 디코더가 같은 예측을 재현하고 실제로 나온 값을 구분할 정보도 기록해야 한다. 그럴듯한 다음 문장을 생성하는 것만으로는 원문을 복원할 수 없다.

아날로그 신호, 푸리에 변환, 샘플링

Q. 아날로그 신호 전송과 푸리에 변환은 어떻게 연결되는가?

아날로그 신호는 시간에 따라 변하는 파형이다. 푸리에 변환은 그 파형을 어떤 주파수의 진동들이 얼마나 섞여 있는지로 바라보게 해 준다. 전선이나 전파는 모든 주파수를 똑같이 잘 전달하지 않으므로, 신호가 차지하는 주파수 대역을 알아야 필터와 전송 방식을 설계할 수 있다.

Q. 샘플링이란 무엇인가?

연속적으로 변하는 신호를 일정한 시간 간격으로 측정하는 것이다. 신호에 들어 있는 최고 주파수가 1,000Hz라면, 이상적인 조건에서 원래 신호를 복원하려면 초당 2,000번보다 빠르게 샘플링해야 한다. 너무 느리면 높은 주파수가 낮은 주파수처럼 보이는 에일리어싱이 생긴다. 샘플링은 측정할 시점을 정하고, 측정값을 몇 비트로 표현할지는 이후의 양자화에서 정한다.

Q. 그래픽에서 말하는 안티 에일리어싱도 같은 원리인가?

그렇다. 소리를 샘플링하기 전에 높은 주파수 성분을 줄이는 것처럼, 이미지를 픽셀로 줄이기 전에도 픽셀 안의 색을 적절히 평균 내면 계단처럼 보이는 경계를 줄일 수 있다. 둘 다 촘촘한 정보를 듬성듬성 기록하기 전에 신호를 적절히 걸러 내는 일이다.

양자 컴퓨팅으로 이어지는 지점

Q. 지금까지 공부한 것은 양자 컴퓨팅과 어떻게 엮이는가?

파인만은 물리 현상을 컴퓨터로 모의 실행하는 문제를 통해 양자적인 계산 장치를 생각했다. 지금까지의 개념은 서로 다른 지점에서 이 질문과 이어진다.

• 계산 가능성과 효율: 양자컴퓨터도 계산 모형이다. 여기서 중요한 질문은 계산 불가능한 문제를 풀게 되느냐보다 어떤 문제를 더 효율적으로 계산할 수 있느냐다.
• 가역 계산: 양자 게이트의 기본 동작은 되돌릴 수 있는 변환이다. 따라서 고전적인 가역 계산이 양자 계산으로 넘어가는 다리가 된다.
• 정보와 오류 정정: 큐비트에 저장된 정보도 잡음으로 손상될 수 있다. 허프만 코딩은 정보를 압축하려고 하고, 양자 오류 정정은 정보를 보호하려고 여분의 물리적 자원을 쓴다.
• 푸리에 변환: 양자 푸리에 변환은 양자 상태의 위상 패턴을 다루며, 위상 추정과 쇼어 알고리즘 등에 쓰인다. 앞서 본 신호의 푸리에 변환과 수학적 뿌리를 공유한다.
• 샘플링과 신호 처리: 양자 알고리즘 자체보다 실제 양자 장치를 제어하고 측정하는 신호를 다룰 때 연결된다.

관련 도서: 『파인만의 컴퓨터 강의(2판)』 출판사 소개