계산 이론 개론

Category:계산 이론 개론

개요

해당 문서에서는 기계적 계산(machine computation)에서 등장하는 추상적인 개념들을 소개한다. 이를 위해 다루는 주제는 유한 오토마타(finite automata), 정규 표현식(regular expressions), 형식 언어(formal languages) 등을 포함한다.

Logic and Proofs

수학적 명제(Assertion)의 구조에 익숙해지기 위해서는 명제 연결자(Propositional connectives)와 수량자(Quantifier) 등의 개념에 익숙해져야 한다. 또한 어떤 명제가 주어졌을 때, 이를 바탕으로 다른 명제를 증명하는 구조 역시 중요하다. 이러한 개념과 구조 등은 Logic and Proofs 문서에 자세히 설명된다.

Mathematical Objects

수학적인 명제혹은 주장들은 각종 수학적인 객체들에 대한 문장이나 진술로 해석될 수 있다. 따라서 수학적인 객체에 대한 이해는 매우 중요하며, 이에 따라 해당 문단에서는 각종 수학적 객체들에 대해 설명한다.

• Sets: 순서가 없는 객체들의 모임을 의미한다.
• Functions: 입력이 주어지면 이에 따라 출력을 내는 "블랙박스"로 이해할 수 있다.
• Relations: 어떤 객체 혹은 객체의 쌍에 대해 "참/거짓"을 판별하는 속성을 의미한다.
• Ordered Pairs and Tuples: 순서가 정해진 객체들의 모임을 의미한다.
• Natural Numbers: 0, 1, 2, 3, … 같은 기본적인 수 체계이다.

Finite Automata와 Regular Languages

Finite Automaton은 유한한 메모리를 가진 단순한 계산 장치를 수학적으로 모델링한 것이며, FSM(Finite State Machine)의 가장 기본적인 형태이다. 이는 단순한 계산 장치이며, "유한 메모리"이기 때문에 무한한 기억이나 복잡한 연산이 불가능하고, 오직 현재 상태와 입력에 따라 동작만 결정된다는 특징이 있지만, 다양한 활용 분야를 가지고 있다.

자세한 내용은 Finite Automata 문서를 참조하십시오. 또한 finite automata를 이용하면, Regular Languages를 정의할 수 있다. Regular languages와 관련된 개념으로는 아래의 것들이 있다:

• Languages
• Regular Expressions
• Generalized NFA
• Grammars
• Nondeterministic Finite Automata
• Chomsky Normal Form
• CYK Algorithm
• Pushdown Automaton
• Pumping Lemma

Turing Machines

튜링 머신(Turing Machine)은 계산의 본질을 단순한 모델로 표현한 이론적 컴퓨터 모델이다. 튜링 머신은 모든 계산 가능한 것을 정의하는 최초의 이론적 모델로서 현대 컴퓨터의 이론적 토대를 마련했다. 또한 , 튜링 머신을 통해 계산 가능성의 한계를 증명하고, 어떤 언어의 능력을 평가하는 '튜링 완전성' 개념의 기반이 되었다.

튜링 머신(Turing Machine)에 대한 자세한 설명은 해당 문서를 참조해 주십시오.