在理論計算機科學和數學中，計算理論是處理在計算模型上可以解決哪些問題、使用算法、解決這些問題的效率或程度（例如，近似解決方案與精確解決方案）的分支 ). 該領域分為三個主要分支：自動機理論和形式語言、可計算性理論和計算復雜性理論，它們由以下問題聯系起來：計算機的基本能力和局限性是什么？。

為了對計算進行嚴格的研究，計算機科學家使用計算機的數學抽象，稱為計算模型。 有幾種模型在使用，但最常檢查的是圖靈機。 計算機科學家研究圖靈機是因為它易于表述，可以分析并用于證明結果，還因為它代表了許多人認為xxx大的合理計算模型（參見丘奇-圖靈論文）。 潛在的無限內存容量似乎是一個無法實現的屬性，但圖靈機解決的任何可判定問題總是只需要有限數量的內存。 所以原則上，任何可以由圖靈機解決（決定）的問題都可以由具有有限內存的計算機解決。

計算理論可以被認為是計算機科學領域中各種模型的創建。 因此，使用數學和邏輯。 上個世紀它成為一門獨立的學科，與數學分離。

計算理論的一些先驅是拉蒙·魯爾、阿朗佐·丘奇、庫爾特·哥德爾、艾倫·圖靈、斯蒂芬·克萊恩、羅薩·彼得、約翰·馮·諾依曼和克勞德·香農。

自動機理論是對抽象機器（或更恰當地說，抽象“數學”機器或系統）以及可以使用這些機器解決的計算問題的研究。 這些抽象機器稱為自動機。 Automata 來自希臘語單詞 (Αυτ?ματα)，意思是某物正在自己做某事。自動機理論也與形式語言理論密切相關，因為自動機通常按它們能夠識別的形式語言類別進行分類。 自動機可以是形式語言的有限表示，而形式語言可能是無限集。 自動機用作計算機器的理論模型，并用于證明可計算性。

語言理論是數學的一個分支，它關注將語言描述為對字母表的一組操作。 它與自動機理論密切相關，因為自動機用于生成和識別形式語言。 有幾類形式語言，每一種都允許比之前的更復雜的語言規范，即喬姆斯基層次結構，每一種都對應于一類識別它的自動機。 因為自動機被用作計算模型，所以形式語言是任何必須計算的問題的首選規范模式。

可計算性理論主要處理問題在計算機上可解決的程度的問題。 圖靈機無法解決停機問題是可計算性理論中最重要的成果之一，因為它是一個具體問題的示例，該問題既易于表述又無法使用圖靈機解決。 許多可計算性理論都建立在停機問題的結果之上。

可計算性理論的另一個重要步驟是賴斯定理，該定理指出對于偏函數的所有非平凡屬性，圖靈機是否計算具有該屬性的偏函數是不可判定的。

可計算性理論與稱為遞歸理論的數理邏輯分支密切相關，遞歸理論消除了僅研究可簡化為圖靈模型的計算模型的限制。 許多研究遞歸理論的數學家和計算理論家將其稱為可計算性理論。

復雜性理論不僅考慮一個問題是否可以在計算機上完全解決，而且還考慮解決問題的效率。 主要考慮兩個方面：時間復雜度和空間復雜度，分別是執行一次計算需要多少步，以及執行該計算需要多少內存。

為了分析給定算法需要多少時間和空間，計算機科學家將解決問題所需的時間或空間表示為輸入問題大小的函數。 例如，隨著數字列表變大，在一長串數字中查找特定數字會變得更加困難。