콜라츠의 추측으로 본 프로그램의 속성
콜라츠의 추측(Collatz Conjecture)은 아래 두가지 간단한 상태변화를 다루는 프로그램이다.
1. x가 짝수이면 2로 나눈다.
2. x가 홀수이면 3*x + 1을 한다.
그런데 놀랍게도 거의 모든 양의 정수가 이 과정을 반복하면 1로 귀결될 것으로 추측되고 있다.
그런데 재미있는 것은 이 콜라츠의 추측이 모든 양의 정수에서 성립하는지 증명되지 않고 있다는 사실이다. 이 프로그램이 나타내는 숫자 변환은 마치 랜덤처럼 변화하면서 숫자가 평균적으로 작아지기는 하지만, 모든 숫자가 그런지는 알려지지 않았다.
이 문제는 기존에 지적한 대로 골드바흐의 추측과 같은 속성을 지닌다.
즉 2부터 2를 더하면서 해당 수가 두 소수의 합인지 조사하고 해당 만족하는 소수가 없으면 중단하라는 프로그램을 만든 후 프로그램이 중단하는지 조사하는 문제와 같다.
콜라츠의 추측도 동일하게, 수를 1부터 1씩 증가시켜 가면서 상기 콜라츠의 추측 검사를 하고 1로 귀결되지 않으면 멈추도록 한 후 해당 프로그램이 중단하는지 검사하는 문제가 된다.
만약에 칸토어가 집합론을 가지고 수라는 집합의 무한의 정도를 분류한 것처럼, 만약에 우리가 위 프로그램을 분류하고 등급화하는 방법을 만들면 어떨까?
칸토어는 상태에 대한 정리를 한 셈인데, 거듭되는 변환에 대해서는 아직 체계화된 메타 학문이 없는 셈이다. 어떤 도구를 가지고 이 프로그램들을 분류하고 유형화할 수 있을까? 그리고 이미 불가능하다고 증명된 이 정지여부 검사는 또 어떻게 조금더 개선할 수 있는 방법을 찾을 수는 없을까?