可計算函數是可計算性理論研究的基本對象。 可計算函數是算法直觀概念的形式化模擬，從某種意義上說，如果存在可以完成函數工作的算法，則函數是可計算的，即給定函數域的輸入，它可以返回相應的函數域 輸出。 可計算函數用于討論可計算性，而不涉及任何具體的計算模型，例如圖靈機或寄存器機。 然而，任何定義都必須參考某些特定的計算模型，但所有有效定義都會產生同一類函數。產生可計算函數集的特定可計算性模型是圖靈可計算函數和一般遞歸函數。

在對可計算函數進行精確定義之前，數學家們經常使用非正式術語“有效可計算”。 這個術語后來被認為是可計算的函數。 請注意，這些函數的有效可計算性并不意味著它們可以被有效計算（即在合理的時間內計算）。 事實上，對于一些可有效計算的函數，可以證明任何計算它們的算法都將非常低效，因為算法的運行時間會隨著輸入的長度呈指數增長（甚至超指數增長）。 可行的可計算性和計算復雜性研究可以有效計算的函數。

根據丘奇-圖靈論題，可計算函數就是在給定無限量的時間和存儲空間的情況下，可以使用機械計算設備計算的函數。 等效地，該論文指出，當且僅當函數具有算法時，該函數是可計算的。 請注意，這個意義上的算法被理解為一個人可以在無限時間和無限供應的筆和紙上執行的一系列步驟。

Blum 公理可用于定義關于可計算函數集的抽象計算復雜性理論。 在計算復雜性理論中，確定可計算函數的復雜性的問題被稱為函數問題。

函數的可計算性是一個非正式的概念。 描述它的一種方法是說如果函數的值可以通過有效的過程獲得，則該函數是可計算的。 更嚴格地說，函數 f : N k → N {\displaystyle f:\mathbb {N} {k}\rightarrow \mathbb {N} } 是可計算的，當且僅當存在一個有效的程序時， 給定任何自然數的 k 元組 x {\displaystyle \mathbf {x} }，將產生值 f ( x ) {\displaystyle f(\mathbf {x} )} 。 與此定義一致，本文的其余部分假定可計算函數將有限多個自然數作為參數并產生一個值，該值是單個自然數。

作為這種非正式描述的對應物，存在多種正式的數學定義。 可計算函數的類別可以在許多等效的計算模型中定義，包括

• 圖靈機
• μ-遞歸函數
• Lambda 演算
• Post 機器（后圖靈機和標簽機）。
• 注冊機器

盡管這些模型對函數、它們的輸入和輸出使用不同的表示，但任何兩個模型之間都存在轉換，因此每個模型本質上描述的是同一類函數，這導致人們認為形式可計算性既自然又不太好 狹窄。 這些函數有時被稱為遞歸函數，與非正式術語可計算形成對比，這種區別源于 1934 年 Kleene 和 G?del.p.6 的討論

例如，可以將可計算函數形式化為 μ 遞歸函數，這些函數是采用自然數的有限元組并返回單個自然數的部分函數（就像上面那樣）。 它們是最小的偏函數類，包括常量函數、后繼函數和投影函數，并且在組合、原始遞歸和 μ 運算符下是封閉的。

等效地，可計算函數可以形式化為可以由理想化計算代理（例如圖靈機或寄存器機）計算的函數。 形式上來說，部分函數 f : N k → N {\displaystyle f:\mathbb {N} {k}\rightarrow \mathbb {N} } 可以計算當且僅當存在計算機程序時 以下屬性：

• 如果定義了 f ( x ) {\displaystyle f(\mathbf {x} )}，則程序將在輸入 x {\displaystyle \mathbf {x} } 時終止，其值為 f ( x ) {\displaystyle f(\mathbf {x} )} 存儲在計算機內存中。
• 如果 f ( x ) {\displaystyle f(\mathbf {x} )} 未定義，則程序永遠不會在輸入 x {\displaystyle \mathbf {x} } 時終止。