알고리즘 난수열

알고리즘 무작위 수열(Algorithmic random sequence)이란 어떤 알고리즘에 대해서 각 알파벳이 무작위하게 등장한다고 간주되는 무한수열이다. 무작위 수열을 정의하는데 쓰이는 알고리즘의 종류는 매우 다양하기 때문에 무작위성에도 서로 다른 정의가 있다. 마틴-뢰프 무작위성(Martin-Löf randomnes)은 그 중 가장 흔하게 사용되는 정의이다. 무작위 수열은 알고리즘 정보이론의 주요한 연구주제중 하나이다.

정의

마틴 뢰프의 무작위 수열에 대한 본래 정의는 구성적인 영덮개를 이용하였다. 즉 어떤 수열이 어떤 덮개에도 포함되지 않는다면 그 수열을 무작위하다 정의하였다. 한편 레오니드 레빈(Leonid Levin)과 클라우스-피터 슈노르(Claus-Peter Schnorr)는 콜모고로프 복잡도를 사용한 정의가 마틴 뢰프의 정의와 동치임을 증명하였다.

• 콜모고로프 복잡도 (Schnorr 1973, Levin 1973): 콜모고로프 복잡도는 어떤 유한수열 내지는 문자열의 압축성에 대한 하한이라고 생각할 수 있다. 보다 직관적으로 어떤 문자열 w에 대한 콜모고로프 복잡도 K(w)는 w를 출력하는 가장 짧은 컴퓨터 프로그램의 길이이다. 어떤 자연수 c에 대하여 문자열 w 가 c-비압축적이라는 것은 $K(w)\geq |w|-c$ 라는 것이다. 무한 수열 S 의 모든 유한한 접두사에 대해서 고정된 c가 존재하여 그것이 c-비압축적인 것과 S 가 마틴-뢰프 무작위성을 가지는 것은 동치이다.