[생활 속의 과학] 복잡도와 규칙
우주에서 날아오는 잡다한 신호
압축시키면 의미 여부 알수 있어

미국 UFO박물관에 전시된 외계인 모델.
전화번호 중 하나는 '1111-1111'이고 다른 하나는 '7342-3590' 이라고 하자. 어떤 것이 더 암기하기 쉬운 것인가를 물어본다면 당연히 앞의 것이라 할 것이다.

어떤 사물의 복잡한 정도를 계산하고자 한다면 러시아 수학자 콜모고로프(Kolmogorov)게 제시한 복잡도를 활용하면 좋다. 콜모고로프 복잡도란 그 수열을 생성하는 최소 프로그램의 크기로 정의된다.

프로그램을 할 수 없는 분을 위해서 설명한다면 그냥 그 수열을 최소한의 한글로 표현할 때의 글자 수 정도로 생각하면 된다. 예를 들어 '1212121212...'인 수열을 짧은 한글로 표현하면 '1과 2가 계속 반복', 즉 11자(공백까지 포함하여)로 표현이 된다.

그러나 규칙을 찾기 어려운 수열 '248569070815...'를 표현해보려면 별 뾰족한 수가 안 보인다. 굳이 표현을 한다면 '처음에는 2, 그 다음 4, 그리고 이어서 8,5,6,9,0... 이 순서대로 나옴' 이렇게 하다보면 수열의 길이보다 한글 표현의 길이가 더 길어질 수 있다.

콜모고로프 복잡도로 계산하면 그 수열의 내부에 포함된 규칙이 강하면 강할수록 생성 프로그램은 짧아진다. 우주에서 날아오는 잡다한 신호가 외계인이 보낸 것인지, 아니면 그냥 우주공간의 잡음인지는 그 신호파일을 우리가 흔히 쓰는 압축 프로그램으로 줄여보면 대략 알 수 있다.

아무런 규칙이 없는 잡음의 연속이라면 이런 데이터는 압축이 거의 되지 않는다. 그에 반해서 어떤 숨은 규칙이 있는 데이터라면 적절한 크기로 압축이 된다.

한글과 영어, 독일어 문서도 압축을 해보면 그 압축정도가 각각 미묘하게 다름을 알 수 있다. 따라서 문서의 콜모고로프 복잡도만으로 언어를 구분할 수도 있다. 의미가 담긴 드라마나 영화는 압축 요약이 되지만 취객의 무의미한 횡설수설은 요약이 불가능한 것은 콜모고로프 이론이 잘 설명해준다.

복잡한 사람 살이에도 규칙이 있다. 케빈 베이컨의 6단계 법칙에 따르면 지구촌의 모든 사람은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다고 한다. 문제:'101001000100001000001....'을 최소 글자로 한번 표현해보자. 조환규·부산대 정보컴퓨터공학부 교수
/ 입력시간: 2007. 08.08. 09:53