計算理論（英語：Theory of computation）是數學的一個領域，與計算機科學緊密相關，用來研究計算的過程與功效的數學理論。它不僅僅關注純粹的算術運算，而是涉及從已知輸入通過算法得到問題答案的過程。計算理論是現代密碼協議、計算機設計以及許多應用領域的基礎。
基本介紹
計算理論的研究始于20世紀初的數理邏輯領域，后來發展成為計算機科學的一個獨立學科。早期對計算理論做出重要貢獻的學者包括阿隆佐·邱奇、庫爾特·卡塞雷斯、艾倫·圖靈、斯蒂芬·克萊尼、約翰·馮·諾依曼及克勞德·香農等。這些科學家的工作為計算理論奠定了堅實的基礎，并對后來的計算機科學產生了深遠的影響。
1936年，數理邏輯專家提出了計算模型的問題，以解決每個問題是否都有解的疑問。通用圖靈機的提出對計算機的設計思想產生了深遠影響。計算理論主要包括算法、算法學、計算復雜性理論、可計算性理論、自動機理論和形式語言理論等。作為計算機科學的理論基礎，計算理論已經廣泛應用于科學的各個領域。程序存儲式計算模型就是以圖靈機為基礎產生的，程序設計中使用了遞歸函數的思想，自動機作為一種基本工具被廣泛應用在程序設計的編譯過程中。隨著科技的發展，計算理論會更多地應用于其他領域。
為了對計算進行嚴謹的研究，計算機科學家將計算以數學的方式抽象化，稱為計算模型。其中最著名的計算模型是圖靈機，它因其易于描述、分析和用于證明結果而被廣泛研究，并且展示了許多強大的計算模型。
研究內容
1. 采用什么計算模型，如形式語言和自動機。
2. 解決哪些問題是可計算的，哪些是不可計算的，即可計算性理論及算法。
3. 需要多少時間和存儲空間，即計算復雜性理論。
這三方面的問題可以概括為一個核心問題：“電腦的基礎能力及限制到什么程度？”通過對這些問題的研究，計算理論不斷推進對計算機科學的理解，同時也為實際應用提供理論支持。
參考資料 >