비지 비버 함수와 정지 문제, 어떤 알고리즘으로도 계산할 수 없는 수가 존재하는 이유

핵심 메시지

• 비지 비버 함수는 n개 상태를 가진 튜링 머신 가운데 정지한 것이 남긴 1의 최대 개수로, 2·3·4상태에서 각각 4, 6, 13이라는 값이 알려져 있다.
• 4상태만 해도 250억 개가 넘는 머신을 따져야 했고, 5상태 값은 아직 인류가 계산하지 못했다.
• 비지 비버 함수는 계산 가능한 함수가 아니며, 어떤 계산 가능한 함수보다도 빠르게 증가한다.
• 골드바흐 추측이 거짓일 때만 멈추는 27상태 튜링 머신이 존재하기 때문에, 이 수들은 수학의 미해결 문제에 관한 정보를 품고 있다.
• 어느 지점을 넘어서면 참인데도 통상의 공리계로는 증명할 수 없는 값들이 나타난다.

쉽게 이해하기

화자는 그레이엄 수나 TREE(3) 같은 거대한 수를 다룬 영상을 다시 보다가, 비지 비버 값이 그보다도 크냐는 대목에 붙들려 이 주제로 들어갔다고 말한다. 그러고는 자신이 한 일은 스콧 아론슨을 비롯한 연구자들의 글을 읽은 것뿐이라며, 이 영상을 그 아이디어의 전달로 봐 달라고 미리 선을 긋는다. 겸손한 전제이지만 설명은 오히려 그 덕분에 군더더기가 없다.

출발점은 이진 튜링 머신이다. 0과 1이 적힌 무한한 테이프가 있고, 기계는 내부 상태를 가진 채 칸을 읽어 0이나 1을 쓰고 좌우로 한 칸 움직이며 다음 상태로 넘어가거나 멈추는데, 이 동작 전체가 상태 표 한 장에 적힌다. 여기에 두 가지 사실이 얹힌다. 처치-튜링 논제에 따르면 입력에 유한한 단계를 적용해 출력을 내는 모든 계산은 어떤 튜링 머신의 동작과 같으므로, 튜링 머신에 대해 말하는 것은 파이썬 함수든 C++ 프로그램이든 컴퓨터가 하는 모든 일에 대해 말하는 것이 된다. 다른 하나는 정지 문제로, 임의의 상태 표와 테이프를 받아 그 기계가 멈출지 판정하는 알고리즘은 존재하지 않지만 특정한 기계와 테이프에 한해서는 전용 알고리즘이 답을 낼 수도 있다는 단서가 붙는다.

비지 비버 함수는 이렇게 정의된다. n개 상태를 갖는 모든 튜링 머신을 전부 0인 테이프 위에서 돌린 뒤, 멈춘 것들 가운데 1을 가장 많이 써넣은 개수를 취한다. 2상태는 4, 3상태는 6, 4상태는 13이다. 상태가 하나 늘 때마다 기계의 수는 지수적으로 불어나 4상태에서 이미 250억 개를 넘었고, 그 전부를 따져 13이라는 답을 얻는 데 상당한 노력이 들었다. 5상태는 조 단위의 기계를 다뤄야 해 아직 답이 없다. 진짜 어려움은 개수가 아니라 어떤 기계가 멈추는지를 가리는 일에 있고, 일반적인 해법이 없어 기계 하나하나를 두고 수년씩 이론적으로 씨름해야 한다.

그런데 이 함수는 계산이 어려운 정도가 아니라 아예 계산 가능한 함수가 아니다. 어떤 기계는 영원히 돌기 때문에 모든 n에 대해 답을 내는 유한한 절차가 존재하지 않는다. 특정한 n을 고르면 기계의 집합이 유한해지므로 분석으로 답에 이를 수 있다는 것이 4상태 값을 아는 이유다. 더 나아가 이 수열은 어떤 계산 가능한 함수보다도 빠르게 자란다. 화자는 계승을 지수로 올린 표기를 만들고 그것을 다시 중첩해 감당 못 할 크기의 함수를 지어내 도전하지만, 어느 지점부터는 아예 상대가 되지 않는다. 진 이유가 명료하다. 자신의 함수는 유한한 절차로 기술할 수 있었고, 그것이 곧 계산 가능하다는 뜻이었기 때문이다.

마지막으로 이야기는 수학의 기초로 넘어간다. 골드바흐 추측이 거짓일 때만 멈추는 27상태 튜링 머신이 존재하므로, 각 기계의 정지 여부를 판정하는 정공법으로 27상태 값을 구한다면 수백 년 묵은 이 미해결 문제가 함께 풀리게 된다. 리만 가설에 대해서도 비슷한 일이 성립한다. 화자는 이 문제들을 직접 풀지 않고 우회하는 경로가 있을 수도 있다고 단서를 달면서도, 요점은 이 수들이 수학의 상당 부분에 관한 정보를 품고 있다는 데 있다고 말한다. 여기서 한 걸음 더 나가면, 특정 상태 수의 값이 어떤 수와 같다는 참인 명제 가운데 통상의 공리계로는 증명할 수 없는 것들이 나타난다.

주요 인사이트

• 비지 비버 함수는 계산의 한계를 추상적인 정리가 아니라 하나의 고정된 수열로 보여준다. 이 수열 자체가 계산 가능한 영역과 불가능한 영역을 가르는 경계선인 셈이다.
• 정지 문제의 결론은 '어떤 프로그램도 판정할 수 없다'가 아니라 '모든 경우에 통하는 단일 알고리즘이 없다'는 것이다. 이 구분을 놓치면 왜 특정 상태 수의 값은 알 수 있는지가 설명되지 않는다.
• 화자가 직접 초고속 증가 함수를 만들어 도전했다가 완패하는 대목이 핵심을 가장 잘 드러낸다. 표기를 아무리 중첩해도 그것이 유한한 절차로 적히는 한 계산 가능한 함수이고, 그 순간 승부는 끝나 있었다.
• 골드바흐 추측과 리만 가설이 특정 상태 수의 값에 걸려 있다는 사실은, 이 수들이 단순히 크기만 한 것이 아니라 수학적 정보를 압축해 담고 있음을 보여준다.
• 어느 지점을 넘어서면 참인데도 증명할 수 없는 값이 나타난다는 것은, 수학이 이 대상에 대해 주장할 능력 자체를 잃는 지점이 있다는 뜻이다.

자주 묻는 질문

관련 AI 소식