[틈새 과학] 유한 상태 기계-자유의지에 대한 가장 기계적인 질문

“신호를 기다렸다. 이제 간다.”라는 메시지를 해상에서 모스 부호로 보내는 상황을 생각해 보자. 국제 협약상 1999년 이후로는 거의 모든 원양 선박에서의 통신 수단이 인공위성을 활용하는 문자 데이터 전송 방식으로 대체되었지만, 천재지변에 민감한 상황에서 육지에서 우리가 이용하는 인터넷 수준의 대역폭을 기대할 수는 없다. 주고받는 메시지도 간결해야 하는데, 이때 구두점에 신경을 쓰지 않으면 위의 메시지는 상황에 따라 “신호를 기다리다가 받지 못하고 떠난다”라는 전혀 다른 의미로 해석되어 혼란이나 재난을 초래할 수 있을 것이다. 이러한 인위적인 상황을 소개하는 것은 형식 언어(形式言語)로 소통이 이루어지는 가장 기본적인 단위 과정을 살펴보기 위해서다.

구두점은 인간의 언어에서도 중요하지만 컴퓨터 언어를 비롯한 디지털 데이터를 취급하는 상황에서는 필수불가결하다. CPU가 아무리 빨라진들 긴 문자열 형태로 전송된 메시지 중 명령어가 어디서 끝나고 데이터가 어디서 시작되는지는 한 글자 또는 바이트(byte) 단위로 읽어 들이며 인식되어야 하기 때문이다. 결국 전체 메시지가 얼마의 길이를 가지며 그 안에 포함되는 지시사항은 어떤 것인지 정확하게 전달하기 위해서는 메시지를 보내는 이와 받는 이가 엄격한 규칙을 정하고 이에 맞추어 메시지를 작성하고 분해해야 한다. 인간의 언어와는 달리, 예외 규칙이나 문학적 기교가 없다시피 한 언어체계를 구축하고 이를 인식하거나 기록하는 일을 자동화하는 것이 컴퓨터 프로그래밍의 기본 작업이 된다.

이를 위해서는 전송되는 메시지뿐 아니라 메시지를 읽어 들이는 장치가 어떠한 상태에 있는지에 대한 정보도 기억장치에 기록되고 조회되어야 한다. 예를 들면, 메시지의 중간에 열리는 괄호 “(”가 들어갈 경우 메시지가 끝나기 전에 “)”로 닫아야 하는데 그렇지 않으면 메시지 자체가 온전하지 않거나 손상되었음을(깨졌음을) 나타낸다. 이를 인식하기 위해서는 열리는 괄호가 읽어졌을 때 “괄호 안으로 들어옴”이라는 상태를 기억장치에 표시해야 하고, 닫히는 괄호가 읽어졌을 때 상태 표시가 해제되어야 한다. “괄호 안으로 들어옴”, “메시지의 끝에 도달함” 등 가능한 상태 표시가 유한할 경우 이러한 언어체계를 유한 상태 언어(有限狀態言語)라고 한다. 이러한 언어의 상태를 그림으로 표시할 수 있는데, 아래와 같이 교점(交點)과 이들을 잇는 화살표를 통틀어서 유한 상태 기계(有限狀態機械)라고 한다.

위 그림의 유한 상태 기계에서 A, B, C는 문자의 입력을 기다리는 상태를 의미한다. 기억하기 쉽도록 윷놀이처럼 원에 말을 얹어놓고 진행할 수 있는데, 문자가 입력되면 해당 문자 표시가 된 화살표를 따라 말을 옮겨놓으면 된다. A 상태에서 시작하면 3가지 경로로 이동할 수 있다. 마침표(.)가 입력되면 종료 지점 C상태로 직행하며 기계 작동이 끝난다. 왼쪽(열리는) 괄호를 입력하면 A에서 B로 상태가 전환된다. 이외에 한글 글자 마디, 알파벳, 숫자를 허용하고 이를 통틀어 별표(*)로 표시하자. 별표에 해당하는 글자를 연속해서 입력하다가 오른쪽(닫는) 괄호를 입력하면 B에서 A로 돌아온다. 괄호가 열려 있는 동안에는 작동 종료 상태로 직행할 수 없고 반드시 괄호를 닫아 A 상태로 돌아온 다음에 C 상태로 갈 수 있다. 이 기계가 유효하고 완전하다고 인식할 수 있는 메시지로는 “배(과일)를사러간다.” “스물여덟(28)자를맹가노니.” “넬읽룰어삐넉켰쩂.” 등이 있다. 반면 “불이야!” “광복절(8.15)행사”와 같이 한국어로 유의미하지만 마침표로 끝나지 않거나 마침표가 괄호 안에 등장하는 문자열은 이 기계가 올바르게 인식할 수 없다. 워드프로세서에서 사용자가 문장을 올바르게 쓰지 않았을 때 빨간 밑줄을 표시해 주는 맞춤법 검사 기능은 이러한 유한 상태 기계에 온갖 규칙을 더하여 수백, 수천 개의 교점을 간선(幹線)으로 조밀하게 이어 나타낼 수 있는 언어논리 체계에 기반해 있다고 할 수 있다.

유한 상태 기계는 언어상에서 올바른 문장을 인식, 구분하는 용도 외에도 다양한 영역을 지배하는 논리체계를 분석하거나 설계할 때 사용된다. 현재 우리나라의 폭염 경보체계를 조금 단순화하면 아래의 유한 상태 기계로 나타낼 수 있다. 시작점을 A로 하고, 하루에 한 번 정해진 시간에 기상청에서 발표하는 내용에 따라 어느 화살표를 타고 이동할지 결정하면 된다. 35도 미만에서 별다른 기상 특보가 없을 때는 A에서 원을 그리며 돌아오는 화살표를 따라 제자리걸음을 한다. 어느 날 35도 이상의 온도가 측정되면 B 상태로 넘어가지만, 다음 날 다시 35도 아래로 내려오면 다시 A로 돌아간다. 하지만 B 상태에서 한 번 더 35도 이상의 온도가 측정되면 폭염 경보(C)가 발령된다. 이후에는 온도가 떨어지더라도(*) 기상청에서 공식적으로 경보 해제를 발표해야만 보통 상태인 A로 돌아갈 수 있다. 아래의 유한 상태 기계는 결국 폭염 경보의 발표 기준인 “35도 이상의 온도가 2일 이상 지속될 때”라는 (인간의 언어로 표현된) 조건을 컴퓨터가 인식할 수 있는 형태로 변환한 결과다.

이외에도 자판기에서 현재 어떤 동전이 몇 개씩 투입되었는지에 따라 구입 가능한 제품을 밝게 비추기, 교통카드 충전이나 결제 과정, 엘리베이터, 교통 신호 체계 등에서 발생하는 논리체계를 유한 상태 기계로 표현할 수 있다. 이로 인해 우리의 일상은 잘 정의된 상태와 규칙의 연속으로 구성되며, 사용자에게 예측 가능하고 안정적인 경험을 제공하는 순기능을 한다. 하지만 동시에 사용자의 행동을 정해진 틀 안에 가두는 역할도 한다. ‘허용된 입력’ 외의 행동은 오류로 처리되며, 시스템이 정한 경로를 벗어나는 것은 거의 불가능하다. 이처럼 효율성과 통제라는 가치를 위해 설계된 시스템들은 때로 사용자의 자율성을 제한하고, 정해진 각본에 따라 살아가도록 유도하는 사회적 영향을 미친다.

여기까지 다룬 유한 상태 기계의 가장 근본적인 특징은 결정론(決定論)이다. 특정 상태에서 특정 입력을 받으면 다음 상태는 반드시 하나로 정해진다. 여러 개의 간선 중 하나를 확률적으로 선택해서 다음 상태로 가는 비결정론적 유한 상태 기계라는 개념도 알고리즘 설계의 중요한 도구로 존재하지만, 하드웨어 제어나 네트워크 서비스 등 현대 기술에서 실제로 실행되는 대부분의 알고리즘은 결정론적 유한 상태 기계를 기반으로 구동된다. 만약 인간의 정신이나 사회 현상을 유한 상태 기계에 담을 수 있다면, 우리의 선택이나 사회의 변화 역시 미리 정해진 경로를 따르는 것에 불과한가? 이는 자유의지의 존재에 대한 오래된 철학적 논쟁을 다시 소환한다. 우리의 ‘선택’이라는 행위가 사실은 수많은 내부 상태와 외부 입력값에 의해 결정되는, 복잡하지만 결국은 예측 가능한 기계의 작동은 아닌지 성찰하게 만든다.

양창모 이학박사