디시인사이드 갤러리

마이너 갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

[일반] 누가 더 큰 수를 댈 수 있을까? (정보글)

llll(110.35) 2020.06.03 01:31:37
조회 8534 추천 64 댓글 34
														

이 글은 Texas Austin의 양자컴퓨터/계산복잡도 이론의 대가인 스콘 아론손(Scott Aaronson)의 글의 번역임. 큰 수를 대는 방법이라는 주제로 물리/천문학이랑 양자역학, 컴퓨터과학, 수리논리 등을 아우르는 재밌는 글이라서 내 개인페이지에 번역해서 뒀는데, 혼자보기 아까워서 이리저리 공유함.


아론손이 Festivaletteratura라는 이탈리아 문학축제에서 한 발표를 글로 정리한거라고 함. 1999년 아론손 자신의 글과 많이 겹치는데, 이리저리 추가된 내용이 있음. 수리논리나 집합논같은 부분인데, 솔직히 내가 잘 모르는 부분이라 번역이 젤 어려웠음. 그리고 디씨 텍스트/수식 편집이 불편해서 많은 부분 여기서 알아들을만한 표현으로 고침. (예를 들어 지수를 ^로 쓴다던가) 그래서 이상한 부분이 있을수 있는데, 말하면 고칠게.






큰 숫자들


by Scott Aaronson, 2017년 9월 9일

(역주:Texas at Austin의 교수로 양자컴퓨터와 계산복잡도 이론의 대가. 주요 업적으로는 P=NP가 증명하기 어렵다는 근거중 하나인 Algebrization, 최근 구글의 양자 우월(Quantum supremacy) 실험의 이론적 배경 등이 있다.)


translated by Minki Hhan (한민기), 2020년 6월 번역됨. 많은 부분 의역하거나 조금 수정함

물리/천문학이나 수리논리학에 관한 부분은 익숙하지 않아 오역이 있을수 있음을 밝힘


이제 겨우 네 살이 된 제 딸은 가끔씩 제게 쪼르르 달려와 이렇게 말하곤 합니다. “아빠, 나 드디어 가장 큰 수가 뭔지 알겠어! 바로 백곱하기백곱하기백곱하기배곱하기백곱하기백곱하기만만만만천천십십구구팔억이야!”

그럼 제가 대답하죠. “글쎄, 네가 정확히 무슨 숫자를 말하고있는지도 모르겠는걸. 그치만 그거에 1을 더하면 어때?” “아 그러네!” 딸은 소리치고 제게 되묻죠. “그럼 그게 바로 가장 큰 수야?”


물론 가장 큰 수는 없습니다. 그렇지만 우리가 현실적인 시간 안에 말할수 있는 가장 큰 수가 뭔지 고민해보는것은 굉장히 자연스러운 고민이예요. 좋아요, 한번 두 지원자를 불러서 실험해보죠. 수학을 좋아하는 아이들 혹시 없나요?


[두 명의 아이들이 단상으로 올라왔고, 저는 칠판 가운데 선을 그어 두 아이를 서로 다른편에 두었습니다. 분필과 함께요.]


좋아요, 우리가 해볼 게임은 바로 큰 숫자 대기예요. 이 두명의 지원자는 10초간 각자가 쓸 수 있는 가장 큰 수를 칠판에 적을거예요. 그렇지만 여러분은 “옆에 적힌 숫자 더하기 1″이나 “무한”같은 수를 적어서는 안됩니다. 그거 말고는 내가 이해할만한 설명으로 아무거나 적으면 됩니다. 원칙적으로는요.


좋아요, 준비됐나요? 그럼 시작해보죠.


[왼쪽 아이는 99999999같은 숫자를, 오른쪽 아이는 11111111111같은 숫자를 적었습니다.]


그래요, 9는 1보다 크죠. 그치만 1을 쓰는게 조금 더 빨랐어요. 그리고 이 차이가 승부를 갈랐네요. 좋아요, 우리 지원자분들께 박수 부탁드립니다!






전 어릴때부터 큰 수 대기에 푹 빠져있었습니다. 제가 10대일 때는 Who Can Name the Bigger Number?라는 에세이를 쓰기도 했었죠. 그 에세이가 여전히 여러 넓은 관점을 제시하는 것 같네요. 심지어는 제가 지금까지 했던 어떤 연구보다도요. 기뻐야할지 슬퍼야할지를 모르겠네요.


사실 그 에세이는 아직도 좀 유명한것같아요. 아마 구글에 아무나, 뭐 그런것 있잖아요, “가장 큰 수는 무엇인가?” 같은걸 치면 그 에세이가 나오기 때문일거예요. 여러분중 누군가는 구글이 사실 엄청 큰 숫자인 구골(googol), 10^100에서 나온것도 알고 있으시겠죠. 1 뒤에 0이 100개나 따라오는 숫자죠.


물론 구골은 당신이 말할수 있는 가장 큰 숫자에 전혀 가깝지 않아요. 흠, 구골플렉스(googolplex)라는 숫자로 시작해보죠. 이건 1 뒤에 0이 구골개 따라와요. 그럼 또 쉽게 구골플렉스플렉스라는 1뒤에 0이 구골플렉스개 따라오는 숫자를 생각할수 있겠죠. 그럼 구골플렉스플렉스플렉스.. 계속 생각할 수 있겠네요. 정말 정말 큰 수 입니다. 그치만 이 글에서 여러분이 배울 가장 기본적인 사실은 이런거예요. 만약 우리가 단지 어떤 행동을 반복하는 것으로써 더 큰 숫자를 댈 때, 그 때가 바로 한 발짝 물러설 때라는 거예요. 이런 반복적인 행동을 초월하는 뭔가를 찾아야 할 때라는 거죠. (일상생활에로의 응용은 물론 여러분의 몫입니다!)


이런 큰 수를 대는것은 가장 처음 고민한 사람은 기원전 200세기 고대 그리스의 아르키메데스(Archimedes)였을거예요. 아르키메데스는 아마도 역사상 최초의 대중과학글인 모래셈꾼(Sand-Reckoner)를 집필했습니다. 이 시라쿠스(Syracuse)의 왕에게 바쳐진 이 기념비적인 작품에서 그는 온 우주, 그러니까 그 때까지 알려진 온 우주를 가득 채우기 위한 모래알의 숫자의 최댓값을 계산합니다. 그는 결론적으로 “모래알의 숫자”를 셀수 없다, 혹은 알 수 없다는 뜻으로 쓰던 그 당시 몇몇 사람들의 생각을 반박한거죠.


아르키메데스는 우주의 크기를 그냥 어림짐작만 했었어요. 그가 그 시점의 최신이였던, 코페르니쿠스(Copernicus)보다도 앞섰던 아리스타르코스(Aristarchus)의 천문학을 이용하긴 했지만 말이예요. 아르키메데스는 이런 우주의 크기나 모래알의 크기에 대한 어림짐작은 차치해 두더라도 엄청 큰 수를 부르기 위한 뭔가 새로운 방식이 필요했어요. 그 때는 우리가 쓰는 아라비아 수체계나 과학적 표기법들이 없었으니, 그는 그냥 “myriad”라는 1만을 뜻하는 숫자를 조합해서 쓰는 방식을 채택했습니다. 이 방식으로 아르키메데스는 대략 1063개 정도의 모래알이면 우주를 채우기 충분하다고 계산해냈지요. 신기하게 고대 인도 수학자들도 비슷한 수를 부르는 비슷한 체계를 만들었었구요. 어떤 의미에서는 큰 수를 부르는 방식은 20세기까지 본질적인 진보 없이 이 정도에서 정체되어 있었습니다.


우리는 그런 최근의 진보들까지 모두 얘기할거예요. 그렇지만 그 전에, 아르키메데스가 우주를 다루기 위해 큰 수를 생각했다는 것을 떠올려봅시다. 이런 관점에서, 우리의 물리적 세계와 관계있는 가장 큰 수는 무엇일까요?


우리 몸에는 얼마나 많은 원자들이 있을까요? 혹시 아시는분 있나요? 예, 대략 10^28개 정도입니다. (만약 여러분이 고등학교 화학시간을 기억한다면 “몰”이 대략 6×1023정도 되니까, 꽤나 그럴듯한 숫자죠.)


그럼 우리은하에는 얼마나 많은 별들이 있죠? 이론의 여지가 있긴 한데, 그냥 1조개 쯤이라고 합시다.


우리가 관찰할 수 있는 우주 속에는요? 아마 별이 10^23개쯤 될거예요.


그럼 우리가 관찰할 수 있는 우주 안에 원자보다 작은 입자(subatomic particles)는 얼마나 될까요? 암흑물질이 뭘로 만들어졌는지 아무도 모르니 정확히 알수는 없지만, 10^90개 정도는 합리적인 추정으로 보이네요.


그럼 아마 몇몇분은 궁금해하시겠죠. 우주가 무한할수도 있고, 우주가 무한히 많은 별과 입자들을 가질수도 있지 않을까? 그 답은 꽤나 흥미로운데요, 사실은 아직 아무도 우주가 영원히 뻗어나가는지, 아니면 지구처럼 구부러져서 제자리로 돌아오는지 몰라요. 게다가 1998년에 밝혀진바에 따르면, 암흑에너지때문에 우주가 무한한 경우에도 우리가 볼 수 있는 부분은 기껏해야 유한하다고 생각한다네요. 암흑에너지는 은하들을 갈라놓는 힘이고, 은하들은 더 멀리 떨어져 있을수록 더욱더 빨리 멀어집니다. 그러니까 굉장히 먼 은하들은 빛보다도 빨리 멀어지고 있는거죠.


현재로써는 우리는 450억광년 떨어진 은하로부터 온 빛까지만 볼 수 있습니다. (왜 우주 자체가 136억년밖에 안됐는데 450억광년 멀리서 온 빛을 볼 수 있냐구요? 사실 그 은하가 빛을 방출했을 때는 우리은하와 훨씬 더 가까이 있었답니다! 그리고 빛이 우리에게 오는동안 우주가 그만큼이나 팽창한거구요.) 만약 암흑에너지가 우주적 상수(cosmological constant)의 형태를 가진다면, 어디엔가는 우리가 아직 보지 못한 우주만이 아닌, 절대 보지 못할 우주마저도 포함하는 더 먼 지평선마저도 있는거구요.


(역주: 마지막 문장은 의미를 파악하지 못하고 번역함. 원문은 If, as seems likely, the dark energy has the form of a cosmological constant, then there’s a somewhat further horizon, such that it’s not just that the galaxies beyond that can’t be seen by us right now—it’s that they can never be seen.)




현실에서 많은 큰 숫자들은 지수적인 증가의 형태를 보입니다. 아래에 세 함수 n, n^2, 2^n을 보여주는 그래프가 있습니다.



viewimage.php?id=20bcc42e&no=24b0d769e1d32ca73ced8efa11d02831dd2ecabb386674d2cf3d2b24d2c7634b12c12cfd516da08142503a8127663d55f9cde1dfa1bab0bbc82965


Image taken from the original article.


n과 n^2의 차이는 이 그래프 내에서 보이는대로 손 쓸수 있는정도만 차이가 나네요. 그렇지만 2^n은 금방 화면 밖으로 튀어오르고 맙니다. 이 급격한 증가는 현실에서도 많은 일들을 만들어내죠. 수학적인 사실들의 나열보다 훨씬 중요한 결과들을요.


예를 들어 현재 전 세계의 인구는 대략 75억명 정도 된다고 합니다. 제가 어릴때는 50억명 정도였구요. 현재 추세대로라면 64년마다 인구는 두배가 될 거예요. 이 속도가 지속된다면, 인간이 살아갈 다른 땅을 찾지 않는 이상 3000년도 지나지 않아 지구에 발디딜 틈 없이 인간이 가득차버릴거예요. 사람들이 꼭 데오드란트를 썼으면 좋겠네요…


다른 예로는 핵 연쇄반응(Nuclear chain reaction)이 있어요. 하나의 우라늄이나 플로토늄 핵이 분열되어 중성자들을 방출하고 결국 두 개의 핵의 분열을 만든다고 해봅시다. 그러면 이게 네 개의 핵분열을 일으킬거고, 8, 16, 32와 같이 폭발할때까지 끝없이 증가하고, 이걸로 핵무기를 갖게 되는거죠. (혹은 당신이 이 과정의 속도를 느리게 조절하면 핵 원자로가 되겠죠.) 세 번째 예시로는 국가의 총GDP나 당신 은행의 계좌에 붙는 복리같은거도 있구요. 네 번째로는 반도체의 성능이 18개월마다 2배씩 증가한다는 무어(Moore)의 법칙도 있죠. 물론 메모리나 다른 성능들도 비슷한 지수적 증가를 이루구요. 이런 지수적인 발전덕에 우리가 태어났을 때 쓰던 미국 최고의 슈퍼컴퓨터들보다 지금 여러분 주머니의 스마트폰이 훨씬 작고 성능이 좋은거죠.


근데 우리가 관찰할 수 있는 우주안에서는 지수적 증가에 대한 일반적인 규칙이 있어요. 이 지수적 증가는 오래 지속되지 않는다는겁니다. 이건 멈추게 되어있어요. 이런 현상을 지속할 자원, 예를 들어 인구수의 경우에는 음식의 양이나 땅이 있을거고, 핵반응의 경우에는 연료가 다 소모되겠죠. 그럼 무어의 법칙은 어떨까요? 어떤 물리적 법칙이 이걸 막죠?


무어의 법칙에는 사실 여러가지 버젼이 있는데, 어떤 버젼에서는 무어의 법칙은 이미 멈췄어요. 컴퓨터의 클럭 속도는 이미 무어의 법칙만큼 빨리 증가하지 않아요. 요즘에는 보통 좀 더 병렬연산을 하려고 노력하고, 코어에 더 많은 칩을 넣고 뭐 그럴 뿐이죠. 그리고 왜 그런지는 쉽게 알 수 있어요. 빛의 속도가 유한하니까요! 그러니까 컴퓨터의 속도가 그 자체의 크기때문에 제한될수 밖에 없어요. 요즘 트랜지스터들은 약 15나노미터정도인데, 여기서 두 배정도만 작아져도 원자를 하나하나 다뤄야할거예요. 우리가 공상과학소설의 세계에 뛰어들지 않는 한은 원자보다도 작은 트랜지스터를 상상하긴 어렵죠.


그럼 한번 공상과학소설의 세계로 뛰어들어봅시다. 공학적인 어려움은 모두 잊어버리자구요. 그럼 컴퓨터의 부품들의 크기를 더욱더 작게 만들고, 우리의 컴퓨터의 속도를 더 빠르게 만드는것에 한계를 줄 근본적인 물리학적 이유가 있을까요?


안타깝게도 있어요. 아직 누가 이걸 실험으로 직접 검증한건 아니지만, 1초에 약 10^43번 연산을 하는것, 혹은 플랑크시간(Plank time)에 연산을 한번 하는게 본질적인 한계죠. 비슷하게, 어떤 정보가 저장되는건 1플랑크영역(Plank area)에 1비트, 혹은 1평방미터에 10^69비트가 최고죠.


만약 이거보다 빠른, 혹은 좀 더 많은 정보를 저장하는 컴퓨터를 만드려고하면 어떻게 될까요? 그런 컴퓨터는 너무 많은 에너지를 너무 좁은 영역에 집중시키게 되고, 소위 말하는 슈바르츠실트 반지름(Schwarzschild radius)라는 영역을 초과하게 될거예요. 무슨 말인지 몰라도 괜찮아요. 그냥 간단히 그 컴퓨터가 블랙홀로 될거라는 말의 멋진 표현에 불과하거든요. 난 이렇게 자연이 우리에게 뭔가를 하지말라고 막는 방식이 아주 좋아요.


참고로 말하자면 현대적인 관점에서는 블랙홀은 가장 밀도가 높은 물체일 뿐만 아니라, 그 블랙홀의 사건의 지평선 1평방미터당 약 10^69비트를 저장하는 가장 효율적인 하드드라이버기도 해요. 물론 거기서 정보를 복구하는건 정말 어려운 일이지만요. 마찬가지로 블랙홀은 가장 빠른 컴퓨터기도 하죠. 블랙홀은 정말로 초당 10^43번의 연산을 하고 있거든요. 아무도 신경쓰지 않을 연산이긴 하지만요.


이 컴퓨터의 저장량과 속도에 관한 근원적 한계와 앞서 논의했던 관측할 수 있는 우주의 크기에 대한 논의를 합칠수도 있겠죠. 그러니까, 우리가 관측할 수 있는 우주는 기껏해야 10^122비트정도를 저장할 수 있어요. 다른말로 하면, 우리 세계에서 일어나는 모든 계산들이 얼마나 복잡하냐에 관계 없이 저 저장량에 모두 적힌다는 거예요. 그러니까 10^122이 우리 우주를 정하는 스케일의 숫자라는거죠. 우리가 물리에 대해 생각하는 것, 우리가 보고 행동하는것, 이 모든것이 0과 1이 나열된 10^122길이의 숫자 하나로 표현될 수 있다는 겁니다.




그렇지만, 수학이나 컴퓨터과학, 혹은 다른 분야 (물리학 자체도 포함해서요!) 우리는 종종 10^122보다 큰 숫자들을 다발로 만납니다. 어떻게 이게 가능하죠? 왜냐면 우리가 물것들의 수나 3차원에서의 크기 말고도 다른, 예를들어 공간에 물질들을 다르게 배치하는 방법의 수같은 추상적인 것들에 대해서도 생각을 하기 때문이죠. 이런 것들은 10122을 넘어서 계속 지수적으로 계속 증가해 나가곤 합니다.


예를 들어 400페이지에 10포인트로 쓴 소설은 얼마나 많이 있을까요? 아마 정말로 수없이 많은 책들이 쓰여지겠죠. 이게 바로 호르헤 루이스 보르헤스(Jorge Luis Borges)의 바벨의 도서관이라는 이야기에서 다룬 주제였습니다. 바벨의 도서관은 세상에 가능한 모든 책을 다 보관하고 있는 엄청난 크기의 도서관입니다. 물론 대부분의 책은 헛소리로 가득 차 있는데, 그중에는 세상의 모든 위대한 문학 작품들, 인류의 미래를 정확히 예측하는 책들, 혹은 미래를 딱 하나의 오류를 빼고 정확히 예측하는 책들 등등 모든 것들이 다 있지요.


좀 더 수치적으로 계산해 볼까요? 첫 번째 페이지를 채우는 방법은 얼마나 많을까요? 좋아요, 우리는 최소한 문법적으로 맞는 영어 글을 고려한다고 합시다. 쓸데없는 괴상한 문자로 가득찬 책은 말구요. 그런 경우에 영어의 표준적인 압축률(compressibility, or entropy)를 고려해보니, 아마 대략 10^700개 정도의 가능성이 있더군요. 좋아요, 소설들의 나머지 페이지들은 모두 갖다 버립시다. 가능한 첫 페이지만 생각해도 관측 가능한 우주에 가득채우기에는 너무나 많은 우주적으로 큰 가능성이 있다구요!


비슷하게 체스게임을 생각해봅시다. 얼마나 많은 다른 체스의 플레이방식이 있을까요? 제가 계산해보니 10^40정도부터 10^120정도의 가능성이 있더라구요. 이 차이는 우리가 얼마나 그럴듯한 게임만 셀건지, 말도안되는 게임도 전부 고려할건지에 대한 선택에서 오는거구요. 바둑의 경우에는 훨씬 더 복잡해요. 판도 19×19로 더 크죠. 이 경우에는 최소 10^800가지 정도의 게임 수가 있어요. 최소로요. 그래서 세계 체스 챔피언은 1997년 컴퓨터에게 졌지만, 컴퓨터가 바둑에서 이세돌을 이기는데는 2016년까지 20년이 더 걸린거죠.


또 다른 경우를 생각해봅시다. 1000개의 도시가 있어요. 그러면 외판원이 이 모든 도시를 딱 한번 들르려고 할 때, 얼마나 많은 경로가 존재할까요? 우리는 그 답을 쉽게 1000!, 천 팩토리얼임을 알 수 있죠. 그러니까 1000×999×998×…×2×1 말이예요. 첫 도시를 고르는데 1000가지 경우의 수, 두 번째 도시에 999, 뭐 이렇게 계속 되는거죠. 이 수는 대략 4×10^2567정도 됩니다. 그래서 또 보이는 우주의 입자수보다 많은 경로의 수가 있고 또 어쩌구저쩌구, 그렇게 되는거죠.


잠깐만, 외판원이 가장 짧은 경로에만 관심이 있다고 해봅시다. 물론 모든 도시들 사이의 거리는 전부 알구요. 그러면 컴퓨터가 이 가장 짧은 경로를 찾는데 1000!가지 경로를 모두 찾아야할까요? 아니면 적당히 더 현명한 방법이 있어서 1000!가지 경로는 아니지만 대략 도시의 수에 지수적으로 증가하는 경로를 뒤지면 충분할까요? 아니면 혹시 최단 경로를 훠얼씬 빠르게 찾아주는, 예를들어 도시의 수 n에 선형적, 혹은 2차함수정도로 느려지는 알고리즘이 있을까요?


이런저런 세부사항들을 슬쩍 무시하고 나면, 이게 바로 수학과 과학에서 가장 유명한 난제중 하나인 문제가 됩니다. 아마 몇분들은 들어보셨을거예요, P대 NP문제말이예요. 여기서 P는 다항식시간(Polynomial-time)의 약자로써, “그럴듯한 시간”에 풀리는 문제들의 집합을 말합니다. “그럴듯한 시간”이란 문제의 크기(예를 들어 도시의 크기 n)의 고정된 다항식정도의 에 비례하는, 예를 들어 n, n^3등의 시간을 말해요. NP는 비결정적 다항식시간(Nondeterministic Polynomial-time)이라는 좀 더 복잡한 단어의 약자인데, 이건 컴퓨터가 답을 맞는지 확인하는걸 그럴듯한 시간 안에 할 수 있는 문제들의 집합을 말해요. 만약 P=NP라면 답을 확인하기는 쉬운, 엄청 복잡한 조합적인 문제들이 사실은 풀기도 쉽다는 것을 말해요. 예를 들어서 스도쿠라던가, 비행기의 시간표를 조정한다던가, 박스들을 차의 트렁크에 최적으로 넣는다던가 하는 이런저런 문제들이 말이예요. 반면 P≠NP라면 이런 종류들의 문제중에서 어떤 문제는 푸는데 진짜진짜 오랜 시간이 걸린다는걸 말하는거구요. 우리가 컴퓨터 프로그램을 얼마나 훌륭하게 짜느냐에 관계없이 말이죠.


대부분의 수학자와 컴퓨터과학자들은 P≠NP라고 믿고있습니다. 사실 우리가 물리학자라면 좀 더 간단히 P≠NP가 바로 “자연의 법칙”이다 라고 선언해버리고, 우리에게 노벨성을 줘버리면 될거예요. 그리고 만약 P=NP라는 사실이 발견된다면, 우리에게 우리 “자연의 법칙”을 반증한 결과로 노벨상을 하나 더 줄수 있을걸요. 그렇지만 우리는 수학자와 컴퓨터과학자고, 우린 결국 이걸 “추측”이라고 부를수밖에 없네요.


다른 유명한 NP문제 하나를 소개해보죠. 자, 제가 2000자리 숫자 하나를 줄게요. 이 숫자를 소인수분해 해보시겠어요? 그래요, 두 천자리 숫자를 곱하는것은 최소한 컴퓨터에게는 쉬운 일이지만, 이 곱한 숫자를 보고 원래 인수들을 찾아내는것은 천문학적으로 어려운 것으로 보여요. 최소한 우리가 갖고있는 컴퓨터와 우리가 알고있는 알고리즘으로는 말이죠. 대체 누가 신경쓸까요? 글쎄요, 들어보신적 있을지 모르겠지만, 여러분이 온라인으로 뭔가를 주문할때 종종 작은 자물쇠아이콘을 보았을거예요. 이건 여러분의 신용카드 번호나 개인정보같은 것들이 암호 코드로 보호되고 있다는것 말하고, 사실 그 암호코드가 소인수분해와 비슷한 문제들이 어렵다는 가정 하에만 안전한거거든요. 만약 P=NP가 성립한다면 이런 안전성에 대한 믿음은 전부 거짓으로 밝혀질거고, 그럼 여러분을 지키던 이 모든 암호가 “그럴듯한 시간”안에 전부 박살나버린다구요.


사실 소인수분해나 암호에서 쓰이는 다양한 어려운 문제들이 박살나기 위해서는 P=NP만큼 놀라운 사실이 필요하지도 않아요. 그러니까, 이게 바로 우리가 또다른 얘깃거리로 넘어갈 부분이네요. 바로 10122같은 지수적 크기가 심심하면 나오는 양자역학의 세계에요.


아마 몇몇분들은 양자역학이 복잡하고 어렵다고 들었을거예요. 근데 사실은, 물리학만 빼면 양자역학은 놀라울만큼 쉬워집니다. 사실 저는 양자역학이 물리라기보다는 뭔가 물리밖의 것들이 돌아가는 운영체계같은것에 가깝다고 생각합니다. 양자역학에서 중요한 것을 한문장으로 말하면 이거예요, 물리적 시스템을 설명하기 위해서 우리는 진폭(amplitude)라고 하는 숫자를 세상의 가능한 모든 형태에 주어야한다는 것. 이 진폭은 우리가 세상을 관측할때 어떤 형태로 보이는지의 확률을 계산하기 위해 필요해요. 근데 이건 그냥 확률은 아니예요. 0부터 1사이가 아니라, 음수나 양수가 될 수 있고, 사실은 복소수도 될 수 있거든요.


우리가 이런 것들을 모두 정확히 알 필요는 없습니다. 양자역학이 말하는 중요한 것은, 예를 들어 1000개의 상호작용하는 입자들을 설명하기 위해서는 우리에게 최소한 2^1000개의 진폭이 필요하다는거예요. 이건 우리가 관측가능한 우주 전체에 적을수있는 숫자보다 더 많은거구요. 어떻게보면 화학자들과 물리학자들은 1926년부터 이 거대함에 대해 알고는 있었어요. 근데 그걸 뭔가 현실적인 문제같은걸로 생각했죠. 예를들면 “양자역학을 보통 컴퓨터에서 시뮬레이션하려면 입자 수보다 지수적으로 큰 컴퓨터가 필요하겠군” 같은것처럼요. 1980년대에 와서야 리처드 파인만(Richard Feynman)과 데이비드 도이치(David Deutsch)같은 몇몇 물리학자들이 “이 문제가 기회다(turning the lemon into lemonade)”라고 하며 이런 지수적으로 많은 진폭을 이용하는 컴퓨터를 만들자고 제안했어요. 만약 우리가 그런 컴퓨터를 만든다면 무슨 좋은일이 일어날까요? 그 주장을 했던 당시에는 양자역학 자체를 시뮬레이션할 수 있다는 응용뿐이였을거예요. 물론 그 자체로 지금까지도 가장 중요한 양자컴퓨터의 응용중 하나죠.


1994년에 피터 쇼어(Peter Shor)라는 한 학자가 양자컴퓨터에 대한 극적으로 놀라운 발견을 해냈습니다. 그게 뭐냐면요, 양자컴퓨터를 이용한다면 n자리 합성수를 소인수분해하는데 n^2정도의 시간만이 필요하다는 것이였습니다. n에 대한 지수적인 시간이 아니라요! 그러니까 만약 실용적인 양자컴퓨터가 만들어진다면 현재 인터넷 보안에 사용되는 대부분의 암호체계가 모두 무너진다는거죠.


(지금 당장은 아주아주 작은 양자컴퓨터밖에 없긴 해요. Shor의 알고리즘을 사용해서 소인수분해하는 최고 기록은 기껏해야 21=3×7정도예요. 그렇지만 구글은 몇 년 내에 49개의 양자 비트, 즉 큐비트를 가진 칩을 만들 계획을 세우고 있고, 세계의 다른 그룹들도 비슷한 노력을 하고 있습니다. 물론 49큐빗은 소인수분해나 뭔가 다른 쓸모있는일을 하기에는 너무 작지만, 이정도로도 고전적으로 어려운 일을 하기에는 충분합니다. 대략 249, 혹은 563조번 정도의 연산을 고전적으로 하는것이 정말 힘들다는 뜻에서요.*)


(*역주: 이 글을 번역하는 시점(2020년 6월)에는 구글이 이미 (에러가 많은) 53큐빗의 양자컴퓨터를 만들고, 이를 통해 양자우월성(quantum supremacy)를 달성했다고 주장하였음.)


물론 다른 NP문제들, 예를들어 새로운 다른 암호 코드들이나 외판원문제, 스도쿠 처럼 앞서 말한 문제들 모두가 양자컴퓨터로 빠르게 풀린다는 것은 아니라는것을 강조해야겠네요. 우리는 그런 문제들에 대한 양자 알고리즘은 잘 모릅니다. 보통은 양자컴퓨터를 사용해도 저런문제를 고전컴퓨터보다 제곱배 빠르게 푸는것에 그칩니다. 그러니까, 10^4에 풀던 문제를 10^2에 푸는것처럼요. 이게 바로 그로버(Grover)의 알고리즘의 결과지요. 지수적인 양자적 진보는 최소한 새로운 혁신이 필요합니다. 아직 그런 양자적 혁신이 불가능하다고 증명한 사람은 없습니다. 사실은 고전적으로도 불가능함을 증명한 사람도 없죠. 이게 바로 P대 NP문제니까요! 물론 아까 말했듯이 우리 대부분은 그런 혁신이 (양자적으로도) 불가능하다고 생각하지만요.


만약 우리의 그런 추측이 맞다면 양자컴퓨터는 큰 수들의 만병통치제는 아니겠네요. 물론 소인수분해같은 몇가지 문제에 극적인 혁신을 불러오긴 했지만, 우리가 바벨의 도서관에 들어갔을 때 최적의 책을 찾아줄 때 생기는 지수의 저주를 본질적으로 해결하진 못할거예요. 우리가 아는 가장 좋은 양자알고리즘을 쓰더라도, 외판원이 1000개의 도시를 어떻게 돌아야 가장 빠르게 도는지 알려주기 위해 양자컴퓨터는 우주의 나이보다 더 긴 시간을 쓰고 말거구요.




그렇지만 진실은, 수학에서 등장한 가장 큰 수는 지금까지 우리가 열심히 논의한 수보다 훨씬 훨씬 큽니다. 그러니까, 10^122보다는 당연히 크고, 혹은


svg.latex?2%5E%7B10%5E%7B122%7D%7D


와 같은, 관측 가능한 우주를 설명하기 위해 필요한 모든 진폭의 대략적인 수보다도 훨씬 큰거죠.


우선 스큐스 수(Skewes’ number)를 한번 얘기해보죠. 이 수는 하디(G. H. Hardy)가 “수학에서 명백한 목적을 갖고 쓰여진 가장 큰 수 “라고 부르기도 했어요. 우선 π(x)를 x이하의 소수들의 갯수라고 정의해봅시다. 예를 들어 소수 2,3,5,7때문에 π(10)=4가 되죠. 그럼 π(x)의 근사식으로 li(x)라는 함수가 알려져 있어요. li(x)라는 함수는 정말 한참동안 π(x)를 조금 크게 근사합니다. 최소 수조, 혹은 그보다 훨씬 큰 수까지요. 근데 어떤 x부터는 li(x)와 π(x)가 만나더니, li(x)가 π(x)를 조금 작게 근사하기 시작합니다. (그리고는 또 크게 근사했다가, 작게 근사했다가, 반복하죠.) 스큐스 수는 이 첫 교차점의 상한으로 제안된 수인데요, 1955년에 스큐스가 보인것은 첫 교차점이 바로 아래 수보다 작다는 거였어요.


svg.latex?x=10%5E%7B10%5E%7B10%5E%7B964%7D%7D%7D


물론 이 상한은 엄청나게 나아져서, 이제는 1.4×10316정도밖에 안됩니다. 뭐 그래도 괜찮아요. 이제 스큐스의 첫 추정값보다 훨씬 훨씬 큰 수들이 램지이론(Ransey Theory)과 다른 논리나 조합의 분야에서 등장하기 시작했거든요.


정말 아쉽게도 그런 예시인 그라함 수(Graham’s number)같은 세부적이고 또 아름다운 예시들을 자세히 파고들 시간까지는 없습니다. 그래서 그 대신 우리가 어떻게 지수를 넘어가는 방법론들과 수들을 만드는지 그 과정을 설명할게요.


시작점은 간단합니다. 우리가 초등학교 때 배운 연산들을 쭉 나열해보는거예요. 그리고 왜 우리가 그 연산들에서 이유없이 갑자기 멈추었는지 한번 반추해보죠.


좋아요, 우리 초점은 양수에만 맞춰져 있습니다. 그러면 “곱셈”은 그냥 “덧셈의 반복”을 뜻하는거죠. 예를 들어 5×3은 5를 3번 더하는 것, 그러니까 5+5+5를 말하는거죠.


“지수”도 비슷합니다. 바로 “곱셈의 반복”을 말하는거예요. 예를 들어 5^3 은 5×5×5를 말하는거였죠.


그러면 만약 우리가 지수를 반복해서 취하면 어떻게 될까요? 우리가 지금 소개하는 이 연산의 이름을 넷셈(tetration)이라고 불러보죠. 그리고 (^3)5와 같이 써보자구요. 5에 지수를 스스로 3번 취하는 것으로요. 그러면 우리가 얻는 것은 다음과 같습니다.


svg.latex?%5E35=5%5E%7B5%5E5%7D=5%5E%7B3125%7D=%201.9*%2010%5E%7B2184%7D

(주: DC의 텍스트 편집기 문제로 비슷하다는 것을 =으로 씀)


그러면? 우리는 계속해서 반복할 수 있어요. 우리가 x를 y에 다섯셈 한다는 것, 혹은 xPy를 x를 스스로 넷셈하는 것을 y번 하는것으로 정의하면 되는거죠. 물론 x를 y에 여섯셈 하는것, 혹은 xSy를 비슷하게 정의할수도 있을거구요. 얼마든지 반복할 수 있습니다.


이제 우리가 아커만 함수(Ackermann function)를 정의할 수 있습니다. 이건 1928년에 빌헬름 아커만(Wilhelm Ackermann)이 발명했는데, 바로 우리가 한 모든 연산들을 앞지르며 더 빨리 증가하는 함수예요. 우리가 위에서 했던 아이디어를 토대로 우리는 조금은 표준적이진 않지만 우리에게 충분한 형태의 아커만 함수를 아래와 같이 정의할 수 있어요.


  • A(1)은 1+1=2.
  • A(2)는 2×2=4.
  • A(3)은 3의 3 제곱, 즉 33=27.

뭐 이까지는 되게 단순하지만요…


  • A(4)는 4에 대한 4 넷셈, 즉

svg.latex?%5E44%20=%204%5E%7B4%5E%7B4%5E4%7D%7D=4%5E%7B4%5E%7B256%7D%7D=BIG


그리고 A(5)는 5에대한 5다섯셈인데, 이건 제가 간단히 쓰려고 노력하기도 싫네요. 물론 A(6)은 6에대한 6 여섯셈으로 정의되겠죠. 계속 비슷하게 정의할 수 있을거구요.


이 엄청나게 큰 아커만 함수는 정말로 수학과 컴퓨터과학의 몇몇 곳에 모습을 드러냅니다. 예를 들어 아커만함수의 역함수, 그러니까 a(A(n))=n이 되는 함수 a는 아커만함수가 빨리 증가하는 만큼 어엄청나게 느리게 증가하지요. 우주적으로 큰 수에 대해서도 그 결과값은 기껏해야 4정도밖에 안되는 정말 느리게 증가해요. 그런데 이 함수가 실제 알고리즘의 실행시간에 등장하곤 합니다.


그리고 물론 아커만함수는 좀 더 현실적이고 즉각적인 응용도 갖고있어요. 이제 당신이 큰 수 대기 대결에 참여한다면, 당신은 그냥 A(1000)이나 A(A(1000))같은 수를 적으면 되겠죠. 물론 아커만함수를 위처럼 밝히고 나서 말이예요. 당신은 무조건 승리할걸요. 물론 상대방이 아커만이나 뭔가 그것보다 큰 것에 대해 듣지 않았다면 말이죠.




근데 사실 이야기의 끝은 아직 한참 남았답니다. 만약 우리가 이해하기 어려울만큼 멀리가고자 하면, 그 좋은 시작점은 베리역설(Berry Paradox)이 되겠네요. 이건 버틀란드 러셀(Bertrand Russell)이 처음 지면에서 얘기를 했어요. 러셀은 이 역설이 한 사서 베리에게서 시작되었다고 말했지만요. 베리역설은 우리에게 지수나 아커만함수같은 어떤 체계를 뛰어넘는 뭔가를 상상하게 해줍니다. 그러니까 다음과 같은 비장의 수로 모든것을 끝내버리라고 하는거죠.


백글자, 혹은 그 이하의 한글로 명확하게 밝힐 수 있는 가장 큰 수


왜 이게 역설이라고 불릴까요? 음, 누구 문제점 찾은 사람 있어요?


그래요, 만약 위 숫자가 말이 된다면, 우리는 다음과 같은 숫자도 적을수 있겠죠.


백글자, 혹은 그 이하의 한글로 명확하게 밝힐 수 있는 가장 큰 수의 두배


근데, 우리가 이 숫자를 쓰는 순간 그 정의에 의해 이 숫자는 100글자보다 많은 숫자를 써야해요. 그런데 100글자보다 적게 썼단 말이죠. 뭐야, 무슨일이 일어난거죠?


많은 논리학자는 이 역설이 “한글로 명확하게 밝힐 수 있는 수”가 제대로 정의되지 않았기 때문에 발생한다고 말해요. 그래서 위와 같이 이상한, 실제로는 정확한 수를 말하지 않는 수를 적게 된다는거죠. 그럼 우리는 저 개념이 제대로 정의되지 않았다는걸 어떻게 알수있을까요? 왜 그 개념이 베리역설로 이어지는걸까요?


우리가 이 논리학적 역설의 법정에서 어떻게 빠져나갈수 있을까요? 이런 수를 피하기 위해, 우리는 한글을 좀 더 잘 정의된, 숫자를 정확히 명시할 수 있는 논리적 언어로 바꿔야겠어요. 글쎄요, 아! 이렇게 써보는건 어떨까요?


천바이트 이하의 컴퓨터프로그램으로 결정되는 가장 큰 수


이게 말이 되게 하려면 우리가 두 가지 문제를 해결해야해요. 첫 번째로 컴퓨터 프로그램으로 숫자를 “결정” 하는게 뭘까요? 여러가지 해결방법이 있겠지만, 우리는 컴퓨터 프로그램이 입력을 받지 않고 정확히 N번의 연산을 하고 끝냈을 때 N을 결정한다고 합시다.


두 번째 문제는 우리가 어떤 프로그래밍 언어를 생각해야하냐에 대한 겁니다. 베이직? C? 파이썬? 사실 결론만 말하면 이건 결과에 큰 영향을 미치지 않는다는거예요. 컴퓨터과학의 가장 기초적인 아이디어중 하나인 처치-튜링 논제(Church-Turing Thesis)은 모든 “합리적인” 프로그래밍 언어로 다른 모든것을 모방할 수 있다는 것을 말합니다. 그러니까 아무거나 당신 마음에 드는 언어를 고르기만 하면 우리는 이야기를 계속할 수 있어요. 명확하게 하기 위해 저는 최초이자 가장 간단한 프로그래밍 언어인 “튜링기계”를 고를거예요. 앨런 튜링(Alan Turing)이 1936년에 만들었던 바로 그것말이예요.


튜링기계 언어에서 당신은 사각형이 두 방향으로 끝없이 이어진 1차원의 테이프를 생각해야해요. 모든 사각형에는 0이 채워져 있어요. 그리고 테이프의 꼭지(head)와 n개의 “내부상태”가 있죠. 꼭지는 테이프에서 앞뒤로 움직여요. 각 내부상태는 해당하는 지시어들을 갖고있어서, 튜링기계는 지시어들의 명령대로만 따릅니다. 지시어들은 이런것들이예요: “0”을 현재 꼭지가 위치한 사각형에 써라, “1”을 현재 위치한 사각형에 써라, 꼭지를 오른쪽 사각형으로 움직여라, 왼쪽 사각형으로 움직여라, 내부상태를 다른걸로 바꿔라, 프로그램을 멈춰라. 이런 지시들을 현재 사각형에 적힌 숫자와 형재 내부상태만 보고 반복하는거죠.


이런 튜링 기계를 이용해서 수학자 티보 라도(Tibor Radó)는 우리가 지금까지 정의한 숫자들보다 아주아주 큰 바쁜비버함수(Busy Beaver function), BB(n)을 정의했어요. 그 정의는 약간 복잡한데, 아래와 같습니다.


n개의 내부상태를 갖는 모든 튜링기계를 생각합시다. 어떤 기계는 영원히 멈추지 않을것이고, 어떤 기계는 모두 0인 처음 상태에서 시작하자마자 끝나버릴거예요. 이 모든 기계들 중 언젠가 끝나는 기계들만 모아놓읍시다. 이 끝나는 기계들 중 끝나기 직전까지 가장 큰 횟수의 연산을 한 기계가 있을거예요. 그 가장 큰 연산 횟수가 바로 BB(n), 혹은 n번째로 큰 바쁜비버숫자입니다.


처음 몇 바쁜비버숫자들은 이미 정확히 계산되어있어요. 몇개의 예시를 한번 보죠.


  • BB(1)은 1이예요. 1개의 상태를 가진 튜링기계는 시작하고 바로 멈추거나, 똑같은 연산을 반복하죠.
  • BB(2)는 6입니다. 연필과 종이만 있으면 이걸 확인하는건 엄청나게 어렵진 않아요.
  • BB(3)은 21입니다. 이건 어떤 논문에서 증명된거예요.
  • BB(4)는 107이고, 이건 다른 논문에서 확인했죠.

아커만함수처럼, 아직은 별로 놀랍진 않죠. 그렇지만 계속해보면…


  • BB(5)는 아직 정확한 값이 알려져있지 않지만, 최소한 47,176,870 이상이라는 것은 알려져 있습니다.
  • BB(6)은 최소한 7.4×10^36,534이구요.
  • BB(7)은 다음 값보다는 큽니다.

svg.latex?10%5E%7B10%5E%7B10%5E%7B18,000,000%7D%7D%7D


여기부터는 명백히 괴물이죠. 우리가 이 무서운 괴물을 이해할수나 있을까요? 흠, 수열 f(1), f(2), …이 계산가능하다는 것은 어떤 컴퓨터 프로그램이 있어서 인풋 n에 대해 유한시간의 연산을 하고는 결국 f(n)을 결과로 내고 멈춘다는 뜻입니다. 계산하는데 얼마나 걸리는지는 관계없이, 끝나기만 하면 돼요. 예시를 한번 보자면, f(n)=n2, f(n)=2n이나 심지어 아커만함수마저도 모두 계산가능한 수열이예요.


여기서 제가 주장하고자 하는 것은 바쁜비버함수는 모든 계산가능한 수열보다 더 빨리 증가한다는거예요. 우리가 수학에 대해서 조금은 얘기하고 있으니까, 이 주장에 대한 증명을 한번 슬쩍 보죠.


가장 쉬운 방식은 이걸것같네요. 만약 바쁜비버함수보다 더 빨리 증가하는 함수 f가 하나 존재한다고 해봐요. 그리고 이 f를 이용해서 우리가 봤던 베리역설과 비슷하게 진짜 모순을 이끌어내 보자구요. 좋아요, f를 계산하는 함수가 1000바이트짜리 프로그램으로 표현되어서 그렇게 크지 않다고 합시다. 그러면 우리는 (예를들어) 2×f(1000000)번의 연산이 필요한 프로그램 P를 만들 수 있어요. 2×f(1000000)을 계산하고 1씩 더해가며 이 수보다 큰 수가 나올때 멈추는 프로그램을 생각하면 되죠. 근데 이 프로그램은 1000바이트보다 약간 큰 정도의 크기예요. 왜냐면 이 프로그램은 f를 보조프로그램으로 쓸거고, 1000000을 인풋으로 넣기 위해 아주 짧은 추가 코드가 필요할테니까요. 자 그러면 f(1000000)을 봅시다. 이건 BB(1000000)보다 클거고, 따라서 1000000바이트보다 작은 프로그램은 무조건 f(1000000)번의 연산 내에 끝나야 하죠. 어라, 근데 P는 더 많은 연산을 하는군요. 이건 모순이고, 우리가 내릴수 있는 결론은 사실 가정했던 함수 f가 없다는거겠네요.


(위 증명에서 모순을 없애고 그냥 내부상태 n개에 f(n)번의 연산이 필요한 함수을 어떻게 “hardwire”해서 만드는 식의 증명도 가능해요. 혹은 세 번째 증명으로 BB의 상한이 계산가능하다면, 어찌저찌 멈춤문제(halting problem)를 푸는 튜링기계를 만들어서 모순을 보일수도 있어요. 왜냐면 튜링이 이미 1936년에 멈춤문제를 푸는 기계가 없음을 증명했거든요.)


어떻게보면 바쁜비버함수가 계산 못할정도로 빨리 증가하는게 당연할지도 몰라요. 왜냐면 이게 계산이 된다면 우리가 수학의 드넓은 진실이 컴퓨터를 통해 우리에게 나타날지도 모르기때문이예요. 무슨 말이냐구요? 예를 들어 모든 4이상의 짝수가 두 소수의 합으로 나타내질수 있는지 묻는 골드바흐의 추측(Goldbach’s Conjecture)의 참거짓을 알고싶다고 생각해봐요. 그럼 우리는 각 짝수마다 그 짝수가 두 소수의 합으로 나타나는지 하나씩 하나씩 체크하고, 그렇지 않다면 멈추는 프로그램 하나를 만들면 될거예요. 이 프로그램이 N개의 내부상태를 가진 튜링기계로 표현된다면, 우리는 이 기계를 BB(N)번의 (혹은 아무 BB(N)의 상한) 연산을 하도록 두고, 이 기계가 멈췄는지 아닌지를 확인함으로써 골드바흐의 추측이 틀렸는지 맞는지를 확인할 수 있게됩니다. 그러니까 골드바흐 추측, 혹은 리만가설(Riemann Hypothesis)이나 다른 수많은 증명되지 않은 수학의 난제들이 단지 컴퓨터프로그램 하나가 끝나는지 아닌지를 확인하는걸로 표현된다는 거죠.


(물론 여기서 프로그램이 끝난것을 확인하는것은 극단적으로 이론적인 관점입니다. 누군가가 그냥 BB(N)번의 연산을 하는 N개의 내부상태를 가진 튜링기계를 우리에게 준다고 해도 BB(N) 스스로가 초-메가-천문학적이라서 우리는 이 기계와 그냥 영원히 끝나지 않는 기계를 구별하지 못할거예요. 그래서 위 “전략”은 리만가설이나 골드바흐의 추측의 증명을 그냥 “유한한 계산”으로 줄이는 정도이고, 우주가 끝날때까지 답을 확인하지는 못하겠죠.)


좋아요, 우리가 바쁜비버함수에 대해 할게 있을까요? 사실 제가 한 일인데요, 2015년 저와 제 전 제자 아담 예디디아(Adam Yedidia)는 BB(8000), 즉 8000번째 바쁜비버숫자가 우리의 수학적 공리계, 즉 ZF 집합론(Zermelo-Fraenkel set theory)하에서 결정하지 못한다는것을 증명한 논문을 썼습니다. 물론 BB(8001)이나 다른 큰 숫자들도 마찬가지구요.


혼란에 빠지지 마세요, BB(8000)은 정확한 하나의 숫자입니다! 가능한 8000-상태 튜링기계는 유한개 뿐이고, 각각의 기계는 언젠가 멈추거나 영원히 돌아가거나 하죠. 그리고 그 멈추는 것들 중 가장 길게 돌아가는 기계도 있구요. 우리가 증명한것은, 우리가 받아들인 공리계 하에서는 BB(8000)의 정확한 값을 증명하는 것이 본질적으로 불가능하다는 거죠.


우리가 이걸 증명한 방법은 한 8000-상태 튜링기계를 만든거예요. 이 튜링기계는 모든 ZF 공리계에서 나올 수 있는 결과들을 하나하나 나열하고, 모순을 발견하는 경우, 즉 0=1을 증명하는 경우에만 멈추는 기계입니다. 우리가 믿듯이 집합론은 일관성(consistency)이 있을거고, 아마 우리가 만든 프로그램은 영원이 돌아가겠죠. 그런데 이 프로그램이 영원히 실행되는걸 증명한다면 ZF 집합론의 일관성을 증명하는거예요. 혹시 이게 문제가 있다는걸 들어본 사람 있나요? 이게 불가능하다는 것이 괴델의 불완전성 정리(Gödel’s Incompleteness Theorem)입니다! 괴델이 증명한바에 따르면 어떤 집합론이 일관성을 갖는다는 것은 (혹은 좀 더 정확하게 산술적으로 정당하다(arithemetically sound)기도 하다는 것은) 이 집합론만으로는 일관성을 갖는다는 것을 증명하지 못한다는, 그러니까 우리 프로그램이 영원히 돌아가는지 멈추는지 증명하지 못한다는 것을 말합니다. 다른말로는 우리가 가정한 집합론으로는 BB(8000)역시 계산 못한다는거죠. 왜냐면, 만약 우리가 BB(8000)을 정확히 알수 있다면 그냥 BB(8000)번의 연산 아래에 우리 프로그램이 끝나는지만 확인하면 되니까요.


또 분명히 말하면, 어떤 집합론이 일관성이 있을때, 또 그때만 멈추는 프로그램이 있다는 것은 이미 오랫동안 잘 알려져 있었습니다. 그래서 한 집합론 내에서 알아낼 수 있는 바쁜비버함수의 값들은 유한개인 것을 잘 알고 있었구요. 우리가 증명한 것은 그냥 그 값이 8000보다 아래라는거예요. 이걸 위해서 엄청 많은 최적화와 공학적 기술이 필요했죠. (처음 우리의 상한은 백만정도였어요.) 최근에는 스테판 오 리어(Stefan O’Rear)가 우리 상한을 1000 이하로 내렸어요.


마지막으로 우리는 겨우 바쁜비버함수의 값을 고작 네개만 안다는 걸 다시 강조할게요. BB(100)의 값을 우리 집합론과 무관하게 구할 수 있을까요? BB(10)이나 BB(5)는? 우리가 얼마나 빨리 정신적 초공간(Platonic hyperspace)으로 도약하게 될까요? 물론 아직 답을 모르지만, 제겐 정말 궁금한 문제입니다.




아, 당연히 물어보실 줄 알았어요. 바쁜 비버들을 물 밖으로 날려버릴정도로 빠르게 증가하는 수열이 있긴 할까요? 물론 있습니다!


한번 여러분이 숫자 n을 적어 넣을수 있는 마법의 상자를 생각해봐요. 이 상자는 n이 입력되자마자 바로 BB(n)을 출력합니다. 컴퓨터과학자들은 이런 상자를 “오라클”이라고 불러요. 비록 바쁜비버함수가 계산 불가능하지만, 우리가 원할때 BB오라클에 접근하고 마음대로 이용할 수 있는 새로운, 마법적 능력으로 강화된 새로운 “초-튜링기계”를 생각하는 것이 수학적으로는 충분히 의미가 있습니다. 그러면 우리는 SBB(n), 초-바쁜비버함수를 n-상태 초-튜링기계가 중지하기 전 수행하는 최대 시행 수로 정의할 수 있죠.


그러면 우리가 지금까지 했던 논의를 그대로 따라가면, 이 초-바쁜비버함수 SBB(n)은 아무 계산 가능한 함수보다 빠르게 증가합니다. 게다가 초-바쁜비버함수 SBB(n)은 우리가 초-튜링머신으로 계산할수 있는 아무 함수보다도 빨리 증가해요. 예컨대 BB(n), BB(BB(n))같은 숫자들 말이죠.


그럼 비슷한 논의를 반복할 수 있겠네요. 이제 초-울트라-튜링기계를 초-바쁜비버함수를 오라클로 쓸 수 있는 튜링기계라고 합시다. 그러면 우린 또 초-울트라-튜링기계로 초-울트라-바쁜비버함수를 정의할 수 있고, 또 초-울트라-캡숑-튜링기계와 초-울트라-캡숑-바쁜비버함수도 정의할 수 있겠죠.


좀 더 간단하게 1단계 BB를 보통의 바쁜비버함수라고 합시다. 그리고 비슷하게 2단계 BB를 초-바쁜비버함수, 3단계 BB를 초-울트라-바쁜비버함수처럼 계속 정의합니다. 이러면 자연스럽게 n단계 BB를 임의의 자연수 n에 대해 정의할 수 있겠네요.


근데 우리가 여기서 멈출 필요가 있나요? 우리는 더 많이가서 ω단계 BB를 정의할 수도 있습니다. 근데 ω가 뭐죠? 수학자들은 이걸 “첫번째 무한서수(the first infinite ordinal)”혹은 첫번째 서수라고 부릅니다. 서수란 무한집합까지 포함한 우리가 이름지을 수 있는 모든 숫자집합에서 뭔가 그 모든것보다 더 큰 숫자로 가는 일종의 수 체계입니다. 좀 더 구체적으로는 ω단계 바쁜비버함수는, 간단하게 아무 원하는 자연수 k에 대해 k단계 바쁜비버함수를 마음대로 오라클로 쓸 수 있는 튜링기계를 통해 정의된 바쁜비버함수예요.


그럼 여기서 멈출까요? 왜요? 우린 새로운 (ω+1)단계 BB를 정의할 수 있어요. 이건 ω단계 바쁜비버함수를 오라클로 사용할 수 있는 튜링기계를 이용해 정의한 바쁜비버함수죠. 그럼 (ω+2)단계 BB도, (ω+3)단계 BB도, 계속 정의할 수 있겠죠. 그러다보면 우린 이걸 다 초월해서 모든 자연수 k에 대해 (ω+k)단계 BB를 오라클로 쓰는 튜링머신에 대해 정의된 2ω단계 BB를 정의하게 되겠네요. 마찬가지로 3ω단계 BB, 4ω단계 BB… 계속 정의하는데 전혀 문제가 없습니다. 그러다보면 결국 또 이것들을 초월해서 ω^2단계 BB에 도달하죠. 물론 이전의 모든 오라클을 사용할 수 있는 튜링머신에 대해 정의되는거구요. 그럼 ω^3단계 BB도 문제없고, ω^4단계 BB도…. 그러면요? 우린 이걸 모두 또다시 다 초월해서 ω^ωBB함수를 만들수 있겠네요. 여기서 끝나지 않았어요? 우린 계속하다보면 ω^ω^ωBB함수나 ω^ω^ω^ωBB함수, 혹은 이걸 계속계속 반복해서 ω가 ω번 반복되는 ω^ω^ω^.^.BB같은거도 도착할 수 있을걸요. (마지막 서수는 ε0로 불리기도 합니다.) 수학자들은 이러한 방식을 더욱 더 큰, ε0보다도 훨씬 큰 서수로 가는 방식을 알고 있고, 이걸 이용하면 우리는 훨씬 빠르게 증가하는 새로운 바쁜비버함수를 얻을수 있겠네요. 서수는 초월성의 개념을 체계화한다는 역설적으로 보이는 것을 달성합니다.


그럼 이걸 얼마나 계속 밀어붙일 수 있을까요? 궁극적인 답은, 사실 우리가 어떤 공리계를 믿느냐에 달려있습니다. 바로 이게 문제예요! 우리가 괴물같이 큰 서수를 얻을때는 항상 그들을 명백히 밝히기위한 체계가 필요합니다. 컴퓨터 프로그램을 쓸 수도 있겠죠. 그러면 떠오르는 질문은 그러한 것들 중 어떤 서수가 “존재하는지 증명할 수 있는지”입니다. 더 강력한 공리계일수록 더 큰 서수가 존재함을 증명할 수 있는데, 문제는 이런 공리체계는 계속 진행하다보면 언젠가 우리에게 연료가 부족해지고, 괴델이 했던 것처럼 새로운, 더 큰 서수를 부르는 방법을 가진 체계를 고안하지 않으면 더는 초월할 수 없게됩니다.


(기술적인 주석: 어떤 사람들은 우리가 이 모든 과정을 first-order logic에서 second-order logic으로 넘어감으로써 초월할 수 있다고 주장합니다. 그렇지만 난 이 의견에 기본적으로 동의하지 않습니다. second-order logic에서는 당신이 이름붙였던 수가 집합론의 모델에 의존하게 되고, 결국은 그 숫자를 정확히 밝히는게 불가능합니다. 반면 보통의 바쁜비버숫자들으로는, 비록 이 숫자들이 절망적일정도로 계산하기 힘들지라도, 정확히 하나의 숫자로 고정됩니다. 그리고 우리가 말하는 서수가 정확히 존재하죠, 최소한 양의 정수에 대해서는 말이예요.)


어쨌거나 이 모든 것의 결론은, 큰 수 대기 대결의 최고 전문가들은 결국 집합론의 공리에 대한 논쟁으로 뻗어나가게 될거라는 겁니다. 더 강력한 집합론이 일관성을 갖는다고 가정할수록 더 큰 서수의 이름을 말할 수 있고, 더 빠르게 증가하는 BB함수를 말하게 되겠죠.


예, 큰 수 대기 논쟁의 끝에는 결국 괴델의 늪이 존재합니다. 다행히도 그 늪에 빠지기 전에도 놀라울만큼 큰 숫자들을 얘기할 수 있다는 점은 다행이네요.




그 와중에도 우리 우주와 우리가 겪었던 모든것은 10^122가지의 가능성만을 갖고있는걸로 보입니다. 혹은 여러분이 스스로 어떤 초-특이점의 컴퓨터 클라우드에서 일어나는 우주의 혹사 (the heat death of the universe)까지 살지 못할거라고 생각하고, 100년정도만 살거라고 생각하다면 훨씬 적은 가능성이 있겠죠. 한편, 인류의 생존은 어쩌면 10^122보다 훨씬 작은 숫자를 이해하는 인간의 능력에 달려있을지도 모릅니다. 10억이나 1조, 혹은 우리 문명의 지수적 성장과 우리가 만나는 한계들을 다루는 숫자같은 것들이요.


만약 우리 목표가 이 축제의 목표대로 젊은 친구들에게 수학이 더 매력적으로 보이게 하거나, 양적인 세상과 문학적 세계 사이에 연결점을 두는것이라고 한다면, 우리의 이해 안에 있는 조그만 숫자들 밖에 숨어있는 광대함을 알리는것도 즐거울거라고 생각합니다. 다들 들어주셔서 감사합니다.

추천 비추천

64

고정닉 8

2

원본 첨부파일 1

댓글 영역

전체 댓글 0
등록순정렬 기준선택
본문 보기
자동등록방지

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 말머리 제목 글쓴이 작성일 조회 추천
2847 설문 열애설 터지면 큰 타격 입을 것 같은 아이돌은? 운영자 24/03/25 - -
41980 공지 공지 테스트 [9] Rafle갤로그로 이동합니다. 22.10.12 2931 6
42225 공지 수학 갤러리 추천도서 ㅅㄲㅁㅇ갤로그로 이동합니다. 22.10.17 5578 6
41450 공지 수잘갤에서 병신이 되지 않기 위해 명심할 행동강령 [17] ㅅㄲㅁㅇ갤로그로 이동합니다. 22.09.26 4526 43
14721 공지 고닉추 2 이하인 념글은 내림 [7] ㅅㄲㅁㅇ갤로그로 이동합니다. 20.04.12 4690 31
34238 공지 글 삭제 방침 [24] Rafle갤로그로 이동합니다. 22.02.16 3462 32
56347 일반 나비에 스토크스 난제 풀려면 토마스 칼큘정도면 충분함 ? [1] ㅇㅇ(210.102) 18:21 17 0
56345 중고딩 아래 g(x) 질문 풀이입니다 [1] 수갤러(223.38) 16:18 60 0
56344 일반 미적분학 공부하는데 여기있는 증명들 다 외워야됨? [7] ㅇㅇ(223.62) 15:24 115 0
56343 대학교 이거 틀린 증명 아닌가요? 선대 [11] ㅇㅇ(118.235) 14:57 125 0
56342 대학교 선대 embedding/projection 질문 [1] 미나미갤로그로 이동합니다. 14:35 58 0
56341 일반 고딩수학으로 이해하는 극한의 엄밀한 정의 수갤러(125.138) 14:12 100 2
56340 일반 독학런데 스튜어트 9. 미분방정식부터 시작해도 됨? [3] 흑석동꽁치두마리갤로그로 이동합니다. 14:09 55 0
56339 일반 범주론적으로 free group이 universal한거 맞냐? ㅇㅇ(211.246) 13:54 44 0
56338 일반 stein 복소 솔루션 있음? 수갤러(118.235) 12:48 51 0
56335 일반 도와주세요 [3] ㅇㅇ(220.116) 11:33 92 0
56334 중고딩 g(x)가 연속임을 보여야하는 이유...? [8] 수갤러(58.233) 10:10 213 0
56333 일반 페르마의 마지막정리 약한버전 이거 어떻게 증명안됨? 수갤러(220.71) 03.28 129 0
56332 중고딩 수갤러분 다시 한번 봐주세요 ㅜㅜ [1] 수갤러(220.83) 03.28 134 0
56331 대학교 수학 교수들은 왜이렇게 수업을 잘하냐?? [8] 수갤러(119.202) 03.28 437 9
56329 일반 이공계 종합 학술 갤러리 STEM 갤러리, 관심 있으시면 들러주세요 [3] ROBERT갤로그로 이동합니다. 03.28 240 2
56328 일반 훈련갔다왔더니 뇌손상온거같음 [6] 갱생리카갤로그로 이동합니다. 03.28 214 0
56327 일반 님들 스트랭 교수님 선대 강의 듣기 빡셈? [1] ㅇㅇ(106.102) 03.28 75 0
56326 일반 ideal의 finitely generated [7] 수갤러(125.176) 03.28 145 0
56325 일반 이거 뭐라고 읽나요? [2] 수갤러(125.136) 03.28 145 0
56324 중고딩 제가 뭘 잘못한걸까요? [1] 수갤러(118.235) 03.28 143 0
56323 대학교 X->X^2 bijective는 X가 무한이면 항상존재 증명 [2] ㅇㅇ(118.235) 03.28 138 0
56322 중고딩 대부분 문제를 지문까진 이해하는데 식을 못 세움 수갤러(210.91) 03.28 58 0
56321 일반 방금 고유벡터 질문, 생각해봐도 너무 당연해서 지웠음 ㅇㅇ(118.235) 03.28 50 0
56319 일반 나이 40 되서까지 포닥하다가 결국 탈수학하는 사람들 은근 많음? [12] ㅇㅇ(175.210) 03.28 431 9
56318 일반 수리통계 질문 [5] ㅇㅇ갤로그로 이동합니다. 03.28 151 0
56317 일반 수포자인데 ㅅㅂ 대학와서 수학을 하다니 [5] 수갤러(112.212) 03.28 238 3
56316 일반 수학 물리학 복수전공해서 4년에 마치는거 가능하나요? [2] 수갤러(223.38) 03.28 144 0
56315 일반 B1 이 smallest sigma algebra라는데 [4] ㅇㅇ갤로그로 이동합니다. 03.28 173 2
56314 일반 수학의 매력은 뭐라고 생각함 수갤러(106.102) 03.28 81 0
56308 대학교 증명보조기 다뤄본 사람들 있음? [4] ㅇㅇ갤로그로 이동합니다. 03.28 192 1
56307 일반 문제가 안풀려서 질문하기 위해 정돈해서 글작성하다보면 [3] ㅇㅇ(118.235) 03.28 179 0
56306 일반 허준이 교수님 이 인터뷰 뭔가 정곡을 찌르네 [4] ㅇㅇ(220.121) 03.28 530 11
56305 일반 studocu 결제 취소 어디서함? [1] 케빈듀란트갤로그로 이동합니다. 03.28 88 0
56303 중고딩 수능 수학 문항별로 어느정도 난이도임? [3] ㅇㅇ(211.248) 03.27 204 0
56302 대학교 위상수학 질문드려요 ㅜㅜ [3] 수갤러(121.133) 03.27 211 0
56301 대학교 두 집합의 Span이 같을 동치조건 증명 [3] ㅇㅇ(118.235) 03.27 162 0
56300 일반 쌍곡선함수 공식 기억하는 사람 있긴함? [1] 케빈듀란트갤로그로 이동합니다. 03.27 148 0
56299 일반 진도못나가고 이상한 거 꽂혀서 그거에 골몰하는 거 어케고침 [2] ㅇㅇ(175.223) 03.27 201 0
56298 일반 고딩때 배우는 평행이동을 더 좋게 설명할수있을거같아서 수갤러(223.38) 03.27 171 0
56297 일반 arcsecx가 arccos(1/x)임? [4] 알코올의존증갤로그로 이동합니다. 03.27 146 0
56296 일반 선대군 그래도 선대 한번 본 다음에 볼법하긴 한듯 [3] 미나미갤로그로 이동합니다. 03.27 223 1
56295 대학교 실전압축으로 미적분학 기초 다지려는데 책 추천좀 [14] 알코올의존증갤로그로 이동합니다. 03.27 198 0
56293 일반 외각의 합 질문. [4] (182.227) 03.27 128 0
56292 일반 공부할때 어떻게 함? [6] ㅇㅇ(211.104) 03.27 216 0
56291 일반 선대 강의 영상 추천좀 [1] ㅇㅇ갤로그로 이동합니다. 03.27 111 0
56289 일반 수학에서 위 과정을 반복하면~은 엄밀하게 표현가능? [3] ㅇㅇ(118.235) 03.27 245 0
56288 일반 sylow thm [3] ㅇㅇ(1.251) 03.27 231 0
56286 일반 님들 혹시 코딩도 함?? [1] 알코올의존증갤로그로 이동합니다. 03.27 209 0
56284 일반 변분법 좋같이 어려운데 [5] TP갤로그로 이동합니다. 03.26 394 0
56283 대학교 이 갤러리에서 수학/물리학 기호 적으려면 어떻게 하나요? [4] 수갤러(175.196) 03.26 268 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2