計算可能関数
以下の関数は計算可能関数である。
定数関数 f : N→ N, f(n1,...nk) := n
加法 f : N→ N, f(n1,n2) := n1 + n2
素因数分解関数
2つの数の最大公約数(を求めること)は計算可能関数である。
ベズーの等式 - 線形ディオファントス方程式
f と g が計算可能ならば、f + g、f * g、 f ∘ g {\displaystyle f\circ g} (fが単項の場合)、max(f,g)、min(f,g)などといった様々な組合せも計算可能関数となる。
以下の例では、関数を計算するのがどのアルゴリズムなのかが不明でも、関数が計算可能とされる場合があることを示す。
πを計算した十進数列に n 個の連続した '5' が出現するなら f(n) = 1 を返し、そうでなければ f(n) = 0 を返すような関数 f は、計算可能である。(この関数は単に定数 1 を返すか、または、何らかの定数 k について、n < k なら f(n) = 1 を返し、k ≤ n なら f(n) = 0 を返す。