튜링상 관련 업적
래빈과 스콧의 1959년 논문, ‘유한 오토마타와 결정 문제들’은 형식 언어 이론의 고전적 논문이 되었으며 아직도 이 분야의 최고 입문용 글 중 하나이다….
1976년 튜링상 선정 이유 중에서4
그 후에도 래빈과 스콧은 각자 (해당 분야의) 표준으로 자리 잡은 기여를 해왔다. 그 깊이와 차원을 보여주는 대표적인 사례를 들어보면, 래빈은 오토마타 이론을 논리학에 적용해왔고 스콧은 프로그래밍 언어를 위한 의미론을 개발해왔다. 전자는 컴퓨터 과학을 수학에 적용하는 것이고, 후자는 수학을 컴퓨터 과학에 적용하는 것이라고 하겠다.
형식 언어formal language란 정해진 법칙을 따르는 언어를 말한다. 이 세상에 법칙(규칙)이 없는 언어가 어디에 있겠느냐마는, 우리가 일상에서 사용하는 한국어, 영어, 중국어 등은 모두 예외적인 상황을 가지고 있다. 그런 점에서 형식 언어는 실험실에 가둬 놓은 언어라고 볼 수 있다. 형식 언어는 수학, 컴퓨터 과학 등에서 그 빛을 발한다. 그리고 오토마타 이론은 형식 언어 연구에서 아주 중요한 역할을 한다.
오토마타
오토마타automata는 오토마톤automaton의 복수형이다. 오토마톤은 원래 자동 기계를 의미하던 단어였다. 역사적으로 사용된 사례를 보면, 단순한 동작을 자동으로 수행하는 인형을 가리키는 경우가 대부분이었다.5
컴퓨터 과학에서 말하는 오토마타는 이와 다르다. 래빈과 스콧의 논문, <유한 오토마타와 결정 문제들>에는 이렇게 정의되어 있다.
오토마톤이란, 질문이 입력되면 “예” 또는 “아니오”라는 답을 출력하는 블랙박스이다.6
상당히 단순하면서도 감을 잡기 어려운 정의이다. 이 정의는 ‘힐베르트의 결정 문제’를 연상시킨다.
어떤 문장statement이 입력으로 주어졌을 때, 공리를 만족시키는 모든 구조 내에서 이 문장이 참이면 ‘네’, 그렇지 않으면 ‘아니오’를 답하는(계산하는) 알고리듬이 항상 존재하는가?7
힐베르트가 궁금해했던 것은, 수학적 문장이 주어졌을 때 이것이 맞는지 틀리는지를 자동으로 알아낼 방법이 항상 있느냐는 것이었고, 내심 그는 가능하다고 믿었다.§§
힐베르트의 결정 문제는, 참/거짓을 자동으로 계산할 수 있는 추상적 기계에 관한 연구를 자극했다. 우리가 흔히 접하는 수학적 문제는, 숫자 혹은 문자와 같은 기호로 구성된 수식이나 도형을 대상으로 한다. 그런데 힐베르트의 결정 문제를 풀기 위해서는 ‘계산이라는 과정’ 그 자체를 수학적으로 모델링해야만 한다. ‘계산하는 과정’을 어떻게 수학적으로 다룰 수 있을까? 이에 대한 해결책 중 하나가 앨런 튜링이 제시한 튜링 기계Turing machine였다.8
튜링 기계는, 입력 정보가 적혀 있는 테이프와, 이 테이프에서 한 칸씩 입력 정보를 읽는 헤드head, 입력 정보에 의해 전이되는 내부 상태 등으로 구성되어 있다. 이 추상적인 기계는 ‘계산’이라는 과정을 모두 표현할 수 있다. 만약 어떤 ‘계산’ 혹은 ‘알고리듬’이 튜링 기계의 메커니즘을 통해 표현될 수 없다면 그것은 결국 불가능한 ‘계산’이 되는 셈이다. 튜링 기계의 특징이라면 테이프에 적혀 있는 입력 정보를 기계가 수정할 수 있다는 점과, 테이프가 한 방향으로만 이동하는 것이 아니라 앞뒤로 다 움직일 수 있다는 것이다.
래빈과 스콧도 언급했듯이 오토마톤은 일종의 블랙박스와도 같다. 내부가 어떻게 되어있든지 간에 답을 출력하면 된다. 그래서 오토마톤은 다양한 형태로 모델링되었다. 사실, 단순한 논리 회로도 오토마톤이다. 예를 들어 두 개의 입력을 받아서 논리곱(AND)을 하는 단순한 회로를 생각해보자. 입력을 받아서 참/거짓이라는 출력이 나오므로 이것도 역시 오토마톤이다.
튜링 기계Turing machine도 역시 오토마톤이라고 볼 수 있다. 이 외에도 맥컬록과 피트는 신경망neural network 형태의 오토마톤을 제안했고 폰 노이만은 셀 오토마타cell automata라는 형태의 모델을 연구했다.
튜링 기계가 ‘계산’을 모델링한다는 점에서, 튜링 기계는 ‘계산’하는 기계인 컴퓨터의 추상적인 모형으로 생각할 수 있다. 하지만 튜링 기계는 그 강력함에도 불구하고 단점을 가지고 있다. 어떤 계산을 튜링 기계로 모델링하려고 할 때, 튜링 기계의 입력과 출력에 사용되는 테이프의 최대 길이(즉 용량)를 미리 예측할 수 없다는 점이다. 현실 세계의 컴퓨터는 자원에 제한을 두고 있다. 따라서 튜링 기계는 현실 세계의 컴퓨터를 대변할 수 없다.
그런 이유에서 자원의 제약을 전제로 하는 추상적 모델링이 필요했고 유한 오토마타가 대두되었다.
유한 오토마타
실질적으로 컴퓨터 과학에서 다루는 오토마타는 주로, 유한 오토마타finite automata 혹은 유한 상태 기계finite state machine를 가리킨다. 이 추상적인 기계는, 내부에 있는 상태의 개수가 유한하고, 한 상태에서 다른 상태로 전이되기 위한 조건이 정해져 있으며, 입력값은 변경되는 일 없이 순서대로 처리된다. 그래서 초기 상태에서 어떤 입력값들이 순차적으로 들어오면 상태 사이의 전이가 계속 일어나며, 마지막 입력값에 의해 도달한 상태가 무엇이냐에 따라 “예” 또는 “아니오”가 결정된다. 래빈과 스콧은 튜링 기계와 유사한, 아주 단순한 유한 상태 기계를 가정했다.
우리는 일차원 테이프가 입력되는 기계를 가정한다. 읽기 장치head가 있는 이 기계는 입력되는 테이프를 한 칸씩 읽는다. 테이프의 각 칸마다 한 개의 문자가 쓰여 있다… 우리는 기계가 어떤 식으로 만들어졌는지에는 관심이 없으며 그것의 동작에만 신경을 쓸 것이다. 불필요한 세부 사항을 피하는 간단한 방법은 ‘내부 상태’라는 개념을 사용하는 것이다. 기계 안에 전선이나 진공관이 얼마나 있든지 간에, 기계의 동작은 기계의 내부 상태에 의해 결정된다… 사실, 어떤 상태에서 어떤 문자가 입력되었을 때 어떤 새로운 상태로 전이하는지를 모두 정리한 표를 만들면, 실질적으로 이 기계의 모든 동작을 표현하는 셈이 된다.6
내부에 상태를 가지고 있고, 입력에 반응하는 종류의 시스템(생명체, 컴퓨터, 소프트웨어)이라면 오토마타로 모델링할 수 있다. 컴퓨터 과학 분야에서는 컴파일러, 텍스트 처리 등에 유한 오토마타 이론이 사용되고 있다.
결정적 유한 상태 기계 / 비결정적 유한 상태 기계
‘결정적deterministic‘이라는 말은, 달리 다른 수가 없다는 의미이다. 결정적 유한 상태 기계에서는, 어떤 상태에서 어떤 입력이 들어오면 다른 수 없이 하나의 상태 전이가 일어난다. 이에 비해 ‘비결정적nondeterministic‘이라는 말은, 다른 수가 있을 수도 있다는 의미이다. 즉, 어떤 상태에서 어떤 입력이 들어왔을 때 한 가지 수만 있는 것이 아니라 몇 가지 수가 있을 수도 있다는 말이다.
결정적 유한 상태 기계의 예
| 현재상태 | 입력값이 0일 때 다음 상태 | 입력값이 1일 때 다음 상태 |
| S0 | S1 | S3 |
| S1 | S2 | S2 |
| S2 | S3 | S2 |
| S3 | S3 | S3 |
결정적 유한 상태 기계의 상태 전이표를 보면, 현재 상태에서 어떤 입력값이 들어왔을 때 다음 상태는 오직 한 개만 존재한다.
비결정적 유한 상태 기계의 예
| 현재상태 | 입력값이 0일 때 다음 상태 | 입력값이 1일 때 다음 상태 |
| S0 | S0, S1 | S2 |
| S1 | S2 | S0, S3 |
| S2 | S2 | S3 |
| S3 | S3 | S3 |
비결정적 유한 상태 기계의 상태 전이표를 보면, 현재 상태에서 어떤 입력값이 들어왔을 때 다음 상태는 여러 개가 될 수도 있다.
앞에서 언급했듯이 래빈과 스콧은 오토마타가 ‘예’ 또는 ‘아니오’라는 답을 주는 일종의 블랙박스라고 보았다. 그러므로 내부가 어떻게 되어 있건 간에 주어진 입력들에 대해 “예” 또는 “아니오”라는 답이 같기만 하면 두 개의 오토마타는 동일한 일을 한다고 볼 수 있다. 어차피 같은 일을 하는 오토마타라면 내부의 상태 개수가 적을수록 비용이 적게 든다.
래빈과 스콧은 <유한 오토마타와 결정 문제들> 논문에서, 비결정적 유한 상태 기계라는 개념을 처음으로 제시하였고, 비결정적 유한 상태 기계와 동일한 일을 하는 결정적 유한 상태 기계가 항상 존재함을 보였다. 비결정적 유한 상태 기계는, 동일한 일을 하는 결정적 유한 상태 기계에 비해 내부 상태의 개수가 훨씬 적다. 더 간단하게 컴퓨터를 만들 수 있다는 의미이다.
확률적 오토마타
확률적 오토마타Probabilistic automata에서는 어떤 상태에서 입력이 들어왔을 때 전이되는 다음 상태가 확률에 의해 결정된다.9 다음 상태의 개수가 여러 개일 수 있다는 점에서 비결정적 유한 상태 기계와 유사해 보이지만, 입력이 처리된 후에 오토마타의 최종 상태가 무엇인지를 따질 때 큰 차이가 있다. 비결정적 유한 상태 기계에서는 여러 경우의 수가 발생하면 이를 다 따져봐서 ‘예’라는 답을 주는 상태가 포함되면 오토마타의 결과가 ‘예’라고 본다. 하지만 확률적 오토마타에서는 여러 경우의 수에 대해 발생할 수 있는 최종 상태가 확률적이므로 그 최종 상태가 ‘예’의 값을 가진다고 해서 이 오토마타의 결과가 ‘예’라고 볼 수 없게 된다.
확률적 오토마타의 현실적 예로는, 오류가 발생할 가능성이 있는 컴퓨터를 들 수 있다. 컴퓨터에 사용되는 부품들은 정도의 차이는 있을지언정 모두 오류가 발생할 가능성이 있다. 따라서 이런 시스템을 오토마타로 모델링하게 되면 확률적 오토마타가 된다.
확률적 오토마타가 어떤 입력을 받았을 때, ‘예’인지 ‘아니오’인지를 답하는 것은 확률에 달려 있다. 믿을 만한 답을 얻기 위해서는 결국 어러 번 시행해서 통계적으로 따져보는 수밖에 없다. 래빈은 확률적 오토마타에 컷아웃cut-out이라는 값을 도입했다. 이는 일종의 기준값으로, 만약 ‘예’라는 상태에 도달할 확률이 컷아웃보다 높다면 이 시스템의 결과는 ‘예’라고 간주하는 식이다.
ω-오토마타
앞에서 설명한 세 가지 오토마타는 모두 입력값의 길이가 유한하다는 전제를 가지고 있다. 즉, 상태 전이의 횟수가 유한한 셈이다. 입력값의 길이가 무한한 경우를 다루는 오토마타가 ω-오토마타이다.
ω-오토마타의 출발은 2차 논리second-order logic의 결정 문제를 다루기 위해서 시작되었다.10 실제 현실 세계에서는, 멈춤이 없이 계속 수행되는 하드웨어나 운영체제 같은 것들을 모델링하는 데 사용된다.
래빈은 이진 트리를 도입해서 ω-오토마타 모형을 만들었다. 그가 생각한 이진 트리는 계속 0과 1로 가지를 치며 무한히 만들어지는 트리였다. 각 노드는 결국 뿌리root 노드로부터 그 노드까지의 경로상에 있는 0과 1로 구성된 문자열에 대응된다.
답글 남기기