차이틴 상수

알고리즘 정보 이론에서 차이틴 상수(Chaitin's constant) 또는 차이틴 오메가 수(Chaitin omega number) 또는 정지 확률은 무작위로 만들어진 프로그램이 정지할 확률을 나타내는 실수이다. 그레고리 차이틴이 정의하였다.

무작위로 만든 프로그램이 정지할 확률은 프로그램을 0과 1로 부호화하는 방식에 따라 달라진다. 따라서 무한히 많은 종류의 ‘정지 확률’이 존재하지만, 마치 단 하나만 존재하는 것처럼 취급하고 그리스 글자 오메가(Ω)로 나타내는 경우가 많다. 특정한 부호화 방식을 염두에 둔 것이 아닐 때에는 상수라는 이름 대신 차이틴 구성(Chaitin's construction)이라는 이름을 사용하기도 한다.

각각의 정지 확률은 초월수이고 정규수이며, 계산 불가능한 수이다. 계산 불가능하다는 것은 그 값을 임의의 정확도로 계산하는 알고리즘이 존재할 수 없다는 뜻이다. 나아가 각각의 정지 확률은 마르틴-뢰프 무작위적이다.

배경

정지 확률을 정의하려면 접두어 없는 보편 계산 가능 함수(prefix-free universal computable function)가 주어져야 한다. 쉽게 말하면 이것은 튜링 완전한 프로그래밍 언어이면서, 올바른 프로그램 뒤에 내용을 덧붙여 또다른 올바른 프로그램을 만들 수 없는 성질을 지닌 언어라고 할 수 있다. 즉, 올바른 프로그램 코드의 접두어 중에는 올바른 프로그램이 없다는 것이다.

앞으로 ‘문자열’은 0과 1로 이루어진 유한한 이진 문자열을 나타낸다. 문자열 하나를 받아서 문자열 하나를 돌려주거나 아무것도 돌려주지 않는 부분 정의 함수 F가 있다고 하자. 만약 F를 계산하는 튜링 기계가 존재한다면, F를 계산 가능 함수라고 한다.

함수 F가 다음 성질을 만족하면 F가 보편적(universal)이라고 한다.

임의의 일변수 계산 가능 함수 f에 대해 문자열 w가 존재하여, 모든 x에 대해 F(w x) = f(x)이다.

단, w x는 w와 x를 이어붙인 문자열을 나타낸다. 달리 말하면 F는 임의의 일변수 계산 가능 함수를 흉내낼 수 있다는 것이다. 말하자면 w는 계산 가능 함수 f의 ‘코드’이고, F는 ‘인터프리터’로서 자신이 받은 입력의 앞부분을 코드로 해석하여 뒷부분에 실행한다고 할 수 있다.

부분 정의 함수 F의 정의역은 F(p)의 값이 정의되는 모든 p의 집합을 가리킨다. 즉 F를 계산하는 튜링 기계가 언젠가 정지해서 출력값을 돌려주게 만드는 입력값들의 집합이다. 이러한 p는 프로그램 부분과 데이터 부분을 모두 포함한다고 생각할 수도 있고, 단일한 프로그램이라고 생각할 수도 있다.

함수 F가 다음 성질을 만족하면 F가 접두어 없는(prefix-free) 함수라 한다.

p와 q가 F의 정의역에 속하면, p는 q의 접두어가 아니다.

달리 말하면 F의 정의역이 앞자리 부호라는 것이다.

보편 계산 가능 함수의 정의역은 계산 열거 가능 집합이지만, 계산 가능 집합은 아니다. 보편 계산 가능 함수의 정의역을 결정하는 문제는 정지 문제와 동치이기 때문이다.

정의

함수 F가 접두어 없는 보편 계산 가능 함수라 하고, 그 정의역을 P_F로 나타내자. 그러면 다음 값을 차이틴 상수 Ω_F라 한다.

$\Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}$

이때 $\left|p\right|$는 문자열 p의 길이를 나타낸다. 접두어가 없다는 조건과 크래프트-맥밀런 부등식 때문에 이 무한합은 0과 1 사이의 실수로 수렴함이 보장된다. Ω_F의 값은 F에 따라 달라지지만, F가 무엇인지 분명한 경우에는 그냥 Ω라고 쓸 수 있다.

Calude et al. (2002)에서는 특정한 접두어 없는 보편 튜링 기계 U에 대해 Ω_U을 이진법으로 나타냈을 때 첫 64 비트의 값을 계산했다.

${\begin{aligned}\Omega _{U}&=0.0000001000000100000110\cdots _{(2)}\\&=0.00787499699\cdots _{(10)}\end{aligned}}$

(OEIS의 수열 A079365, A100264.)

정지 문제와의 관계

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

성질

각각의 차이틴 상수 Ω는 다음과 같은 성질을 지닌다.

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

정지 문제와 튜링 동치인 수라고 해서 다 정지 확률인 것은 아니다. 보다 강한 동치관계인 솔로바이 동치(Solovay equivalence) 개념을 사용하면 왼쪽 열거 가능 수들 중에서 정지 확률을 골라낼 수 있다. 0과 1 사이의 실수가 (어떤 접두어 없는 보편 계산 가능 함수의) 정지 확률이라는 것은 왼쪽 열거 가능하고 알고리즘적으로 무작위적이라는 것과 동치이다. Ω는 알고리즘적으로 무작위적인 수 중에 얼마 안 되는 정의 가능한 수이고 또 가장 유명한 수이지만, 알고리즘적으로 무작위적인 수의 전형적인 사례는 아니라고 할 수 있다.

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

같이 보기

• 정지 문제
• 괴델의 불완전성 정리
• 무작위성
• 확률론
• 수학 상수

참고 문헌

• Cristian S. Calude (2002). Information and Randomness: An Algorithmic Perspective, second edition. Springer. ISBN 3-540-43466-6
• Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu. Computing a Glimpse of Randomness.
• R. Downey, and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity, Springer-Verlag.
• Ming Li and Paul Vitányi (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. Introduction chapter full-text Archived 2008년 5월 17일 - 웨이백 머신.
• Jürgen Schmidhuber (2000). Algorithmic Theories of Everything (arXiv: quant-ph/ 0011122). Journal reference: J. Schmidhuber (2002). Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612.