50년 만에 비버 수 돌파...컴퓨터 과학자들, 또 다른 벽에 부딪히다

비버 문제 연구진, 콜라츠 추측과 유사한 안티히드라 때문에 BB(6) 계산 난항... 이론 컴퓨터 과학계가 BB(5) 수 계산에 성공했지만, 다음 단계인 BB(6) 계산이 수학 난제와 맞물려 난항을 겪고 있다.

[한국정보기술신문] 지난 2024년 여름, 온라인 커뮤니티가 50년 만에 비버 수 문제에서 획기적인 성과를 거두었다. 연구진은 BB(5)의 정확한 값이 47,176,870임을 밝혀냈다. 비버 수는 단순한 컴퓨터 프로그램이 완료할 수 있는 가장 복잡한 계산의 난이도를 측정하는 지표다.

이제 연구진은 여섯 번째 비버 수인 BB(6)를 찾는 작업에 착수했다. 그러나 이 과정에서 안티히드라라는 프로그램이 큰 장애물로 떠올랐다. 안티히드라는 수학의 오래된 난제인 콜라츠 추측과 유사한 구조를 가지고 있어, 해당 프로그램이 멈출지 여부를 판단하기 어렵다.

비버 게임은 튜링 머신이라는 가상의 장치를 사용해 컴퓨터 프로그램의 복잡도를 측정한다. 튜링 머신은 무한한 테이프에 0과 1을 읽고 쓰며 계산을 수행한다. BB(6)는 6개의 규칙을 가진 튜링 머신 중 가장 오래 실행되는 프로그램의 실행 시간을 의미한다.

안티히드라의 정체

안티히드라는 다음과 같은 규칙으로 작동한다. 처음 x값을 8로 설정한 뒤, x가 짝수면 3x/2를, 홀수면 (3x-1)/2를 계산한다. 이때 짝수 규칙과 홀수 규칙을 적용한 횟수를 각각 기록한다. 홀수 규칙 적용 횟수가 짝수 규칙의 2배를 초과하면 프로그램이 멈춘다.

연구진은 안티히드라를 2,700억 단계 이상 시뮬레이션했지만, 짝수와 홀수 카운트가 거의 동일한 수준을 유지해 멈춤 조건에 도달하지 못했다. 확률적으로 안티히드라가 영원히 멈추지 않을 것으로 보이지만, 이를 수학적으로 증명할 방법이 없다는 것이 문제다.

콜라츠 추측과의 유사성

1937년 수학자 로타르 콜라츠가 고안한 콜라츠 추측은 다음과 같다. 임의의 양의 정수에서 시작해, 짝수면 2로 나누고 홀수면 3을 곱한 뒤 1을 더한다. 이 과정을 반복하면 결국 1에 도달한다는 것이다. 현재까지 2,000조 이상의 숫자에서 예외가 발견되지 않았지만, 엄밀한 증명은 아직 이루어지지 않았다.

안티히드라의 행동 양상은 콜라츠 추측과 질적으로 유사하다. 두 문제를 해결하는 직접적인 수학적 연결고리는 없지만, 비슷한 이유로 어렵다는 점에서 공통점이 있다. 만약 누군가 콜라츠 추측을 증명한다면, 그 증명에 사용된 수학적 기법이 안티히드라 문제 해결에도 유용할 것으로 예상된다.

크립티드의 출현

비버 헌터 숀 리고키는 안티히드라와 같이 멈추지 않을 것으로 보이지만 증명할 수 없는 튜링 머신들을 크립티드라고 명명했다. 처음 발견된 두 크립티드는 빅풋과 히드라로 이름 붙여졌으며, 현재는 너무 많은 크립티드가 발견되어 각각에 이름을 붙이는 것이 무의미해졌다.

이러한 크립티드들의 존재는 BB(5) 이후의 비버 수를 계산하려면 콜라츠 유형 문제를 다루는 새로운 수학적 도구가 필요함을 시사한다. 전설적인 수학자 폴 에르되시는 이러한 문제들에 대해 수학이 아직 준비되지 않았다고 말한 바 있다.

그러나 연구진은 포기하지 않고 있다. 크립티드의 종류와 그들 간의 관계, 다른 미해결 수학 문제와의 연관성 등을 탐구하는 크립티드 생태학이라는 새로운 연구 분야가 형성되고 있다. 비버 게임의 시작부터 지금까지, 연구자들은 계속해서 놀라운 튜링 머신의 행동을 발견해왔으며 이러한 패턴은 앞으로도 계속될 것으로 보인다.

한국정보기술신문 인공지능분과 김주호 기자 news@kitpa.org