알고리즘 정보 이론
Algorithmic information theory알고리즘 정보 이론(Algorithmic Information Theory, AIT)은 문자열이나 기타 데이터 구조와 같이 확률적으로 생성된 객체의 계산과 정보 사이의 관계에 관한 이론 컴퓨터 과학의 한 분야입니다.다시 말해, 알고리즘 정보 이론 내에서 계산적 비압축성은 정보 [1]이론에서 발견되는 관계 또는 불평등을 "모방"하는 것으로 나타난다.그레고리 차이틴에 따르면, 그것은 "샤논의 정보 이론과 튜링의 계산 가능성 이론을 칵테일 셰이커에 넣고 [2]격렬하게 흔들린 결과"라고 한다.
계산할 수 있게 생성된 개체의 약분할 수 없는 정보 내용에 대한 보편적인 조치의 형식화 외에도, AIT의 일부 주요 성과 보여 드리기 위해:(그self-delimited 경우) 같은 불평등은 엔트로피, 클래식 정보 이론처럼;[1]randomne는다(한 constant[3]을 제외하고)사실 알고리즘 복잡성을 따라갔다.ss은비압축성:[4] 랜덤으로 생성된 소프트웨어 영역 내에서 데이터 구조가 발생할 확률은 유니버설 [5]머신 상에서 실행될 때 데이터 구조를 생성하는 최단 프로그램의 순서입니다.
AIT는 주로 문자열(또는 기타 데이터 구조)의 축소 불가능한 정보 내용의 측정을 연구한다.대부분의 수학적 개체는 문자열이나 문자열 수열의 한계로 설명될 수 있기 때문에 정수를 포함한 다양한 수학적 개체를 연구하는 데 사용될 수 있습니다.AIT의 배후에 있는 주된 동기 중 하나는 메타수학 분야와 같이 수학적 객체가 가지고 있는 정보에 대한 바로 그 연구이다. 예를 들어, 아래에 언급된 불완전성 결과에서 알 수 있다.다른 주요 동기는 단일 및 고정 객체에 대한 고전 정보 이론의 한계를 뛰어넘는 것, 무작위성의 개념을 공식화함, 확률 분포에 대한 사전 지식 없이 의미 있는 확률론적 추론을 찾는 것(예: 독립적이고 동일한 분포, 마르코프 또는 심지어 s)에서 비롯되었다.정지).이러한 방식으로, AIT는 기본적으로 알고리즘 복잡도, 알고리즘 랜덤성 및 알고리즘 [6][4]확률이라는 세 가지 주요 수학적 개념과 그 사이의 관계에 기초하는 것으로 알려져 있습니다.
개요
알고리즘 정보 이론은 주로 문자열(또는 기타 데이터 구조)에 대한 복잡도 측정을 연구합니다.대부분의 수학적 개체는 문자열이나 문자열 수열의 한계로 설명될 수 있기 때문에 정수를 포함한 다양한 수학적 개체를 연구하는 데 사용될 수 있습니다.
비공식적으로 알고리즘 정보론의 관점에서 보면, 문자열의 정보 내용은 그 문자열의 가장 압축 가능한 자기포함 표현의 길이와 동등하다.자기포함형 표현은 기본적으로 고정적이지만 무관한 범용 프로그래밍 언어로 실행 시 원본 문자열을 출력하는 프로그램입니다.
이런 관점에서 보면, 3000페이지짜리 백과사전이 훨씬 더 유용하다는 사실에도 불구하고, 실제로는 완전히 무작위적인 3000페이지 분량의 문자보다 적은 정보를 포함하고 있다.왜냐하면 랜덤한 글자의 전체 순서를 재구성하려면 글자 하나하나가 무엇인지 알아야 하기 때문이다.반면 백과사전에서 모든 모음을 제거하면 영어에 대한 합리적인 지식을 가진 사람이 백과사전을 재구성할 수 있는데, 이는 존재하는 문맥과 자음에서 "Ths sntnc hs lw nfrmtnt"이라는 문장을 재구성할 수 있는 것과 같다.
고전적인 정보 이론과 달리, 알고리즘 정보 이론은 비결정론이나 가능성에 대한 물리적 또는 철학적 직관에 의존하지 않는 무작위 문자열과 무작위 무한 시퀀스의 형식적이고 엄격한 정의를 제공합니다.(임의 문자열 집합은 콜모고로프 복잡도를 정의하기 위해 사용되는 범용 튜링 기계의 선택에 따라 다르지만, 어떤 선택도 동일한 점근적 결과를 준다. 왜냐하면 문자열의 콜모고로프 복잡도는 오직 범용 튜링 기계의 선택에 따라 가법 상수까지 불변하기 때문이다.따라서 랜덤 무한 시퀀스 세트는 유니버설머신의 선택과는 무관합니다.)
차이틴의 불완전성 정리와 같은 알고리즘 정보 이론의 결과들 중 일부는 일반적인 수학적, 철학적 직관에 도전하는 것으로 보인다.이 중에서 가장 주목할 만한 것은 Chaitin의 상수 δ의 구성이다. 이것은 자기 기만적인 범용 튜링 기계가 공정한 동전의 플립에 의해 입력이 공급될 때 멈출 확률을 표현하는 실수이다(때로는 랜덤 컴퓨터 프로그램이 결국 멈출 확률로 생각되기도 한다.δ는 쉽게 정의되지만, 일관된 공리화 가능 이론에서는 δ의 최종적인 자릿수만을 계산할 수 있기 때문에, 어떤 의미에서는 알 수 없으며, 괴델의 불완전성 이론과 유사한 지식에 절대적인 한계를 제공한다.δ의 자릿수는 판별할 수 없지만, δ의 속성은 많이 알려져 있습니다.예를 들어 알고리즘적으로 랜덤한 시퀀스이기 때문에 이진수가 균등하게 분포되어 있습니다(실제로 정규).
역사
알고리즘 정보 이론은 통계학에서 베이즈의 규칙 적용과 관련된 심각한 문제를 극복하는 방법인 알고리즘 확률의 발명의 일부로서 기초가 되는 기본적인 아이디어를 발표한 레이 솔로몬오프에 의해 [7]설립되었습니다.그는 1960년 [8]Caltech에서 열린 Conference에서 그의 결과를 처음 기술했고, 1960년 2월 보고서 "A Premary Report on a General Theory of Gueltive Indistion"에서 "귀납적 [9]추론의 일반 이론에 대한 예비 보고서"를 발표했습니다.알고리즘 정보 이론은 1965년 안드레이 콜모고로프와 1966년 경 그레고리 차이틴에 의해 독립적으로 개발되었다.
콜모고로프 복잡도 또는 알고리즘 정보에는 여러 가지 변형이 있다. 가장 널리 사용되는 것은 자기 기만 프로그램에 기초하고 있으며 주로 레오니드 레빈(1974년)에 기인한다.Per Martin-Löf는 또한 무한 수열의 정보 이론에 크게 기여했다.Blum 공리(Blum 1967)에 기초한 알고리즘 정보 이론에 대한 자명한 접근법은 마크 버긴이 안드레이 콜모고로프(Burgin 1982)에 의해 출판을 위해 제시한 논문에서 소개되었다.자명한 접근방식은 알고리즘 정보 이론의 다른 접근방식을 포함한다.알고리즘 정보의 다양한 척도를 알고리즘 정보의 공리적으로 정의된 척도의 특정 사례로 취급할 수 있다.각 특정 척도에 대해 기본 불변성 정리와 같은 유사한 정리를 증명하는 대신, 공리적인 설정에서 증명된 하나의 대응하는 정리로부터 그러한 모든 결과를 쉽게 추론할 수 있다.이것은 수학에서 자명한 접근법의 일반적인 장점이다.알고리즘 정보 이론에 대한 자명한 접근법은 책(Burgin 2005)에서 더욱 개발되었고 소프트웨어 메트릭스에 적용되었다(Burgin and Debnath, 2003; Debnath and Burgin, 2003).
정확한 정의
문자열의 Kolmogorov 복잡도가 문자열의 길이 이상일 경우 이진 문자열은 랜덤이라고 합니다.단순한 카운트 인수는 임의의 길이의 문자열이 랜덤이며 거의 모든 문자열이 랜덤에 가깝다는 것을 나타냅니다.콜모고로프 복잡도는 범용 튜링 기계의 고정된 선택(비공식적으로 "설명"이 주어지는 고정된 "기술 언어")에 의존하기 때문에 랜덤 문자열의 수집은 고정된 범용 기계의 선택에 의존한다.그럼에도 불구하고 랜덤 문자열 집합은 전체적으로 고정 머신에 관계없이 유사한 속성을 가지기 때문에 먼저 범용 머신을 지정하지 않고도 랜덤 문자열의 특성에 대해 그룹별로 이야기할 수 있습니다(그리고 종종 그러합니다).
무한이진수열은 어떤 상수 c에 대해 모든 n에 대해 해당 배열의 길이 n의 초기 세그먼트의 콜모고로프 복잡도가 n - c 이상일 경우 랜덤이라고 한다.거의 모든 시퀀스(무한 이진 시퀀스의 공간에서 표준 측정치("공정 동전" 또는 르베그 측정치)의 관점에서)가 랜덤임을 알 수 있다.또한 두 개의 다른 범용 기계에 대한 콜모고로프 복잡도가 최대 상수만큼 다르다는 것을 보여줄 수 있기 때문에 랜덤 무한 시퀀스의 수집은 (유한 문자열과 대조적으로) 범용 기계의 선택에 의존하지 않는다.무작위성에 대한 이러한 정의는 보통 무작위성에 대한 다른 유사한 개념과 구별하기 위해 Per Martin-Löf의 이름을 따서 Martin-Löf 무작위성으로 불린다.무작위성에 대한 다른 강한 개념(2-랜덤성, 3-랜덤성 등)과 구별하기 위해 1-랜덤성이라고도 합니다.Martin-Löf 랜덤성 개념 외에도 재귀 랜덤성, Schnorr 랜덤성, Kurtz 랜덤성 등이 있습니다.왕융게는[10] 이 모든 무작위성 개념이 다르다는 것을 보여주었다.
, { \ { , \ }} 이외의 알파벳에 대해 관련 정의를 작성할 수 있습니다).
특정 시퀀스
알고리즘 정보 이론(Algorithmic Information Theory, AIT)은 컴퓨터 과학을 이용한 개별 객체의 정보 이론으로 계산, 정보 및 무작위성 간의 관계에 관한 것입니다.
객체의 정보 내용 또는 복잡성은 가장 짧은 설명의 길이로 측정할 수 있습니다.예를 들어 스트링
"0101010101010101010101010101010101010101010101010101010101010101"
에는 「01」의 32회 반복」이라고 하는 짧은 설명이 붙어 있습니다만,
"1100100001100001110111101110110011111010010000100101011110010110"
스트링 자체를 적어 두는 것 외에 간단한 설명은 없는 것 같습니다.
보다 형식적으로 문자열 x의 알고리즘 복잡도(AC)는 x를 계산하거나 출력하는 최단 프로그램의 길이로 정의되며, 여기서 프로그램은 고정 참조 범용 컴퓨터에서 실행된다.
밀접하게 관련된 개념은 범용 컴퓨터가 무작위로 선택된 프로그램으로 공급될 때 일부 문자열 x를 출력할 확률이다.이 알고리즘의 "솔로모노프" 확률(AP)은 유도의 오래된 철학적 문제를 형식적인 방식으로 해결하는 데 핵심적입니다.
AC와 AP의 주요 단점은 계산 불능입니다.시간에 구애받지 않는 "Levin" 복잡성은 실행 시간의 대수를 길이에 추가하여 느린 프로그램에 불이익을 줍니다.이를 통해 AC 및 AP의 계산 가능한 변형이 발생하고 범용 "Levin" 검색(US)은 모든 반전 문제를 최적의 시간 내에 해결합니다(비현실적으로 큰 곱셈 상수 제외).
AC와 AP는 또한 개별 문자열의 무작위성에 대한 형식적이고 엄격한 정의를 비결정론 또는 가능성에 대한 물리적 또는 철학적 직관에 의존하지 않도록 합니다.대략적으로 알고리즘 복잡도가 길이와 동일하다는 의미에서 압축할 수 없는 경우 문자열은 알고리즘 "Martin-Löf" 랜덤(AR)입니다.
AC, AP 및 AR은 AIT의 핵심 하위 분야이지만, AIT는 다른 많은 영역에서 발생합니다.MDL(Minimum Description Length) 원리의 기초로서 기능하며 계산 복잡도 이론의 증명을 단순화할 수 있으며 객체 간의 보편적 유사성 메트릭을 정의하거나 맥스웰 데몬 문제를 해결하는 데 사용되었습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ a b 차이틴 1975
- ^ 알고리즘 정보 이론
- ^ 또는 상호 알고리즘 정보의 경우 입력 자체와 함께 입력의 알고리즘 복잡성을 알립니다.
- ^ a b 2013년 칼루드
- ^ Downey, Rodney G.; Hirschfeldt, Denis R. (2010). Algorithmic Randomness and Complexity. Springer. ISBN 978-0-387-68441-3.
- ^ Li & Vitanyi 2013
- ^ Vitanyi, P. "부고: Ray Solomonoff, 알고리즘 정보 이론의 창시자"
- ^ 캘리포니아 공과대학, 1960년 2월 8일-11일 "A Formal Theory of Induction, Part 1, 1964, p.1"에 인용된 "뇌 시스템과 컴퓨터"에 관한 컨퍼런스 논문
- ^ Solomonoff, R., "귀납적 추론의 일반 이론에 관한 예비 보고서", 보고서 V-131, 케임브리지, Zator Co., 1960년 2월 4일 개정 보고서.
- ^ Wang, Yongge (1996). Randomness and Complexity (PDF) (PhD). University of Heidelberg.
외부 링크
추가 정보
- Blum, M. (1967). "On the Size of Machines". Information and Control. 11 (3): 257–265. doi:10.1016/S0019-9958(67)90546-3.
- Blum, M. (1967). "A Machine-independent Theory of Complexity of Recursive Functions". Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. S2CID 15710280.
- Burgin, M. (1982). "Generalized Kolmogorov complexity and duality in theory of computations". Soviet Math. Dokl. 25 (3): 19–23.
- Burgin, M. (1990). "Generalized Kolmogorov Complexity and other Dual Complexity Measures". Cybernetics. 26 (4): 481–490. doi:10.1007/BF01068189. S2CID 121736453.
- Burgin, M. (2005). Super-recursive algorithms. Monographs in computer science. Springer. ISBN 9780387955698.
- Calude, C.S. (1996). "Algorithmic information theory: Open problems" (PDF). J. UCS. 2 (5): 439–441.
- Calude, C.S. (2013). Information and Randomness: An Algorithmic Perspective. Texts in Theoretical Computer Science. An EATCS Series (2nd ed.). Springer-Verlag. ISBN 9783662049785.
- Chaitin, G.J. (1966). "On the Length of Programs for Computing Finite Binary Sequences". Journal of the Association for Computing Machinery. 13 (4): 547–569. doi:10.1145/321356.321363. S2CID 207698337.
- Chaitin, G.J. (1969). "On the Simplicity and Speed of Programs for Computing Definite Sets of Natural Numbers". Journal of the Association for Computing Machinery. 16 (3): 407–412. doi:10.1145/321526.321530. S2CID 12584692.
- Chaitin, G.J. (1975). "A Theory of Program Size Formally Identical to Information Theory". Journal of the Association for Computing Machinery. 22 (3): 329–340. doi:10.1145/321892.321894. S2CID 14133389.
- Chaitin, G.J. (1977). "Algorithmic information theory". IBM Journal of Research and Development. 21 (4): 350–9. doi:10.1147/rd.214.0350.
- Chaitin, G.J. (1987). Algorithmic Information Theory. Cambridge University Press.
- Kolmogorov, A.N. (1965). "Three approaches to the definition of the quantity of information". Problems of Information Transmission (1): 3–11.
- Kolmogorov, A.N. (1968). "Logical basis for information theory and probability theory". IEEE Trans. Inf. Theory. IT-14 (5): 662–4. doi:10.1109/TIT.1968.1054210.
- Levin, L. A. (1974). "Laws of information (nongrowth) and aspects of the foundation of probability theory". Problems of Information Transmission. 10 (3): 206–210.
- Levin, L.A. (1976). "Various Measures of Complexity for Finite Objects (Axiomatic Description)". Soviet Math. Dokl. 17: 522–526.
- Li, M.; Vitanyi, P. (2013). An Introduction to Kolmogorov Complexity and its Applications (2nd ed.). Springer-Verlag. ISBN 9781475726060.
- Solomonoff, R.J. (1960). A Preliminary Report on a General Theory of Inductive Inference (PDF) (Technical report). Cambridge, Mass: Zator Company. ZTB-138.
- Solomonoff, R.J. (1964). "A Formal Theory of Inductive Inference". Information and Control. 7 (1): 1–22. doi:10.1016/S0019-9958(64)90223-2.
- Solomonoff, R.J. (1964). "A Formal Theory of Inductive Inference". Information and Control. 7 (2): 224–254. doi:10.1016/S0019-9958(64)90131-7.
- Solomonoff, R.J. (2009). Emmert-Streib, F.; Dehmer, M. (eds.). Algorithmic Probability: Theory and Applications, Information Theory and Statistical Learning. Springer. ISBN 978-0-387-84815-0.
- Van Lambagen (1989). "Algorithmic Information Theory" (PDF). Journal of Symbolic Logic. 54 (4): 1389–1400. doi:10.1017/S0022481200041153.
- Zurek, W.H. (2018) [1991]. "Algorithmic Information Content, Church-Turing Thesis, physical entropy, and Maxwell's demon, in". Complexity, Entropy and the Physics of Information. Addison-Wesley. pp. 73–89. ISBN 9780429982514.
- Zvonkin, A.K. and Levin, L. A. (1970). "The Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms". Russian Mathematical Surveys. 256 (6): 83–124. Bibcode:1970RuMaS..25...83Z. doi:10.1070/RM1970v025n06ABEH001269.
