1. 개요
Collatz conjecture1937년 독일의 수학자 로타르 콜라츠(Lothar Collatz)가 제기한 추측으로, 현재까지 증명되지 않은 난제 중 하나이다.
이에 대한 대표적인 권위자로 제프리 라가리어스(Jeffrey C. Lagarias)[1] 교수가 있다. 제프리 교수는 2010년에 이 문제에 대한 알려진 정보만을 토대로 "이것은 현재의 수학에서 완전히 벗어난 매우 어려운 문제입니다"라고 주장했다.
2. 추측 내용
이른바 "우박수" 또는 "우박 수열"이라는 이름으로 아는 사람이 많을 것이다. 이는 수가 커졌다 작아졌다를 반복하다 (추측하건대) 1에 수렴하는 것을, 비구름에서 빗방울이 오르락내리락하며 우박이 되어서 땅에 떨어지는 모습에 빗대어 그렇게 부르는 것이다. (1에 수렴 한다기 보다는 모든 정수에 대해서 진동함.)| [math(T(n) = \left\{\begin{array}{cl} \cfrac n2 & (n\textsf{이 짝수일 때}) \\ 3n+1 & (n\textsf{이 홀수일 때}) \end{array} \right.)] |
| [math(T'(n) = \left\{\begin{array}{cl} \cfrac n2 & (n\textsf{이 짝수일 때}) \\ \cfrac{3n+1}2 & (n\textsf{이 홀수일 때}) \end{array}\right.)] |
이를 풀어서 설명하자면 1을 제외한 아무 자연수나 생각한 다음, 그게 홀수라면 3을 곱한 다음 1을 더하고, 짝수라면 2로 나눈다. 그렇게 나온 수를 다시 저 식에 집어 넣고 이하 반복, 이걸 계속하다 보면 1이 나온다는 것이다. 예를 들어 5에서 시작하면 5는 홀수니까 [math(3\times5+1=16)]이 되고 16은 짝수니까 [math(16\div2=8)], 이후 4와 2를 거쳐 1에 도달하게 된다. 이정도는 간단하지만 27의 경우 최대 9232까지 올라가며 111번을 반복해야 1에 도달한다.
이 추측의 반례는 아직 나오지 않았고, 아마도 참일 것으로 추정된다. 반례가 하나라도 나오는 순간 별다른 증명이 필요없이 저 추측은 거짓인 것으로 문제가 끝나기 때문이다. 이미 1980년대에 컴퓨터를 이용해 약 1해([math(=10^{20})])까지의 수를 넣어보았지만 모두 1에 도달했다. 2020년, [math(2^{68} (\approx 2.95 \times 10^{20}))]까지 참으로 드러났다. 2025년에는 [math(2^{71} (\approx 2.36 \times 10^{21}))]까지 확인되었다.[2]
이 추측은 [age(1937-01-01)]년이 넘도록 풀리지 않고 있다. 게다가 상금도 걸려 있다. 1000파운드와 500달러의 상금이 걸려 있는데, 이중 500달러의 상금을 건 사람은 에르되시 팔이다.[3] 또한 1.2억 엔(약 11억)의 상금을 지급한다.#
3. 일반화
결론부터 말하면 일반화를 해도 진전이 없다. 콘웨이의 생명 게임 창시자로 유명한 존 호튼 콘웨이가 1972년에 정지 문제를 이용해 일반화한 문제는 결정 불가능하다고 증명했기 때문이다. 콜라츠 추측 자체가 결정 불가능하다는 게 아니다. 콜라츠 추측은 짝수면 [math(\cfrac12)]을 곱하고 홀수면 [math(3n+1)]을 하는 함수 [math(g)]가 주어지고 모든 [math(n)]에 대해 이것이 수렴하는지 묻는 것인데 이제는 자연수 [math(P)]가 주어진 상황에서 다음과 같이 [math(n~(\bmod P))]에 따라서 서로 다른(혹은 일부는 같아도 상관 없다) [math(P)]개의 일차함수를 통해 값을 반환하는 더 일반화된 함수 [math(g)]를 생각하자는 것이다.| [math(g(n) = \left\{ \begin{array}{lcl} g(Pk) &= g_1(k) \\ g(Pk+1) &= g_2(k) \\ \vdots \\ g(Pk+(P-1)) &= g_P(k) \end{array}\right. )] |
[math(P=1)]인 경우 [math(g)]는 자명하게 계속 증가하거나 감소한다.
콜라츠 추측은 다음과 같이 표현할 수도 있다.
[math(P=2)], 자연수 [math(k)]에 대해
| [math(T(n) = \left\{ \begin{aligned} T(2k) &= k \\ T(2k+1) &= 3k+2 \end{aligned} \right.)] |
이러한 결과들은 콜라츠 추측을 일반화시켜 연구하는 것이 어려울 것임을 시사한다. 그러나 콜라츠 추측의 참/거짓/증명불가능성과는 직접적인 연관이 없는데 일반화된 알고리즘이 없어도 각 경우를 모두 풀 수 없는 것은 아니기 때문이다.[5]
위의 일반화된 [math(g)]함수와 같은 꼴을 띠는 특정[6] 문제를 콜라츠 추측 유사 문제라고 부르는데, 특히 입출력이 없는 튜링 머신에서 이러한 경향성을 보이는 경우가 있다. 이러한 튜링 머신을 통틀어 Collatz-like Busy Beaver라고 부른다. 이들은 낮은 수의 바쁜 비버 연구에서 핵심적인 역할을 한다. 특히 일부 튜링 머신의 정지 여부를 판단하는 것은 콜라츠 추측과 비슷한 난이도를 가지고 있을 것으로 보인다.[7]
4. 페르마의 마지막 정리와의 비교
콜라츠 추측은 증명의 악랄한 난이도에 비해 문제 자체는 초등학생도 이해할 수 있을 정도로 단순하다. 피보나치 수열과 함께 금성출판사의 푸르넷 초등 4학년 교재의 규칙 찾기 단원에 언급될 정도다. 당장 사칙연산과 자연수의 개념만 알아도 콜라츠 추측의 이해가 가능하기 때문이다. 페르마의 마지막 정리는 그래도 지수의 개념은 알아야 되고 리만 가설도 복소수와 리만 함수에 대한 이해가 필요하다는 점을 생각해보면 콜라츠 추측이 얼마나 단순한지 알 수 있다.지금 당장 구글에 The proof of the Collatz conjecture이라고 검색하면 전문 수학자부터 20세, 심지어 15세가 쓴 논문까지 있다. 그리고 아무것도 동료평가를 통과하지 못했다. 이렇게 계속 증명 시도가 좌절되니 괴델의 불완전성 정리에 따른 증명 불가능설이 고개를 들고 있으며 상당한 신빙성을 얻고 있다.[8]
5. 테렌스 타오의 접근
2019년 9월 8일 테렌스 타오가 콜라츠 추측을 건드렸다.논문기사- 어떤 함수 [math(f(x))]에서
- [math(x)]가 무한히 커질 때 [math(f(x))]도 무한이 되면
- 거의 모든 자연수 [math(N)]에 콜라츠 함수를 반복하면 [math(f(N))] 이하로 언젠가는 떨어진다.
- '거의 모든'이라는 표현이 언뜻 보기엔 수학적이지 않아 납득이 안 갈 수 있는데, 사실 이는 수학적 표현이다. 조건을 만족시키는 수의 확률이 1에 수렴한다는 것을 의미한다.[9]
- 이 말은 '거의 모든 자연수에 대하여 콜라츠 추측이 성립한다'와 동치이다. 로그를 여러 번 사용한 함수같이 매우 천천히 무한으로 발산하는 함수가 있기 때문이다.
물론 이 말은 콜라츠 추측 자체를 증명한 것이 아니다.[10] 참고로 "콜라츠 추측은 (거의) 필연적으로 감소한다"는 것은 타오 이전에도 이미 증명되었는데 1976년에 [math(f(x)=x)]인 경우[11][12]가 1979년에 [math(f(x)=x^{0.869})]인 경우가, 1994년에 [math(f(x)=x^{0.7925})]인 경우가 증명되었기 때문이다. 즉 타오의 업적은 이를 엄청나게 일반화 시켜서 '거의 모든 자연수에 대하여 콜라츠 추측이 성립한다'를 증명한 것이다.[13] 2020년 타오 본인이 정리한 프레젠테이션을 보면 관련 내용이 언급된다.
타오가 제시한 방법은 Forum of Mathematics, Pi에 게재되었다저널 논문. 물론 이 증명이 참이라 해도 여전히 반례가 존재할 가능성은 있다. 단적으로 임의의 [math(N\in\N)]이 합성수일 확률은 1에 수렴하지만(즉 거의 모든 자연수는 합성수이지만) 그 반례인 소수는 가산무한히 많음이 잘 알려져 있다. "거의 확률이 0이다" 라는 명제는 실험 가능한 방법으로, 대표적으로 컴퓨터를 이용한 난수 추출법이나 몬테 카를로 방법 등을 통해서 증명할 수 없다. 모든 자연수 중에 하나의 수를 동등한 확률로 추출하는 것이 불가능하기 때문이며, 컴퓨터 안에 내장되어 있는 난수 추출 함수도 범위에 제약이 있다. 자연수 집합에 적당한 가중치 a(n)을 주고 그 무한 급수의 합이 수렴하는 형태로 하면 범위 제약이 없는 난수 추출은 가능하지만 이것 역시 모든 자연수가 공평하게 나오지 않고 n이 커지면 그 자연수가 나올 확률이 줄어서 소수가 나올 확률이 거의 0임을 입증하는 것은 불가능하다.
6. 여담
만약 이 추측이 거짓이라면 1로 가지 않는 반례가 존재한다는 것을 의미한다. 수학자들은 이런 '예상되는 반례'가 만약 진짜 존재한다면, 자기 자신으로 순환하는 루프가 존재할 것으로 생각한다.[14] 예를 들어 콜라츠 추측을 [math(3n+1)] 이 아니라 [math(3n-1)] 로 살짝 변경하면 5의 경우 아래와 같은 루프가 만들어 진다.| 5 → 14 → 7 → 20 → 10 → 5 |
| 17 → 50 → 25 → 74 → 37 → 110 → 55 → 164 → 82 → 41 → 122 → 61 → 182 → 91 → 272 → 136 → 68 → 34 → 17 |
[math(3n-1)] 문제는 [math(3n+1)] 문제를 음수로 확장한 것과 동일하다. 즉, 위의 2개의 루프를 음수로 확장한 [math(3n+1)] 로 생각할 경우 아래와 같이 된다.
| -5 → -14 → -7 → -20 → -10 → -5 |
| -17 → -50 → -25 → -74 → -37 → -110 → -55 → -164 → -82 → -41 → -122 → -61 → -182 → -91 → -272 → -136 → -68 → -34 → -17 |
그리고, 4 → 2 → 1 루프와 마찬가지로 -1 → -2 로 로 반복되는 기본 루프가 또하나 존재한다.
다른 가능성으로는 무한히 발산한다는 것이 있다. 단 이는 반례의 존재 증명이 어렵다는 문제점이 있다. 그래서 허무맹랑해 보이기도 하지만 존재하지 않는 것이 거의 확실해 보이기로는 순환 루프나 발산이나 오십보백보 수준이다.
7. 둘러보기
| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <bgcolor=#46786a> 이론 | |
| <colbgcolor=#46786a> 기본 대상 | 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오(예상과 확인) · 불 논리(격자) · 브라에스 역설 · 차분 · 포함-배제의 원리 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
| [[이론 컴퓨터 과학|'''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"]] | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36,#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 · 디지털 물리학 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 정보 엔트로피 · 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타프로그래밍 · 람다 대수 · 타입 이론 · 프로그래밍 언어 의미론 · 어휘 분석 · 파싱 · 구문 트리(완전 구문 트리 · 추상 구문 트리) · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set) · 트리^이진 트리(레드-블랙 트리, 힙), B-트리, 피보나치 힙^ · 큐 · 스택 | ||||
| 수학적 최적화 | <keepall> 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| <keepall> 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| <keepall> 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 · 난수생성 | ||||
| <keepall> 대칭키 암호화 방식 | 블록 암호 알고리즘(파이스텔 네트워크 · DES · AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| <keepall> 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
8. 외부 링크
[1] 《The Ultimate challenge: The 3x+1 problem》이라는 관련 서적을 쓰기도 했으며 이외에도 리만 가설을 조화수열 형태로 정리한 걸로 유명하다.[2] Barína, D. (2025). Improved verification limit for the convergence of the Collatz conjecture. Journal of Supercomputing, 81, Article 810. https://doi.org/10.1007/s11227-025-07337-0[3] 에르되시가 500달러를 걸었지만 증명이 안 되자 "수학은 아직 이런 문제를 풀 준비가 되어있지 않다"(Mathematics may not be ready for such questions)라는 말을 남겼다.[4] 사실 이 [math(g)]가 튜링 완전하기 때문에 정지 문제가 적용된다. 그래서 이걸로 만든 프로그래밍 언어를 FRACTRAN이라고 한다. 콘웨이가 짠 [math(P=6\,469\,693\,230)]짜리 소수 생성 프로그램은 덤[5] [math(P=1)], [math(g(x)=2x)]와 같은 경우가 있다.[6] 즉 [math(P)]와 [math(g)]가 정해진 경우[7] 정작 원본 콜라츠 추측과 동치인 튜링 머신은 아직 발견되지 않았으며, 대신 약한 콜라츠 추측과 동치인 124 상태 바쁜 비버가 있다.[8] 상술했듯 이미 일반화한 문제는 결정 불가능함이 증명되었기도 하다.[9] 참고로 '거의 모든'(almost all, almost everywhere 등)은 분야마다 조금씩 다른 의미로 쓰이는데, 해석적 정수론과 확률론 등 해석학 계열 연구분야에서는 이 말을 '해당 조건을 만족하지 못하는 원소의 모임은 측도 0이다'나 '이 성질이 성립할 확률이 1에 수렴한다' 등의 의미로 사용하는 경우가 많다. 해석학적 맥락에서 이들은 사실상 같은 뜻이며, 위상수학 및 동역학계 관련 분야에서 쓰이는 경우에도 제각기 비슷한 맥락의 의미로 쓰인다.[10] 당장 아래 문단에 있는 [math(3n-1)] 문제에 대해서도 같은 논리를 적용할 수 있기 때문이고 이 문제의 경우 1로 끝나지 않는 루프가 발견되었기 때문이다.[11] 즉, 콜라츠 함수를 반복할 경우 초기값보다 작아질 확률은 1이다.[12] 이 버전을 거의 모든 자연수 [math(N)]에서 모든 자연수 [math(N)]으로 바꿔 증명할 수만 있다면 콜라츠 추측도 무한강하법으로 증명할 수 있지만 아직까진 아무도 성공하지 못했다.[13] 참고로 2003년에는 충분히 큰 자연수 [math(N)]에 대해 [math(N)] 이하의 자연수 중 최소 [math(N^{0.84})]만큼은 콜라츠 추측이 성립한다는 것이 증명되었다.[14] 1993년 Eliahou는 반례가 등장할 수 있는 루프의 길이를 구하는 공식을 발견했는데 최소길이가 무려 17,087,915이므로 루프를 찾기가 쉽지는 않다.