차이틴 상수

3. 정의

접두어 없는 보편 계산 가능 함수 ''F''의 정의역을 ''P_F''라 할 때, 차이틴 상수 Ω_''F''는 다음과 같이 정의된다.

:$\backslash Omega\_F\; =\; \backslash sum\_\{p\; \backslash in\; P\_F\}\; 2^\{-|p|\}$

여기서 $\backslash left|p\backslash right|$는 문자열 ''p''의 길이를 나타낸다. 크래프트-맥밀런 부등식에 의해 이 무한합은 0과 1 사이의 실수로 수렴한다. Ω_''F''의 값은 ''F''에 따라 달라지지만, ''F''가 무엇인지 분명한 경우에는 그냥 Ω라고 쓸 수 있다.

3. 1. 예시

4. 정지 문제와의 관계

Ω의 첫 ''N'' 비트를 알면 길이 ''N'' 이하의 모든 프로그램에 대해 정지 문제를 해결할 수 있다. 프로그램 ''p''가 정지하는지 알고 싶을 때, ''p''의 길이를 ''N''이라고 하고, 길이 ''N'' 이하의 모든 프로그램을 동시에 실행한다. Ω의 근삿값을 처음에 0이라 두고 길이 ''n''인 프로그램 하나가 정지할 때마다 2^''n''을 더한다. 충분한 시간이 지나면 근삿값이 Ω의 첫 ''N'' 비트와 일치하는데, 이때 ''p''가 정지하지 않았다면 영원히 정지하지 않음을 알 수 있다. ''p''가 정지한다면 근삿값의 ''N''번째 비트가 달라지기 때문이다. 따라서 ''p''가 정지하는지 유한 시간 내에 결정할 수 있다.^[5]

도브테일링 방식으로 모든 길이의 모든 프로그램을 실행하여, 충분한 프로그램이 정지하여 처음 ''N'' 비트를 일치시킬 만큼 충분한 확률을 공동으로 기여할 때까지 실행한다. 프로그램 ''p''가 아직 정지하지 않았다면, 이는 정지 확률에 대한 기여가 처음 ''N'' 비트에 영향을 미치므로, 절대 정지하지 않는다. 따라서, ''p''에 대한 정지 문제가 해결된다.^[5]

골드바흐의 추측이나 리만 가설과 같은 수론의 많은 미해결 문제들이 특별한 프로그램(반례를 검색하고 발견되면 정지하는 프로그램)에 대한 정지 문제 해결과 동일하기 때문에, 차이틴 상수의 충분한 비트를 아는 것은 이러한 문제에 대한 답을 아는 것을 의미한다. 그러나 정지 문제는 일반적으로 해결할 수 없으며, 따라서 보편적인 언어에 대해 차이틴 상수의 처음 몇 비트를 제외하고는 계산할 수 없다. 이는 정지 문제를 위한 오라클 머신을 구축하려는 시도와 마찬가지로 어려운 문제를 불가능한 문제로 축소시킨다.^[5]

골드바흐의 추측이란, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 어떤 짝수가 주어졌을 때, 그것을 두 소수의 합으로 분해하는 프로그램을 생각한다. 골드바흐의 추측이 옳다면, 이 프로그램은 짝수를 차례로 두 소수로 분해해 나갈 것이다. 소수로 분해할 수 없는 짝수라는 반례가 발견된 경우, 프로그램은 멈추고, 골드바흐의 추측은 틀렸다는 것이 증명된다. 이 프로그램의 길이를 ''N'' 비트라고 한다. 계산 자원과 시간에 제한이 없는 경우, 차이틴 상수를 사용하여 골드바흐의 추측을 증명할 수 있다. 동시에, 길이가 ''N'' + 1 비트 이하인 모든 프로그램을 실행한다. ''N'' 비트인 골드바흐 프로그램이 멈추면, 추측은 거짓이었음이 증명된다. 만약 이와 반대로, 다른 프로그램들이 계속 멈춰서 하나라도 더 멈추면 차이틴 상수를 초과하는 상황이 되어, 그 시점에서 아직 골드바흐 프로그램이 멈추지 않았다면, 더 이상 골드바흐 프로그램은 멈출 수 없으므로, 골드바흐의 추측이 옳다는 것이 증명된다. 이 방법을 사용하는 데에는, 차이틴 상수의 선두부터 ''N'' + 1 비트까지의 값만 알면 된다.^[5]

마찬가지로, 리만 가설 등 수학의 미해결 문제의 대부분도, 차이틴 상수를 사용하여 증명(또는 반증)할 수 있다.^[5]

위의 설명은 재귀적 공리화 가능 이론의 증명 가능성 술어가 차이틴 상수로부터 상대적으로 계산 가능하다는 것을 보여주는 것에 불과하다. 위의 방법으로 미해결 문제의 증명 가능성을 판정하기 위해 필요한 비트 길이는 방대하며, 차이틴 상수의 정확한 값을 필요한 만큼 구하는 것은 어렵다. 만약 필요한 만큼의 비트가 구해졌다고 하더라도, 위의 알고리즘의 계산량은 방대하다. 따라서 위의 방법으로 미해결 문제의 증명 가능성을 판정하는 것이 실제적인 의미에서 가능하다는 것은 아니다.^[5]

5. 확률로서의 해석

칸토어 공간은 0과 1로 이루어진 모든 무한 수열의 집합이다. 정지 확률은 칸토어 공간에 대한 일반적인 측도 하에서 칸토어 공간의 특정 부분 집합의 확률 측도로 해석될 수 있다.

칸토어 공간에 대한 확률 측도는, 때로는 공정한 동전 측도라고도 하며, 모든 이진 문자열 ''x''에 대해 ''x''로 시작하는 수열의 집합이 측도 2^−|''x''|을 갖도록 정의된다. 이는 각 자연수 ''n''에 대해, 칸토어 공간에서 ''f''(''n'') = 1인 수열 ''f''의 집합이 측도 1/2를 가지며, ''n''번째 요소가 0인 수열의 집합도 측도 1/2를 갖는다는 것을 의미한다.

''F''를 접두사 없는 보편적 계산 가능 함수라고 하자. ''F''의 정의역 ''P''는 무한 집합의 이진 문자열로 구성된다.

:$P\; =\; \backslash \{p\_1,p\_2,\backslash ldots\backslash \}$.

이러한 각 문자열 ''p''_''i''는 칸토어 공간의 부분 집합 ''S''_''i''를 결정한다. 집합 ''S''_''i''는 ''p''_''i''로 시작하는 칸토어 공간의 모든 수열을 포함한다. 이러한 집합은 ''P''가 접두사 없는 집합이기 때문에 서로소이다. 합계

:$\backslash sum\_\{p\; \backslash in\; P\}\; 2^\{-|p|\}$

는 집합

:$\backslash bigcup\_\{i\; \backslash in\; \backslash mathbb\{N\}\}\; S\_i$의 측도를 나타낸다.

이러한 방식으로 Ω_''F''는 무작위로 선택된 0과 1의 무한 수열이 ''F''의 정의역에 있는 비트 문자열(일정 길이)로 시작할 확률을 나타낸다. 이러한 이유로 Ω_''F''가 정지 확률이라고 불린다.

6. 성질

• Ω의 자릿수는 알고리즘적 무작위성을 지닌다. (마르틴-뢰프 무작위성이나 1-무작위성이라고도 한다.)^[1] 즉, Ω의 첫 ''n'' 비트를 출력하는 프로그램의 길이는 적어도 ''n'' - O(1)은 되어야 한다.
• 따라서 Ω는 정규수이다. 즉, Ω의 자릿수는 동전을 던져 만든 수열처럼 균등한 분포를 보인다.
• Ω는 계산 가능한 수가 아니다. 즉, Ω의 자릿수를 출력하는 계산 가능 함수는 없다.
• Ω보다 작은 유리수의 집합은 계산 열거 가능 집합이다.^[1] 이런 성질을 가진 실수를 '''왼쪽 열거 가능 수'''라 한다.
• Ω보다 큰 유리수의 집합은 계산 열거 가능 집합이 아니다. 왼쪽 열거 가능하면서 오른쪽 열거 가능한 실수는 계산 가능하지만, Ω는 계산 불가능하기 때문이다.
• Ω는 산술적 수이다. 즉, 1차 페아노 공리계에서 정의할 수 있다.
• Ω는 정지 문제와 튜링 동치이며 따라서 산술적 위계에서 $\backslash Delta^0\_2$에 속한다.

7. 계산 불가능성

어떤 정지 확률도 계산 불가능하다. 주어진 Ω의 처음 ''n''자리를 사용하여 길이가 최대 ''n''인 프로그램의 튜링 정지 문제를 해결할 수 있지만, 정지 문제는 결정 불가능 문제이므로 Ω는 계산될 수 없다.

알고리즘은 다음과 같이 진행된다. Ω의 처음 ''n''자리와 ''k'' ≤ ''n''이 주어지면, 알고리즘은 해당 확률이 Ω의 2^−(''k''+1) 이내에 들어올 만큼 충분한 도메인 요소를 찾을 때까지 ''F''의 도메인을 열거한다. 이 시점 이후에는 길이 ''k''인 추가 프로그램이 도메인에 있을 수 없다. 왜냐하면 각 프로그램은 측정값에 2^−''k''을 더할 것이고, 이는 불가능하기 때문이다. 따라서 도메인에서 길이 ''k''인 문자열 집합은 이미 열거된 해당 문자열 집합과 정확히 일치한다.

8. 알고리즘적 무작위성

Ω의 자릿수는 알고리즘적 무작위성(마르틴-뢰프 무작위성이나 1-무작위성이라고도 한다)을 지닌다.^[2] 즉, Ω의 첫 ''n'' 비트를 출력하는 프로그램의 길이는 적어도 ''n'' - O(1)은 되어야 한다. 실수는 그 실수를 나타내는 이진 수열이 알고리즘적 무작위 수열일 경우 무작위적이다. Calude, Hertling, Khoussainov, Wang은 재귀적으로 열거 가능한 실수가 알고리즘적 무작위 수열이기 위한 필요충분조건이 차이틴의 Ω 수인 경우임을 보였다.^[2]

9. 불완전성 정리

차이틴의 불완전성 정리에 따르면, 페아노 공리계에서는 Ω의 자릿수 가운데 기껏해야 유한 개만을 증명할 수 있다. 즉, ''N''보다 큰 자연수 ''n''에 대해서는 Ω의 ''n''번째 자릿수가 0이라고 또는 1이라고 증명할 수 없는 자연수 ''N''이 존재한다.

각각의 특정한 일관적이고 효과적으로 표현된 공리적 체계는 페아노 공리계와 같이 자연수에 대해 존재하며, 해당 체계 내에서 ''N''번째 이후의 Ω 비트가 1 또는 0으로 증명될 수 없는 상수 ''N''이 존재한다. 상수 ''N''은 형식적 시스템이 효과적으로 표현되는 방식에 따라 달라지므로, 공리적 체계의 복잡성을 직접적으로 반영하지 않는다. 이 불완전성 결과는 산술에 대한 어떤 일관적인 형식적 이론도 완전할 수 없다는 것을 보여준다는 점에서 괴델의 불완전성 정리와 유사하다.

10. 슈퍼 오메가

차이틴의 상수 Ω의 처음 n 비트는 n-O(1) 비트 미만의 정지 알고리즘으로는 계산할 수 없다는 점에서 무작위이거나 압축할 수 없다. 그러나 모든 가능한 프로그램을 체계적으로 나열하고 실행하는 짧지만 결코 정지하지 않는 알고리즘을 생각해 보자. 그 중 하나가 정지할 때마다 해당 확률이 출력에 추가된다(0으로 초기화됨). 유한 시간이 지나면 출력의 처음 n 비트는 더 이상 변경되지 않는다(이 시간 자체가 정지 프로그램으로 계산할 수 없다는 것은 중요하지 않다). 따라서 출력값이 (유한 시간이 지난 후) Ω의 처음 n 비트로 수렴하는 짧은 비정지 알고리즘이 있다. 즉, Ω의 가산 처음 n 비트는 매우 짧은 알고리즘에 의해 극한 계산 가능하다는 점에서 매우 압축 가능하다. 열거 알고리즘 집합과 관련하여 무작위가 아니다. 위르겐 슈미드후버(en)는 원래의 극한 계산 가능 Ω보다 어떤 의미에서 훨씬 더 무작위인 극한 계산 가능 "슈퍼 Ω"를 구성했는데, 이는 어떤 열거 비정지 알고리즘으로도 슈퍼 Ω를 크게 압축할 수 없기 때문이다.^[3]

또 다른 "슈퍼 Ω"의 경우, 접두사 없는 보편 튜링 기계의 보편성 확률, 즉 (이진 문자열로) 모든 입력 앞에 무작위 이진 문자열이 붙더라도 보편성을 유지할 확률은 정지 문제의 세 번째 반복(즉, 튜링 점프 표기법을 사용하여 $O^\{(3)\}$)의 오라클을 가진 기계의 비정지 확률로 볼 수 있다.^[4]

참조

_[1] 웹사이트 Chaitin's Constant https://mathworld.wo[...] 2024-09-03
_[2] 간행물 Recursively Enumerable Reals and Chaitin Ω numbers https://www.cs.auckl[...] Springer Berlin Heidelberg 2022-03-20
_[3] 논문 Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit
_[4] 논문 Universality probability of a prefix-free machine 2012
_[5] 서적 Elements of Information Theory Wiley-Interscience 2006
_[6] 웹사이트 Chaitin's Constant http://mathworld.wol[...] 2012-05-28