알고리즘 난수열 문서 원본 보기

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

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

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

[[분류:정보 이론]]