집밖은 위험해

1. 오토마타 automata, 계산가능성 computabilty, 복잡도 complexity

이 자료에서는 계산 이론의 핵심 분야인 오토마타와 계산 가능성, 복잡도에 대해서 살펴보겠습니다.

이것들은 "컴퓨터의 능력과 한계는 무엇일까?"라는 질문과 연관될수 있겠는데요.

 이 질문은 1930년대 계산의 의미를 탐구하기 시작한 수학자들이 시작하였습니다. 기술적인 발전으로 이론의 영역이었던 이 질문이 지금 현실 문제까지 다뤄지고 있습니다. 오토마타와 계산가능성 그리고 복잡도는 매우 다르게 해설할수 있겠고, 다양하게 대답할수 있겠습니다. 개요에서는 각 개념들에 대한 내용들을 살펴보겠습니다.

계산 복잡도 이론 complexity theory

 컴퓨터 문제는 쉬운 문제도 있고, 어려운 문제도 있고 매우 다양합니다. 정렬 문제는 쉬운 편일 텐데 예시로 숫자 리스트를 오름차 순으로 정렬하는 경우가 있을 것이고, 작은 컴퓨터도 이런 쉬운 문제는 수백만개의 숫자를 빠르게 정렬할수 있을 겁니다.

 하지만 수업 스캐줄링 문제 같은 경우를 생각해보면, 같은 시간에 같은 교실에서 2개 이상의 수업이 있어서는 안되며, 학교 전체에서 이런 제약조건들을 만족하는 수업 일정을 구해야만 합니다. 이 점에서 스캐줄링 문제는 정렬 문제보다 훨씬 힘든 문제라 할수 있겠죠. 특히 교실이 수천개가 있다면 최고의 답을 찾으려면 슈퍼컴퓨터로 수세기가 걸릴겁니다.

"그러면 어떤 문제들이 계산하기 쉬운 것이고 어려운 것일까요?"

 이 것이 계산 복잡도이론의 핵심 질문이라 할수 있겠습니다. 40년이 지난 지금도 아무도 이 해답을 모릅니다.

 계산 복잡도 이론의 중요성을 고려하여 연구자들이 계산의 어려움에 따라서 문제를 분류하는 방법들을 연구하였습니다. 이건 주기율표에서 화학물질질들의 성질에 따라 요소들을 분류하는것과 비슷하다고 할수있는데, 이 방법을 사용해서 특정 문제들이 증명할수 없더라도 계산하기 힘든 문제인지 알아내는 방법을 살펴보겠습니다.

 이것 외에도 계산하기 어려운 문제가 있을때 다양한 방법이 있는데, 첫번째로 이 문제의 해를 찾는일의 어려움을 알고, 이 문제를 풀기 더 쉬운 문제로 바꾸면 됩니다. 두번째로는 덜 완벽한 해를 찾을수도 있겠는데, 완벽한 해보다 근사한 해를 찾는게 쉽겠죠. 세번째로, 어떤 문제는 최악의 상황에서만 힘들지 대부분의 경우에 풀기 쉬운 문제들도 있습니다. 이 경우에 가끔 느리지 대부분은 빠르게 동작할겁니다. 마지막으로 임의의 연산 randomized computation 같은 다른 타입의 연산을 생각해볼수도 있을겁니다.

  계산 이론이 직접적으로 가장 영향을 주는 분야라면 암호학 분야라고 할수 있겠습니다. 대부분의 분야에서는 계산하기 쉬운 문제들이 선호되고 있기 때문인데, 암호학 분야의 경우에는 특히 쉬운 것보다 어려운 계산문제를 필요로 하기 때문입니다. 비밀 코드들은 비밀 키나 패스워드 없이는 뚫기 힘들어야 되겠죠. 계산 복잡도 이론은 암호학자들이 새로운 코드를 설계하여 계산 하기 힘든 문제들을 다루는것을 목표로 하고 있겠습니다.

계산 가능성 이론

 20세기 중반까지 앨런 튜링, 커트 고델 같은 수학자들이 특별한 문제들은 컴퓨터로 풀수 없는것을 찾아내었습니다. 이 형상의 예시 중 하나로 한 수학적 명제가 참인지 거짓인지 증명하는 문제인데, 이 작업은 수학자들에게 빵이 우선인지 버터가 우선인지  같은 문제였습니다. 컴퓨터가 풀기 힘든건 자연스러워 보이겠지만, 어느 컴퓨터 알고리즘도 이 작업을 풀수 없습니다.

 이 문제에 대한 심오한 결과로부터 실제 컴퓨터를 만드는데 기원이 되는 이론적으로 이상적인 컴퓨터 모델에 대한 아이디어가 나오게 되었습니다.

 계산 가능성과 계산 복잡도 이론은 가까이 연관되어 있는데, 계산 복잡도 이론에서 목표는 문제가 쉬운것인지 어려운것인지 보는것이고, 계산 가능성 이론에서는 이 문제가 풀수있는 문제인지 없는 문제인지 찾아내는 것입니다. 계산 가능성 이론은 계산 복잡도 이론에서 사용되는 다양한 개념들이 나오게 됩니다.

오토마타 이론

 오토마타 이론은 수학적 계산모델의 정의와 성질들을 다루는 학문입니다. 이 모델들은 컴퓨터 과학의 여려 분야에서 역활을 하고 있는데요. 유한 오토마타 finit automaton 이라고 하는 한 모델은 텍스트 처리, 하드웨어 설계, 컴파일러 등에서 사용되고  있습니다. 다른 모델로 문맥 자유 문법 context-free grammar라는 모델이 있는데 이 모델은 프로그래밍 언어와 인공지능에서 사용되고 있습니다.

 오토마타 이론은 계산 이론에 대한 연구의 시작이 되었으며, 계산 가능성과 계산 복잡도 이론이 컴퓨터의 정확한 정의를 요구하였다면 오토마타 이론은 계산의 형식적 정의 formal definition를 가지고 수행하며, 다른 컴퓨터 과학의 이론적이지 않은 다른 영역과 관련된 개념들을 제시하고 있습니다.