[Automata Theory] Introduction

What is Automata?

오토마타는 그리스어 'αὐτόματα'에서 유래한 말로 한국어로 번역하면 "자동 기계"라는 뜻을 가지고 있다. 정확히는 오토마타는 복수형이고, 단수형은 오토마톤(Automaton)이다. 이 자동 기계는 상태를 가지고 있고, 입력을 받을 수 있고, 특정 규칙에 따라 작동하며 메모리를 가질 수도 있다. 무언가 현재의 컴퓨터와 유사한 부분이 많다는 생각이 들지 않는가? 정확하다. 오토마타는 이론적으로 추상화된 컴퓨터라고 할 수 있다. (사실 컴퓨터가 오토마타 이론에서부터 출발한 것이므로 오토마타를 구현한 것이 컴퓨터라고 해야 맞다.)

 

Why Automata Theory?

오토마타 이론(Automata Theory)은 말 그대로 오토마타와 그로부터 유도되는 문제 등을 연구하는 학문이다. 그리고 위에서 설명한 것처럼 컴퓨터과학의 기반을 이루는 분야이다. 그렇다면 이것이 왜 중요한 학문일까? 왜냐하면 오토마타는 한마디로 수학적으로 정의된 컴퓨터기 때문이다. 따라서 컴퓨터를 연구함에 있어서 컴퓨터의 능력, 한계 등을 규정할 때 이 학문이 필요하다. 쉬운 예로 정지 문제(Halting Problem)가 있다. 이 문제는 어떤 프로그램이 어떤 입력을 받았을 때 멈출지 영원히 멈추지 않을지 판별하는 문제인데, 모든 프로그램과 모든 입력에 대해 이 문제를 풀 수 없음이 증명되었다. 이 문제가 중요한 이유는 현재의 컴퓨터로는 풀 수 없는 문제가 존재한다는 것을 의미하기 때문이다. 따라서 컴퓨터로 풀 수 있는 문제를 정의하고 판별하는 것이 중요해졌다. 보다 자세한 설명은 추후의 글에서 할 것이다.

 

Plan

앞으로 이 카테고리에 오토마타 이론에 대한 글을 포스팅할 예정이다.

모든 내용은 서울대학교 박근수 교수님의 '오토마타이론' 강의자료에 기반을 두고 있고, 교수님의 허락을 받고 포스팅을 진행함을 밝힌다.