정보엔지니어 (맥스웰의 도깨비, 양자컴퓨터)

 소프트웨어 개발은 그 기원을 튜링 머신에 두고, 튜링 머신은 기계라는 것에 대한 수학적 탐구를 위해 앨린 튜링이 만든 것이다. 그리고 많은 사람들이 현세에 소프트웨어 개발업에 종사하면서 이러한 튜링 머신 체계에 나도 모르게 익숙해지게 된 것은 또 시대의 흐름에 따른다.

 이 상황속에 이 어려운 튜링 머신을 몸으로 체득한 이들이 바로 소프트웨어 개발자이다. 소프트웨어 개발자들은 논리를 설계하고 구현한다. 그리고 이들은 자연스럽게 과거의 수학자들이 했던 고민들을 마주하게 된다. 특히나 극단까지 최적화하려고 노력할수록 더욱 두드러진다.

 그렇다. 최적화를 고민하는 소프트웨어 개발자는 언제나 수학자들의 고민을 만나게 된다.

 이 둘 사이에는 과연 무슨 관계가 있길래 그러할까? 알고 보면 사실은 답이 매우 가까이에 있는데, 수학자과 소프트웨어 개발자들은 어쩌다보니 매우 다른 영역에서 일을 하게 되었고 서로 대화하기도 어려운 처지다. 따라서 필자는 이 둘의 관계 속에 깨달은 사실을 전개해보고자 이 카테고리를 시작한다.

 이 블로그에 이미 서술한 내용의 일부 재 편집과 그리고 추가라고도 볼 수 있다. 아래 주요 토픽들에 대해서 좀 읽기 편하게 순서를 뒤바꾸어 구성해보려고 한다.

 1. 맨 먼저 수 체계가 탄생한 배경 속에서 대칭과 그것을 구현하는 관점에서 바라보는 것에 대해서 논한다.

 2. 압축과 정보량에 대한 섀넌의 정보이론을 잠깐 돌이켜보면서 인코딩과 최적화된 압축에 대해 논한다.

 3. 소수(prime number)가 소프트웨어 개발에 등장하는 이유를 위의 최적화와 암호관점에서 논한다.

 4. 무한과 이산량에 대해서 소프트웨어 구현의 관점에 대해서 논한다.

 5. 랜덤과 그 구현 및 양자 역학에 대하여 논한다.

 6. 세상이 기계적 시뮬레이션이라는 것과 그 구현에 대해서 논한다.

 7. 정리한다.

처음 접하는 이들은 어려워보이겠지만 최적화된 구현을 고민하던 소프트웨어 개발자라면 하나하나 따라가보면서 이런 것들이 숨어있었다는 사실을 알게 될 것이다. 이런 유사한 설명을 들은 적이 없기 때문에 이러한 접근이 자연의 수학적 본성을 이해하고 소프트웨어 개발에 더 흥미를 갖을 수 있는 원동력이 되길 바란다.

전에 소수가 특정 수를 압축하여 나타내는데 사용될 수 있다고 묘사하였다.

즉 에라토스테네스의 체를 생각해보면 알게 되듯이, 소수는 수를 대칭으로 분할했을때( https://infoengineer.tistory.com/31 ) 나오는 "연속"을 처리할때 더 단순화 하는 방법이다.

무한의 수 중에서 2의 배수들은 2의 n번 반복으로 재정의 된다. 그러면 1의 2n번 반복보다는 2배 더 단순화할 수 있게 된다. 이렇게 3의 배수는 3의 n번 반복이다. 5의 배수는 5의 n번 반복이다.

그리고 이 n번 반복은 또다시 소수를 가지고 인코딩하면, 가장 단순한 형태의 수로 나타낼 수 있게 된다.

그런데 이전에 밝혔듯이 이보다 더 단순화를 할 수가 없다.

소수들은 1이 아닌 무언가의 반복으로 나타낼 수 없기 때문이다. 따라서 소수는 숫자를 반복으로 나타내는 구조에서 더이상 압축하여 나타낼 수 없는 정보가 된다.

소프트웨어 엔지니어가 이를 구현한다고 하면 소수는 테이블을 필요로 한다.

즉, 아래와 같은 소수 테이블에 의거하여 그것을 반복하는 형태의 인코딩을 해서만이 모든 수를 복원할 수 있다.

    1번배열 - 2 (첫번째 소수)

    2번배열 - 3 (두번째 소수)

    3번배열 - 5 ..

    4번배열 - 7 ..

    5번배열 - 11 ..

    ..

그리고 이 각각의 소수들은 동등한 권한을 갖는데 어차피 서로가 서로를 반복해서 곱해서 표현할 수 없기 때문이다. 따라서 말 그대로 숫자의 독특한 '원자'로서 작동하게 된다.

만약에 숫자를 소수의 곱으로 압축하는 방법과 같이, 이 소수를 조금더 압축하는 방법이 있다고 하면(결국 가우스가 소수의 규칙을 찾으려는 시도를 한 것은 이것과 같은 의미라고 생각한다. 저 소수 테이블을 쓰는 방법보다 더 단순한 구현방법을 고민한 것이다. 무한대의 전체 숫자를 나타낼 수 있는 방법 말이다) 얼마나 획기적인가? 다시 한번 다양한 숫자를 압축해서 나타낼 수 있게 된다. 즉 그 규칙을 통해 엄청나게 큰 숫자도 적은 정보로 나타낼 수 있다. 매핑 테이블 하나만 가지면 말이다. 그 매핑 테이블이 과연 무엇이냐가 소수의 규칙을 찾는 문제와 같다.

조금 이야기를 돌려보면, 그래서 소수는 모든 지성을 가진 존재(외계인이라고 쳐보자)들은 발견하게 될까?

그렇다고 생각한다. 언제 만나게 되냐면 세상의 모든 수를 압축해서 표현하고 싶을때 나타나게 된다. 정보를 줄이려는 자는 소수와 만나게 되어 있다. 그리고 이 소수는 예측 불가능하며 섞이지 않고 결국에는 알고리즘이 아니라 테이블로 만들어서 관리할 수 밖에 없다는 사실을 깨닫게 되는 것이다.

이렇게 소수와 소프트웨어의 압축과의 관계를 조금 더 풀어 써보았다.

콜라츠의 추측은 아래 단순한 규칙으로 반복하였을때 모두 1로 귀결된다는 추측이다.

if n is odd, get 3n+1

if n is even, get n/2

초등학생도 이해할 수 있는 문제이기 때문에, 아이들과 같이 이야기하다가 도움이 될 수 있는 만한 정보를 확보하여 기록해 둔다. 상기 계산을 숫자별로 계속 반복한 다이어그램이 바로 아래와 같다.

그런데 이 그림을 조금 계량해 보면, 이 문제를 더 단순화 할 수 있다. 어떻게? 특정 홀수들의 2의 x제곱을 각각의 줄로 나열해놓고 표기하는 방법이다. 이렇게 되면 해당 줄에 들어서면 나누기 2를 반복해서 결국 그 홀수로 귀결된다. 그러면 그 홀수에서 3n+1로 jump하는 식으로 구성할 수 있다.

위 그림에서 아예 홀수를 순서대로 나열하는 그림으로 바꾸면 아래와 같은 그림으로 전환된다.

그런데 가만히 살펴보면 이 화살표를 더 단순화 할 수 있다는 것을 알 수 있다. 일단 어느 홀수 선에든 닿으면 그것은 최종의 맨 상단의 본질적인 홀수로 닫게 되고, 그것이 다시 3n+1 jump를 해도 결국 그 jump한 홀수 선의 맨 처음으로 다시 귀결하기 때문이다. 따라서 아래와 같이 그려도 사실 어느 곳으로 움직이냐를 단순화 시켜 나타낼 수 있다.

이것을 더 크게 나타내보면 아래와 같다. 이번에는 even*2^x 패턴에서 이 even값들만 나열해보자. 그러면 더 간단히 나타낼 수 있다.

보다보면 오른쪽으로 이동이나 빨간색 왼쪽 이동은 일정 패턴이 있다는 것을 알 수 있다. 다만 어려운 것은 주황색의 왼쪽 움직임이다. 이 왼쪽 움직임은 몇가지 확인을 해본 결과 3*n을 빼놓고는 모두 닿으면서 다소 불규칙하다. 그래서 사실은 이 주황색의 움직임을 정형화 할 수 있다면 콜라츠의 추측 전체를 증명할 수 있지 않을까 싶었다. 그리고 이 이동이 사실은 테렌스 타오의 증명에 나오는 함수와 연관이 있다는 사실을 알게 되었다. 이 주황색의 움직임은 결국 소수와 연관이 있지 않을까? 그래서 불규칙한가? 라는 생각도 했었다.

이 작업을 진행하면서 3n+1 규칙 대신에 5n+1, 7n+1, 9n+1, 11n+1 등의 규칙을 조사해보았는데, 이런 확장에 대해 다소 규칙성이 있다.  새로운 규칙들에 대해 아래 숫자들을 발견하였다.

3n+1 -> 8n + (7-3)

5n+1 -> 8n + (8-5)

7n+1 -> 8n + (8-7)

9n+1 -> 16n + (16-9)

11n+1 -> 16n + (16-11)

다만 5n+1, 7n+1 등 일때는 순환이 다양한 양상으로 전개되고, 규칙 패턴이 조금씩 다르게 나타난다(검은색, 빨간색의 패턴이 다르다)

이 정보만으로 증명하기는 어렵지만 문제를 이해하는데 조금더 단순화한 그림을 제공할 수 있다고 생각한다.

이 문제에 대한 짧은 유투브 동영상을 같이 공유한다. 위 패턴중 주황색 패턴을 이해하여 이 문제의 증명에 도움을 받는이가 생겼으면 좋겠다.

https://www.youtube.com/watch?v=094y1Z2wpJg