계산 이론 개요

The subject matter of this book, the theory of computation, includes several topics: automata theory, formal languages and grammars, computability, and complexity. Together, this material constitutes the theoretical foundation of computer science.

  • 다음과 같은 것들이 컴퓨터 과학의 이론적인 기반이다.
    • 오토마타 이론(automata theory)
    • 형식 언어(formal languages)
    • 문법(grammars)
    • 계산 가능성(computability)
    • 복잡도(complexity)

Loosely speaking we can think of automata, grammars, and computability as the study of what can be done by computers in principle, while complexity addresses what can be done in practice.

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

To model the hardware of a computer, we introduce the notion of an automaton (plural, automata). An automaton is a construct that possesses all the indispensable features of a digital computer. It accepts input, produces output, may have some temporary storage, and can make decisions in transforming the input into the output.

  • 컴퓨터 하드웨어를 모델링하기 위해, automaton(automaton은 단수형. 복수형은 automata)이란 개념을 소개.
    • 디지털 컴퓨터의 필수 기능을 모두 갖고 있다.
    • 입력을 받는다.
    • 출력을 생성한다.
    • 임시 저장소도 가질 수 있다.
    • 입력을 출력으로 변환하는 과정에서 결정을 하기도 한다.

A formal language is an abstraction of the general characteristics of programming languages. A formal language consists of a set of symbols and some rules of formation by which these symbols can be combined into entities called sentences. A formal language is the set of all sentences permitted by the rules of formation. Although some of the formal languages we study here are simpler than programming languages, they have many of the same essential features. We can learn a great deal about programming languages from formal languages.

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

Finally, we will formalize the concept of a mechanical computation by giving a precise definition of the term algorithm and study the kinds of problems that are (and are not) suitable for solution by such mechanical means. In the course of our study, we will show the close connection between these abstractions and investigate the conclusions we can derive from them.

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