계산 이론 개요

다음과 같은 것들이 컴퓨터 과학의 이론적인 기반이다.

  • 오토마타 이론(automata theory)
  • 형식 언어(formal languages)
  • 문법(grammars)
  • 계산 가능성(computability)
  • 복잡도(complexity)

컴퓨터가 무엇을 할 수 있는가?

  • 오토마타(automata), 문법(grammars), 계산 가능성(computability)
    • 원리적으로 컴퓨터가 무엇을 할 수 있는가에 대한 공부.
  • 복잡도(complexity)
    • 실제로 컴퓨터가 무엇을 해낼 수 있는가에 대한 공부.

automata, automaton

  • automaton : 단수형
  • automata : 복수형

컴퓨터 하드웨어를 모델링하기 위해, automaton이란 개념을 도입한다.

  • 디지털 컴퓨터의 필수 기능을 모두 갖고 있다.
    • 입력을 받는다.
    • 출력을 내놓는다.
    • 임시 저장소도 가질 수 있다.
    • 입력을 출력으로 변환하는 과정에서 결정을 내린다.

형식 언어

형식 언어는 프로그래밍 언어의 일반적인 특징을 추상화한 것이다.

  • 형식 언어는 다음으로 구성된다.
    • 기호의 집합(a set of symbols).
    • 기호를 조립해 문장(sentences)으로 변환하는 규칙들.
  • 형식 언어는 조립 규칙들로 생성되는 모든 문장의 집합이다.
  • 형식 언어는 프로그래밍 언어보다는 심플하지만, 많은 필수적인 기능들을 갖고 있다.
  • 형식 언어를 통해 프로그래밍 언어에 대해 많은 것을 배울 수 있다.

앞으로…

알고리즘이란 용어를 정의하여 기계적인 계산(mechanical computation)의 개념을 formalize할 것이다.

  • 기계적인 계산으로 답을 찾을 수 있/없는 문제의 종류에 대해 공부할 것이다.
  • 공부하는 과정에서, 우리는 이러한 추상적인 것들 사이의 밀접한 관계를 보여줄 것이다.
  • 그리고 그것들을 통해 얻어낼 수 있는 결론들에 대해 공부하게 될 것이다.