알고리즘 정보 이론

알고리즘 정보 이론(Algorithmic information theory, AIT)은 문자열이나 기타 데이터 구조와 같이 계산 가능하게 생성된 개체(확률적으로 생성된 개체와 반대)의 정보와 계산 간의 관계에 관심을 갖는 이론 컴퓨터 과학의 한 분야이다. 즉, 계산 비압축성은 정보 이론에서 발견된 관계 또는 불평등을 "모방"(선택한 범용 프로그래밍 언어에만 의존하는 상수 제외)한다는 것이 알고리즘 정보 이론 내에서 표시된다. 그레고리 차이틴에 따르면 "섀넌의 정보 이론과 튜링의 계산 가능성 이론을 칵테일 셰이커에 넣고 세게 흔든 결과"라고 한다.

계산 가능하게 생성된 객체의 환원 불가능한 정보 내용에 대한 보편적 척도의 형식화 외에도 AIT의 몇 가지 주요 성과는 실제로 알고리즘의 복잡성이 (자기 구분의 경우) 엔트로피와 동일한 불평등(상수 제외)을 따르는 것이다. 고전적인 정보 이론에서와 마찬가지로 그렇다. 무작위성은 비압축성이다. 무작위로 생성된 소프트웨어 영역 내에서 모든 데이터 구조의 발생 확률은 범용 기계에서 실행될 때 생성되는 가장 짧은 프로그램의 순서이다.

AIT는 주로 문자열(또는 기타 자료 구조)의 환원 불가능한 정보 내용 측정을 연구한다. 대부분의 수학적 개체는 문자열 또는 문자열 시퀀스의 극한으로 설명될 수 있으므로 정수를 포함한 다양한 수학적 개체를 연구하는 데 사용할 수 있다. AIT의 주요 동기 중 하나는 아래에 언급된 불완전성 결과에서 볼 수 있듯이 메타수학 분야에서와 같이 수학적 개체가 전달하는 정보에 대한 연구이다. 다른 주요 동기는 단일 및 고정 객체에 대한 고전 정보 이론의 한계를 뛰어넘고, 무작위성의 개념을 공식화하고, 확률 분포에 대한 사전 지식 없이 의미 있는 확률론적 추론을 찾는 것이다(예: 독립적이고 동일하게 분포되는지, 마르코프, 또는 고정되어 있는 경우도 있다). 이러한 방식으로 AIT는 기본적으로 알고리즘 복잡성, 알고리즘 무작위성 및 알고리즘 확률이라는 세 가지 주요 수학적 개념과 이들 간의 관계를 기반으로 하는 것으로 알려져 있다.

같이 보기