이 과목은 무엇을 배우는가?
What are the fundamental capabilities and limitations of computers?
Compute = 컴퓨터가 하는 일
이 강의는 컴퓨터가 할 수 있는 일과 컴퓨터가 하지 못하는 일을 배운다.
그렇다면, 본질적으로 컴퓨터가 하지 못하는 일은 무엇일까?(컴퓨터의 능력과 한계는 어느정도일까?) 수학 이론자들은 1930년도부터 생각하기 시작했다. 심지어 그 때는 컴퓨터가 없었던 시대이다. 그들은 "이런 기계가 있으면 어땠을까?"라고 이론적으로 생각했다.
Complexity, Computability, and Automata
Complexity Theory
컴퓨터로 풀 수 있는 문제들은 여러가지가 있는데, 어떤 문제는 쉽지만 어떤 문제는 지독하도록 어렵다...
Sorting Problem(정렬 문제)나 Searching Problem(탐색 문제)같은 것들은 쉬운 쪽에 속하는 문제들이 있다. 반면에 Scheduling Problem(스케줄 문제)처럼 어려운 문제들도 있다. 수천개의 수업 중 최고의 스케줄을 만드는 문제는, 수퍼컴퓨터로 풀어도 천년 이상 걸릴 것이다. 이것은 문제 자체가 어렵기 때문이다... 그렇기 대문에 어려운 문제가 있는 것을 이해하고 가야한다. P-NP 문제가 있는 것처럼 어떠한 문제가 얼마나 어렵고, 왜 어려운지를 파악하는 것이 Complexity Theory다.
팩트는 나에겐 정렬 문제나 탐색 문제도 어렵다
Computability Theory
1950년도쯤, Gödel, Turing, CHurch등이 "풀 수 없는" 문제들을 찾아냈다.
문제가 해결 가능한지, 불가능한지를 따지는 것을 Computability 라고 하며, 우리는 해결 가능한 문제와 해결 불가능한 문제, 특히 해결 불가능한 문제에 대해서 중점적으로 배울 것이다. 풀 수 없는 문제의 대표격인 홀팅 문제에 대해서 적어놨으니, 시간 나면 보시길
이 세상에는 해결 불가능한 문제들이 존재한다
Automata Theory
Automata : 사람이 행하는 어떤 목적에 합당한 약간 복잡한 동작을 기계적인 제어기구에 의하여 실시하는 장치, 또는 태엽이나 기타 동력이 달려 외부의 조작 없이 스스로 동작하는 기계를 의미한다
오토마타는 계산(Computation)을 수행하는 수학적인 모델이다. 여기서 모델이란 복잡한 것들을 간단하게 나타내는 것을 의미한다.
태양계를 보자. 수성, 금성, 지구, 화성... 더 나아가 지구 안의 생명체들과 유기물... 더 나아가 세포와 원자와 쿼크... 태양계를 공부한다는 것은 이 모든 것을 의미한다. 동의하는가?
그러나 내가 태양계의 인력에 대한 것만 보고싶으면, 태양의 온도는 별로 관련이 없을 것이다.(당연히 관련은 있지만, 다른 것이 더 중요하다는 이야기) 태양의 질량은 당연히 많은 관련이 있을 것이고, 행성들의 거리와 크기 또한 관련이 있을 것이다. 이렇게 태양의 온도나 행성의 색깔 등 별로 관련이 없는 것은 빼고 필요한 것들만 가져다 놓은 것. 이것이 모델이다.
왜 모델이 필요한가?
Compute는 사실 상당히 복잡한 과정이고, 그 과정을 인간이 온전히 이해하기는 어려움이 상당 부분 존재한다. 그렇기에 모델을 이용하여 과정을 간단히 추리고, 이해를 도와준다. 이것이 모델이 필요한 이유이며 mathematical model의 존재 이유다.
어떤 모델은 유한 자동기계(finite automaton)라고 부르며, 텍스트로 작동하는 컴파일러나 하드웨어의 디자인에 쓰인다. 어떤 모델은 문맥 자유 문법 (Context-free grammar)이라고 불리며, 프로그래밍 언어나 인공 지능에 사용된다. 오늘날 컴퓨터의 모델을 튜링 모델(Turing Model)(finite automaton)이라고 하며(제일 비슷한 모델), 현대의 문제보다 좀 더 간단한 일을 해결하는 모델을 푸시다운 자동 기계(Pushdown automaton), 그보다 간단한 일은 유한 자동기계를 이용한다.
문제가 얼마나 어려운 지에 따라 어떤 모델을 사용할지를 고르는것
정리 한 스푼
| Complexity | Computability | Automata |
|---|---|---|
| 문제의 난이도에 대한 이론 | 문제의 해결가능성에 대한 이론 | 문제를 해결하기 위한 알맞은 모델 사용에 대한 이론 |
