계산 이론

튜링 머신의 예술적 표현

계산 이론(計算理論, Theory of computation)은 컴퓨터 과학의 한 갈래로, 어떤 문제를 컴퓨터로 풀 수 있는지, 또 얼마나 효율적으로 풀 수 있는지를 탐구한다. 이 분야는 크게 계산 가능성 이론과 계산 복잡도 이론으로 나뉘어 있는데, 두 분야 모두 추상 기계를 다룬다.

계산에 대한 엄격한 연구를 수행하기 위해, 컴퓨터 과학자들은 계산 모델이라고 불리는 컴퓨터의 수학적 추상화로 작업한다. 여러 모델이 사용되고 있지만 가장 일반적으로 검토되는 모델은 튜링 기계다. 컴퓨터 과학자들이 튜링 기계를 연구하는 이유는 튜링 기계가 공식화하기 쉽고, 분석되고, 결과를 증명하는 데 사용될 수 있으며, 많은 사람들이 가능한 가장 강력한 "합리적인" 계산 모델이라고 생각하는 것을 나타내기 때문이다. 잠재적으로 무한한 메모리 용량은 실현 불가능한 속성으로 보일 수 있지만 튜링 기계에 의해 해결되는 결정 가능한 문제는 항상 유한한 양의 메모리만 필요로 한다. 따라서 원칙적으로 튜링 기계로 해결할 수 있는 모든 문제는 유한한 양의 메모리를 가진 컴퓨터로 해결할 수 있다.