可計算性是有效解決問題的能力。 它是數理邏輯中可計算性理論領域和計算機科學中計算理論領域的一個關鍵課題。 問題的可計算性與解決問題的算法的存在密切相關。

研究最廣泛的可計算性模型是圖靈可計算和 μ 遞歸函數，以及 lambda 演算，所有這些模型都具有等效的計算能力。 還研究了其他形式的可計算性：在自動機理論中研究了比圖靈機弱的可計算性概念，而在超計算領域研究了比圖靈機強的可計算性概念。

可計算性的一個中心思想是（計算）問題，這是一個可以探索其可計算性的任務。

有兩種關鍵類型的問題：

• 一個決策問題解決了一個集合 S，它可以是一組字符串、自然數或從某個更大的集合 U 中取出的其他對象。該問題的一個特定實例是決定，給定 U 的一個元素 u，是否 u 在 S 中。例如，設 U 為自然數集，S 為素數集。 對應的決策問題對應素數檢驗。
• 函數問題由從集合 U 到集合 V 的函數 f 組成。該問題的一個實例是計算給定 U 中的元素 u 和 V 中對應的元素 f(u)。例如，U 并且V可以是所有有限二進制字符串的集合，f可以取一個字符串并返回通過反轉輸入的數字得到的字符串（因此f（0101）= 1010）。

其他類型的問題包括搜索問題和優化問題。

可計算性理論的一個目標是確定在每個計算模型中可以解決哪些問題或一類問題。

計算模型是對特定類型的計算過程的正式描述。 描述通常采用旨在執行手頭任務的抽象機器的形式。 相當于圖靈機的一般計算模型（參見 Church-Turing 論文）包括：

Lambda 演算一個計算由一個初始的 lambda 表達式（或者兩個，如果你想把函數和它的輸入分開）加上一個有限的 lambda 項序列組成，每個 lambda 項都是通過一個 beta 歸約應用從前面的項中推導出來的。組合邏輯一個有很多概念的概念 與 λ {\\displaystyle \\lambda } -演算有相似之處，但也存在重要差異（例如，定點組合子 Y 在組合邏輯中具有范式，但在 λ {\\displaystyle \\lambda } -演算中則沒有）。 組合邏輯的發展具有雄心壯志：理解悖論的本質，使數學基礎更經濟（概念上），消除變量的概念（從而闡明它們在數學中的作用）。μ遞歸函數計算由μ遞歸函數組成 ，即它的定義序列，任何輸入值和出現在具有輸入和輸出的定義序列中的遞歸函數序列。 因此，如果在遞歸函數 f(x) 的定義序列中出現函數 g(x) 和 h(x,y)，則形式為 g(5) = 7 或 h(3,2) = 10 的項 可能會出現。 此序列中的每個條目都需要是基本函數的應用程序，或者通過使用組合、原始遞歸或 μ 遞歸從上面的條目中得到。 例如，如果 f(x) = h(x,g(x))，那么要出現 f(5) = 3，g(5) = 6 和 h(5,6) = 3 之類的項必須出現在上方。 只有當最后一項給出應用于輸入的遞歸函數的值時，計算才會終止。

字符串重寫系統包括馬爾可夫算法，該算法使用類似語法的規則對符號字符串進行操作； 也是后規范系統。注冊機計算機的理論理想化。 有幾種變體。 在大多數情況下，每個寄存器都可以容納一個自然數（大小不受限制），并且指令簡單（數量很少），例如 只有遞減（結合條件跳轉）和遞增存在（和停止）。 缺乏無限（或動態增長）的外部存儲（在圖靈機上看到）可以通過用哥德爾編號技術替換它的角色來理解：每個寄存器保存一個自然數的事實允許表示復雜事物的可能性（例如 序列，或矩陣等）通過適當的巨大自然數 - 表示和解釋的明確性可以通過這些技術的數論基礎來建立。圖靈機也類似于有限狀態機，除了輸入是在執行時提供的 磁帶，圖靈機可以讀取、寫入或在其讀/寫頭上來回移動。 允許磁帶增長到任意大小。