차이틴 상수

이 문서에는 일반 참조 목록이 포함되어 있지만 해당 인라인 인용이 충분하지 않습니다. 좀 더 정확한 인용을 소개하여 이 기사를 개선하는 데 도움을 주시기 바랍니다. (2011년 11월) (이 템플릿 메시지를 제거하는 방법과 시기에 대해 알아보기)

알고리즘 정보 이론의 컴퓨터 과학 하위 분야에서 차이틴 상수(차이틴 오메가 수)^[1] 또는 정지 확률은 비공식적으로 무작위로 구성된 프로그램이 정지할 확률을 나타내는 실수입니다. 이 숫자들은 Gregory Chaitin으로 인해 구성된 것입니다.

프로그램을 인코딩하는 각 방법마다 하나씩, 중단 확률이 무한히 많지만, 마치 하나만 있는 것처럼 ω를 쓰는 것이 일반적입니다. ω는 사용되는 프로그램 인코딩에 의존하기 때문에 특정 인코딩을 언급하지 않을 때 Chaitin의 구성이라고 불리기도 합니다.

각각의 정지 확률은 계산이 불가능한 정상적이고 초월적인 실수이며, 이것은 그 숫자를 계산하는 알고리즘이 없다는 것을 의미합니다. 각각의 정지 확률은 마틴-뢰프 무작위인데, 이는 그 숫자를 확실하게 추측할 수 있는 알고리즘조차 없다는 것을 의미합니다.

배경

정지 확률의 정의는 접두사가 없는 범용 계산 가능 함수의 존재에 의존합니다. 이러한 함수는 직관적으로 유효한 다른 프로그램의 적절한 확장으로 유효한 프로그램을 얻을 수 없는 속성을 가진 프로그래밍 언어를 나타냅니다.

F가 유한 이진 문자열인 하나의 인수를 사용하는 부분 함수이며 출력으로 단일 이진 문자열을 반환할 수 있다고 가정합니다. 함수 F는 임의의 유한 이진 문자열 x와 y에 대하여 입력 x가 주어졌을 때 튜링 기계가 테이프에 y를 두고 중단하는 경우에만 F(x) = y를 계산하는 튜링 기계가 있다면 계산 가능하다고 합니다.

함수 F는 다음과 같은 성질이 성립하면 보편적이라고 합니다. 단일 변수의 모든 계산 가능한 함수 f에 대하여 모든 x에 대하여 F(w x) = f(x)인 문자열 w가 존재하며, 여기서 x는 두 문자열 w와 x의 연결을 나타냅니다. 이는 F가 한 변수의 계산 가능한 함수를 시뮬레이션하는 데 사용될 수 있음을 의미합니다. 비공식적으로 w는 계산 가능 함수 f에 대한 "스크립트"를 나타내고, F는 스크립트를 입력의 접두사로 파싱한 다음 나머지 입력에 대해 실행하는 "해석기"를 나타냅니다.

F의 도메인은 정의되는 모든 입력 p의 집합입니다. 보편적인 F의 경우, 그러한 p는 일반적으로 프로그램 부분과 데이터 부분의 연결로 볼 수 있고, 함수 F에 대한 단일 프로그램으로 볼 수 있습니다.

함수 F는 p'가 p의 적절한 확장인 두 원소 p, p'가 없는 경우 프리픽스 프리라고 합니다. 이것은 다음과 같이 다시 표현될 수 있습니다. F의 도메인은 유한 이진 문자열 집합의 접두사가 없는 코드(즉시 코드)입니다. 접두사가 없는 상태를 적용하는 간단한 방법은 입력 수단이 비트를 한 번에 하나씩 읽을 수 있는 이진 스트림인 기계를 사용하는 것입니다. 엔드-오브-스트림 마커는 없습니다. 입력의 끝은 범용 기계가 더 많은 비트를 읽기 중지하기로 결정했을 때 결정되며 나머지 비트는 허용된 문자열의 일부로 간주되지 않습니다. 여기서 마지막 단락에서 언급한 두 개념의 프로그램 차이가 명확해집니다. 하나는 문법에 따라 쉽게 인식되고 다른 하나는 인식하기 위해 임의의 계산이 필요합니다.

모든 보편적인 계산 가능 함수의 도메인은 계산 가능한 집합이지만 계산 가능한 집합은 결코 아닙니다. 도메인은 항상 정지 문제와 동등한 튜링입니다.

정의.

P를_F 접두사가 없는 보편적 계산 가능 함수 F의 정의역이라 하자. 상수 ω는 다음과 같이 정의됩니다.

$F$=${\displaystyle {\mathrm{}}_{}}$∑ p ∈ $PF$2 - p {\$displaystyle$ \Omega${\displaystyle {\mathrm{}}_{}}$_{F$}=\$sum _{p\in P_{F}}2^{- p}},

여기서 ${\displaystyle p}$ ${\$는 문자열 p의 길이를 나타냅니다$$. 이것은 F의 정의역에 있는 모든 p에 대하여 하나의 합을 갖는 무한합입니다. Kraft의 부등식과 함께 도메인이 접두사가 없어야 한다는 요구 사항은 이 합계가 0과 1 사이의 실수로 수렴되도록 보장합니다. F가 컨텍스트에서 명확하면 ω는 단순히 ω로 표시될 수 있지만 접두사가 없는 범용 계산 가능 함수가 다른 값의 ω로 이어집니다.

정지 문제와의 관계

ω의 첫 N비트를 알면 크기가 N인 모든 프로그램의 정지 문제를 계산할 수 있습니다. 정지 문제를 풀 프로그램 p의 길이를 N비트로 두자. 도브테일링 방식에서는 모든 길이의 모든 프로그램이 실행되며, 이 첫 번째 N비트와 일치할 만큼 충분한 확률을 공동으로 기여할 수 있을 때까지 실행됩니다. 프로그램 p가 아직 중지되지 않았다면 중지 확률에 대한 기여가 첫 번째 N 비트에 영향을 미치기 때문에 절대 중지되지 않습니다. 따라서 정지 문제는 p에 대해 해결됩니다.

골드바흐의 추측과 같은 수론의 많은 미해결 문제들은 특수한 프로그램(기본적으로 반례를 찾고 발견되면 중단되는)의 정지 문제를 해결하는 것과 같기 때문에, 카이틴 상수의 충분한 부분을 알고 있다는 것은 또한 이러한 문제에 대한 답을 알고 있다는 것을 의미합니다. 그러나 정지 문제는 일반적으로 해결할 수 없으며, 따라서 차이틴 상수의 처음 몇 비트를 제외하고는 계산할 수 없기 때문에,^[2] 이것은 정지 문제에 대한 오라클 머신을 구축하려는 것과 마찬가지로 어려운 문제를 불가능한 문제로 줄입니다.

확률로서의 해석

칸토어 공간은 0과 1의 모든 무한한 수열들의 집합입니다. 정지 확률은 칸토어 공간에 대한 일반적인 확률 측도하에서 칸토어 공간의 특정 부분 집합의 측도로 해석할 수 있습니다. 중단 확률이 이름을 딴 것은 이러한 해석에서 비롯됩니다.

공정한 동전 측도라고도 불리는 칸토어 공간의 확률 측도는 임의의 이진 문자열 x에 대하여 x로 시작하는 일련의 집합이 측도^{− x} 2를 갖도록 정의됩니다. 이것은 각각의 자연수 n에 대하여, f(n) = 1이 1/2의 측도를 갖도록 칸토어 공간에 있는 시퀀스들의 집합 f가 1/2의 측도를 가지며, n번째 원소가 0인 시퀀스들의 집합도 1/2의 측도를 가짐을 의미합니다.

F를 접두사가 없는 보편적 계산 가능 함수라고 하자. F의 정의역 P는 무한히 많은 이진 문자열로 구성됩니다.

${\displaystyle P}$ =${\displaystyle }${${\displaystyle {}_{}}$1, p 2, …} {\displaysty${\displaystyle l}$e P=\{p_{1}, p_{2},\ldots \}.

각 문자열 p는_i 칸토어 공간의 부분 집합 S를_i 결정합니다. 집합 S는_i p로_i 시작하는 칸토어 공간의 모든 시퀀스를 포함합니다. P는 접두사가 없는 집합이므로 이들 집합은 서로소입니다. 합계.

${\displaystyle \sum _{p\in P}2^{- p}}$

집합의 측도를 나타냅니다.

$∈$ {\displaystyle \$bigcup$ _{i\in \mathbb {N} }S_{i} 스타일입니다$.$

이와 같이 ω은 임의로 선택된 0과 1의 무한 시퀀스가 F의 도메인에 있는 (일부 유한한 길이의) 비트열로 시작될 확률을 나타냅니다. ω를 정지 확률이라고 부르는 것도 이런 이유에서입니다.

특성.

각 Chaitin 상수 ω에는 다음과 같은 속성이 있습니다.

• 알고리즘적으로 랜덤(Martin-Löf 랜덤 또는 1-랜덤이라고도 함)입니다.^[3] 즉, ω의 첫 n비트를 출력하는 가장 짧은 프로그램의 크기는 n - O(1) 이상이어야 합니다. 골드바흐의 예와 같이, 이 n개의 비트들은 최대 n개의 길이를 가진 모든 프로그램들 중에서 정확히 어떤 프로그램이 중단되는지를 알아낼 수 있기 때문입니다.
• 결과적으로, 그것은 정상적인 숫자이고, 그것의 숫자는 공정한 동전을 던져서 생성된 것처럼 등분되어 있다는 것을 의미합니다.
• 계산 가능한 숫자가 아닙니다. 아래에서 설명하는 것처럼 이진 확장을 열거하는 계산 가능한 함수가 없습니다.
• q < ω가 계산 가능하도록 유리수 q의 집합; 그러한 성질을 갖는 실수는 재귀 이론에서 좌-c.e 실수라고 불립니다.
• q > ω가 되도록 유리수 q의 집합은 계산 가능하지 않습니다. (이유: 이 속성을 가진 모든 좌-c.e 실수는 계산 가능하지만 ω는 그렇지 않습니다.)
• ω는 산술적 숫자입니다.
• 이것은 정지 문제와 동등한 튜링이며 따라서 산술 계층의 레벨$$δ 20 {\displaystyle $\Delta _{$2}^{0}}입니다.

튜링이 정지 문제와 동등한 모든 집합이 정지 확률인 것은 아닙니다. 더 미세한 등가 관계인 Solovay 등가 관계를 사용하여 왼쪽-c.e. 실제 사이의 정지 확률을 특성화할 수 있습니다.^[5] [0,1]의 실수가 왼쪽 ce.e.이고 알고리즘적으로 무작위인 경우에만 차이틴 상수(즉, 접두사가 없는 범용 계산 함수의 정지 확률)임을 보여줄 수 있습니다.^[5] ω는 알고리즘적으로 가장 잘 알려진 난수로 정의 가능한 몇 안 되는 난수 중 하나이지만, 모든 알고리즘적 난수의 전형적인 형태는 전혀 아닙니다.

계산 불능

n이 주어지면 숫자의 첫 번째 n자리를 반환하는 알고리즘이 있으면 실수를 계산 가능하다고 합니다. 이것은 실수의 숫자를 열거하는 프로그램의 존재에 해당합니다.

정지 확률은 계산 가능하지 않습니다. 이 사실의 증명은 ω의 첫 n자리가 주어지면 길이가 n인 프로그램에 대한 튜링의 정지 문제를 해결하는 알고리즘에 의존합니다. 정지 문제는 결정할 수 없기 때문에 ω를 계산할 수 없습니다.

알고리즘은 다음과 같이 진행됩니다. ω ω의 처음 n자리와 k ≤ n이 주어지면, 알고리즘은 정의역의 원소가 충분히 발견될 때까지 F의 정의역을 계산하여 그것들이 나타내는 확률이 ω의 2 이내가 되도록 합니다. 이 시점 이후에는 길이가 k인 어떤 추가 프로그램도 정의역에 있을 수 없는데, 그 이유는 이들 각각이 측정값에 2를 더하면 불가능하기 때문입니다. 따라서 도메인에서 길이가 k인 문자열의 집합은 정확히 이미 열거된 문자열의 집합입니다.

알고리즘 무작위성

실수를 나타내는 이진수열이 알고리즘적으로 임의적인 수열이라면 실수는 임의적인 것입니다. Calude, Hertling, Khoussainov 및 Wang은 재귀적으로 열거할 수 있는 실수가 Chaitin의 ω 수일 경우에만 알고리즘적으로 랜덤한 수열임을 보여주었습니다.

확률 정지에 대한 불완전성 정리

Peano 산술과 같이 자연수에 대해 효과적으로 표현되는 각각의 특정 일관된 공리계에 대해 N번째 이후의 ω의 어떤 비트도 그 시스템 내에서 1 또는 0임을 증명할 수 없는 상수 N이 존재합니다. 상수 N은 형식적 시스템이 효과적으로 표현되는 방법에 따라 다르므로 공리적 시스템의 복잡성을 직접적으로 반영하지 않습니다. 이 불완전성 결과는 산술에 대한 일관된 형식 이론이 완성될 수 없음을 보여준다는 점에서 괴델의 불완전성 정리와 유사합니다.

슈퍼 오메가

위에서 언급한 바와 같이, Gregory Chaitin의 상수 ω의 처음 n비트는 n-O(1)비트보다 적은 정지 알고리즘으로 계산할 수 없다는 점에서 무작위이거나 압축할 수 없습니다. 그러나 가능한 모든 프로그램을 체계적으로 나열하고 실행하는 짧지만 결코 중단되지 않는 알고리즘을 고려해 보십시오. 프로그램 중 하나가 중단될 때마다 확률이 출력에 추가됩니다(0으로 초기화됨). 유한 시간이 지나면 출력의 첫 n비트는 더 이상 변하지 않습니다(이 시간 자체가 정지 프로그램에 의해 계산되지 않는다는 것은 중요하지 않습니다). 따라서 출력이 (유한 시간 후에) ω의 첫 n비트로 수렴하는 짧은 비-홀팅 알고리즘이 있습니다. 다시 말해서, ω의 열거 가능한 처음 n개의 비트는 매우 짧은 알고리즘에 의해 제한 계산이 가능하다는 점에서 매우 압축성이 높습니다. 열거형 알고리즘 집합에 대해 무작위적이지 않습니다. 위르겐 슈미드후버(2000)는 어떤 의미에서는 원래의 한계 계산 ω ω보다 훨씬 더 무작위적인 한계 계산 "슈퍼 ω"를 구축했습니다. 왜냐하면 어떤 의미에서 어떤 사람이 슈퍼 ω를 열거하지 않는 알고리즘에 의해 크게 압축할 수 없기 때문입니다.

대안적인 "슈퍼 ω"의 경우, 접두사가 없는 범용 튜링 머신(UTM)의 보편적 확률 – 즉, (이진 문자열로서) 임의의 이진 문자열로 모든 입력이 접두사가 붙은 경우에도 보편적으로 유지될 확률은 오라클이 있는 기계의 정지 문제의 세 번째 반복(즉, $튜링{\displaystyle {}^{}}$ 점프 표기법을 사용한 O (${\displaystyle {3)}^{}}$ ${\$으로 볼 수 있습니다.^[8]

참고 항목

• 괴델의 불완전성 정리
• 콜모고로프 복잡도

참고문헌

인용된 작품

• Calude, Cristian S. (2002). Information and Randomness: An Algorithmic Perspective (second ed.). Springer. ISBN 3-540-43466-6.
• Downey, R.; Hirschfeldt, D. (2010). Algorithmic Randomness and Complexity. Springer-Verlag.
• Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. 소개장 전문.
• Schmidhuber, Jürgen (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. doi:10.1142/S0129054102001291. 사전 인쇄: 모든 것에 대한 알고리즘 이론 (arXiv: quant-ph/ 0011122)

외부 링크

• Chaitin의 오메가 연구의 최근 발전에 대해 논의한 Chaitin의 오메가 서베이 기사의 측면.
• 오메가와 왜 수학은 TOE가 없는가는 2004년 8월, 알란 튜링 사망 50주년을 맞아 Mathematics Today지에 실린 Gregory Chaitin이 쓴 기사를 바탕으로 합니다.
• 이성의 한계 그레고리 차이틴(Gregory Chaitin)은 원래 2006년 3월 사이언티픽 아메리칸(Scientific American)에 등장했습니다.
• 제한 계산 가능한 슈퍼 오메가가 오메가보다 더 무작위적이고 알고리즘 정보의 일반화(Jürgen Schmidhuber)