Fundamentals of ECE (1) 수학에 대한 고찰과 알고리즘의 탄생

Turing Machine & Semiconductor Devices pt 2.

수학은 발명인가, 발견인가?

수학이라는 것이 도대체 무엇인지는 상당히 흥미롭다.

예컨대 삼각형의 세 각의 합이 $180^\circ$라는 사실은 이미 자연에 존재하고 있는 것처럼 보인다. 우리는 단지 그러한 사실을 ‘발견’해 낸 것이다. 하지만 점과 직선, 길이, 각도, 심지어 자연수 $1$조차도 그것이 물리적인 실체로 자연에 존재하는 것은 아니다. 다만 그러한 개념들은 우리의 상상 속에서만 존재하는 추상적 창작물이다. 그러한 관점에서 수학은 인간이 ‘발명’해 낸 것이다.

자연수는 인간이 가장 직관적으로 생각해 낼 수 있는 수학적 개념이라고 할 수 있다. 사과 1개, 사과 2개와 대응되는 개념이며, 이를 이용한 덧셈, 곱셈 등의 산술 연산은 실제 우리의 경험과 잘 맞아떨어진다.

하지만 $0$은 이보다는 조금 더 추상적인 개념일지 모른다. 음수 역시 그러하다.

내가 애정하는 이영민 교수님의 말씀에 의하면, 최초의 수포자가 탄생하는 지점은 "음수 곱하기 음수가 양수" 라는 것을 배우는 시점이라고 한다... 교수님께서는 수업 중 학생들에게 한 명씩 "왜 음수 곱하기 음수가 양수인지"를 물어보셨다. 다들 저마다 설명하려고 애썼으나 명확하게 왜인지 설명할 수 있는 사람은 아무도 없었다. 교수님은 실수의 순서 공리(Order Axiom of $\mathbb{R}$)를 이용해 증명을 마치시고는 이렇게 덧붙이셨다.

"결국 음수 곱하기 음수가 양수인 이유는 너네가 그냥 외운 것이다."

수학은 기본적으로 엄밀함을 추구한다. 그 기저에는 데카르트적 합리주의가 깃들어 있는 듯하다. 말하자면 절대 반박할 수 없는 공리들로부터 시작하여 쌓아 올린 아주 엄밀한 주춧돌만이 나중에 전체 지식의 탑을 무너뜨리지 않는다는 믿음이다. 그리고 수학은 이러한 '무모순성'이라는, 어찌 보면 강력하고 어찌 보면 아주 약한 규율만을 갖고 있기에 매우 자유롭다. 수학은 무모순성 안에서 모든 것을 허용한다.

이런 것을 보면 수학은 자연과는 동떨어진 인간 지성의 지적 유희와도 같다는 생각이 든다.

비합리적 효율성

여기가 가장 흥미로운 부분인데, 순수한 지적 유희로 보이는 수학이 자연을 기술하는 데 너무나 효율적인 언어라는 점이다. 이것이 Eugene Wigner가 말하는 "자연과학에서 수학의 비합리적 유효성(The Unreasonable Effectiveness of Mathematics in the Natural Sciences)"이다.

'지수'라는 것은 그저 연속되는 곱하기 기호를 생략하기 위해서 만들어졌을 것이다.

고등학교 때 이 지수 위에 유리수를 넣고 확장을 시작한다. 거듭제곱근으로 정의하면 기존의 지수법칙들이 잘 성립한다는 것을 확인한다.

그리고 이를 실수로까지 확장한다. 즉, 지수함수($y=a^x$)의 탄생이다.
나중에는 지수에 복소수는 물론이거니와, 심지어는 행렬까지 올라가는 기이한(?) 식들을 만나게 된다. 익숙한 개념을 추상화를 통해 좀더 일반적인 것으로 만드는 것이 수학자들의 지적유희 중 하나인 것으로 보인다.

하지만 놀랍게도 방사성 동위원소의 농도를 포함한 실제 수많은 자연 현상은 이 지수함수를 따른다.

이러한 예시는 한두 개가 아니라 클리셰와도 같다. 리만 기하학이 나중에 아인슈타인의 일반 상대성이론과 들어맞는 모습은 전형적인 예시이다. 심지어 오비탈의 에너지 준위가 리만 제타 함수($\zeta(s)$)와 닮아있는 것 또한 유명한 글로벌 떡밥이다.

특히 복소수가 그러하다.

내가 처음 복소수에 대한 의문을 가진 것은 공학수학 1에서 미분방정식을 풀 때 복소수를 이용하는 과정에서였다. 2계 미분방정식(예를 들어 RLC 회로 해석이나 감쇠 진동)을 푸는 과정에서 해는 복소수의 형태($e^{i\omega t}$)로 나오게 되고, 우리는 물리적 의미를 찾기 위해 이것의 실수 성분만을 취한다.

그렇다면 해의 허수부가 의미하는 것은 무엇인가가 내 의문이었다.

옛날 사람들은 이차방정식을 풀 때 음의 근이 포함된 경우 이를 무시하고 양의 근만 참된 근이라고 여겼다고 한다. 즉, "복소수는 도대체 무엇인가" 하는 의문 자체가 중요하지 않을 수도 있다는 것이다. 사실 음수도, 엄밀히 말하면 자연수도 현실에 물리적으로 존재하는 것은 아니다. 수학이라는 것은 우리가 지적 유희를 통해 정립한 언어이자 체계일 뿐이고, 이것이 우리가 사는 자연 세계를 설명할 때 소름 돋도록 잘 맞아떨어질 뿐인 것이다. 비슷한 논리로 회로이론을 공부할 때 역시 임피던스($Z = R + jX$), 복소 전압($\tilde{V}$) 등 우리는 그저 수학적 ‘도구’로서 복소수를 사용한다.

다만 정말 놀라운 부분은 양자역학이다. 양자역학의 파동함수($\Psi$)는 실수함수가 아니라 바로 복소함수다. 그전까지 복소 저항(임피던스)이라는 것이 실제로 존재하는 것이 아니라 그저 계산의 편의를 위해 잠깐 도입한 도구였다면, 이것은 차원이 다른 문제다. 우리가 사는 세계의 근간인 파동함수가 실제로 복소수로 이루어져 있다는 것은 쉽게 받아들이기 어렵다.

괜히 오일러 공식이 세상에서 가장 아름다운 공식인 것이 아니다. 그 속에는 우주의 진리가 담겨있는 듯 하다.

300년 전 칸트가 이러한 혼란에 대해 아주 중요한 고찰을 한 바 있다. 인간에게는 자연을 인식하기 위한 선험적 형식이 존재하고, 바로 이것을 밝혀내는 것이 수학의 본질이라는 것이다.

힐베르트 프로그램: 완벽을 꿈꾸다

이쯤에서 이러한 엄밀함을 추구하는 수학 정신의 정점을 찍으려던 시도를 소개할 필요가 있다. 그리고 놀랍게도, 그 과정에서 현대적인 컴퓨터가 탄생하게 되었다.

바로 힐베르트 프로그램(Hilbert's Program)이다. 이는 수학을 인간의 직관이 아닌, 완벽한 기호(Symbol)와 규칙(Rule)의 시스템으로 재정립하려는 시도였다.

"Wir müssen wissen. Wir werden wissen."
(우리는 알아야만 한다. 우리는 알게 될 것이다.)

힐베르트는 다음 세 가지를 수학에서 완성하고자 했다.

1. 완전성 (Completeness): 시스템 내의 모든 '참'인 명제는 증명 가능해야 한다.
2. 무모순성 (Consistency): 시스템 내부에서 모순($A$이자 동시에 $\text{not } A$)이 발생해선 안 된다.
3. 결정가능성 (Decidability): 명제의 참/거짓을 판별하는 기계적인 절차(알고리즘)가 존재해야 한다.

만약 이것이 실현된다면, 우리는 더 이상 난제 앞에서 고민할 필요가 없어진다. 어떠한 난제든 이 기계적인 절차에 넣기만 하면 '참' 혹은 '거짓'이라는 판결을 얻을 수 있게 될 것이기 때문이다.

즉, 힐베르트는 인간의 '직관'과 같은 애매모호하고 거친 현실과 결별하고, 오직 완벽한 논리 위에 서 있는 공고한 낙원을 건설하고자 했던 것이다.

괴델과 튜링: 확실성의 붕괴와 컴퓨터의 탄생

이 너무나도 아름다운 시스템은 괴델에 의해 완전히 박살 나게 된다.

• Kurt Gödel (1931)

• 제1 불완전성 정리 (The First Incompleteness Theorem):
  모순이 없는 공리 체계 안에는 '참(True)'이면서도 '증명할 수 없는(Unprovable)' 명제가 반드시 존재한다. 수학(논리)은 모든 진실을 담아낼 수 없다. 즉, 수학은 불완전하다.
• 제2 불완전성 정리 (The Second Incompleteness Theorem):
  공리 체계 안에서는 그 체계 자체가 모순이 없다는 것을 증명할 수 없다. 시스템은 스스로의 정당성을 스스로 입증할 수 없다. (이를 증명하려면 외부의 상위 시스템이 필요하다.)

즉, 힐베르트 프로그램의 1, 2번을 박살 내버린 것. 남은 것은 3번. '결정 가능성'의 문제였다.

• Alan Turing (1936)

당시엔 기계적 절차(Algorithm)가 무엇인지 아무도 명확히 정의하지 못했다. 튜링은 이를 정의하기 위해 인간을 관찰했다.

• Modeling the Human Computer: 수학 문제를 푸는 인간(Computer)을 관찰.
  • 인간은 종이(Tape)에 기호를 쓰고 지운다.
  • 뇌의 상태(State)는 유한하다.
  • 규칙(Rule)에 따라 한 칸씩 움직인다.
• Abstraction: 이를 튜링 머신(Turing Machine)이라는 가상의 장치로 추상화함.
• Definition: "알고리즘이란, 튜링 머신이 수행할 수 있는 모든 작업이다."

그리고 튜링은 힐베르트의 마지막 희망을 확인사살한다.

The Halting Problem (정지 문제): The Limit of Computation
튜링은 '어떤 프로그램이 영원히 돌지, 아니면 언젠가 멈출지'를 판별하는 알고리즘은 존재할 수 없음을 증명했다. 즉, 결정 불가능한 문제가 존재하므로 "만능 기계적 절차(Decision procedure)는 없다."

이는 훗날 어떤 프로그램도 다른 프로그램의 완벽한 무결성을 실행 전에 미리 보장할 수 없다는 '라이스 정리(Rice's Theorem)'로 확장된다. 이는 우리가 코딩 테스트를 볼 때, 채점 프로그램이 내 코드를 쓱 훑어보고 정답 여부를 판단하지 못하는 근본적인 이유이기도 하다. 완벽한 검증은 불가능하기에, 우리는 여전히 '테스트 케이스'를 하나하나 대입해보는 방식을 쓰고 있는 것이다.

이로써 힐베르트 프로그램은 완전히 종결되었다.

괴델과 튜링의 증명 과정은 칸토어가 실수 집합의 비가산성을 증명할 때 사용한 대각선 논법($|\mathbb{R}| > |\mathbb{Z}|$)과 구조적으로 동일하다. 힐베르트는 생전 '아무도 칸토어가 창조한 낙원에서 우리를 쫓아낼 수 없다'라며 칸토어의 집합론을 옹호했고, 그 위에 수학의 완벽한 성을 쌓으려 했다.

하지만 아이러니하게도 그 성을 무너뜨린 무기는 바로 칸토어가 남긴 유산이었다. 힐베르트는 자신이 가장 사랑했던 칸토어의 정신에 의해, 자신의 꿈이 무너지는 것을 지켜봐야 했다.

하지만, 그 과정에서 보편 만능 기계(Universal Turing Machine)의 설계도가 완성되었다. 수학의 완전함을 증명하려던 시도가 실패함으로써, 오히려 현대 문명을 지탱하는 컴퓨터라는 부산물을 낳은 것이다.

튜링 이전의 기계는 하드웨어 그 자체가 곧 기능이었다. 계산기는 계산만, 타자기는 타이핑만 할 수 있는 것이다. 하지만 튜링 머신은 기계 본체(Head & State Register)는 단순히 테이프를 읽고 쓰는 단순 작업만 수행한다. 대신, 그 테이프에 '어떤 규칙'을 적어 넣느냐에 따라 이 기계는 미분 방정식을 풀 수도 있고, 암호를 해독할 수도 있다.

즉, 적절한 테이프(Software)만 주어진다면, 하나의 기계로 세상의 모든 계산 가능한 문제를 해결할 수 있다.

튜링이 진정한 GOAT인 이유는 그가 상아탑에 갇힌 수학자가 아니었기 때문이다. 그는 '알고리즘'이라는 소프트웨어적 개념을 창시하고 그 논리적 한계(정지 문제)까지 명확히 규명했다. 동시에 그는 전쟁이라는 가혹한 현실 속에서 독일군의 암호(Enigma)를 해독하는 기계를 직접 설계해낸 탁월한 엔지니어였다.

심지어 그는 컴퓨터가 막 태동하던 그 시기에 이미 '기계가 생각할 수 있는가?'라는 질문을 던지며, 오늘날의 인공지능(AI) 개념과 튜링 테스트를 제안하기까지 했다. 그는 진정으로 시대를 앞서간 설계자였다.

튜링머신에 대해 보다 깊은 이야기는 아래 포스트를 참고
https://velog.io/@jm-sens/Turing-Machine

다시 돌아와서...
힐베르트 프로그램의 실패는 무엇을 의미하는가?
그러면 다시, 수학은 무엇인가?
칸트는 맞았는가?