數學 포털

計算 理論 (計算理論, Theory of computation)은 컴퓨터 科學 의 한 갈래로, 어떤 問題를 컴퓨터 로 풀 수 있는지, 또 얼마나 效率的으로 풀 수 있는지를 探究한다. 이 分野는 크게 計算 可能性 理論 과 計算 複雜度 理論 으로 나뉘어 있는데, 두 分野 모두 抽象 機械 를 다룬다.

計算에 對한 嚴格한 硏究를 遂行하기 위해, 컴퓨터 科學者들은 計算 모델이라고 불리는 컴퓨터의 數學的 抽象化로 作業한다. 여러 모델이 使用되고 있지만 가장 一般的으로 檢討되는 모델은 튜링 機械 다. 컴퓨터 科學者들이 튜링 機械를 硏究하는 理由는 튜링 機械가 公式化하기 쉽고, 分析되고, 結果를 證明하는 데 使用될 수 있으며, 많은 사람들이 可能한 가장 强力한 "合理的인" 計算 모델이라고 생각하는 것을 나타내기 때문이다. 潛在的으로 無限한 메모리 容量은 實現 不可能한 屬性으로 보일 수 있지만 튜링 機械에 依해 解決되는 決定 可能한 問題는 恒常 有限한 量의 메모리만 必要로 한다. 따라서 原則的으로 튜링 機械로 解決할 수 있는 모든 問題는 有限한 量의 메모리를 가진 컴퓨터로 解決할 수 있다.

이 글은 컴퓨터 科學에 關한 토막글 입니다. 여러분의 知識으로 알차게 文書를 完成해 갑시다.