Computable Function - Examples

Examples

The following functions are computable:

• Each function with a finite domain; e.g., any finite sequence of natural numbers.

• Each constant function f : Nk → N, f(n₁,...n_k) := n.

• Addition f : N2 → N, f(n₁,n₂) := n₁ + n₂

• The function which gives the list of prime factors of a number.

• The greatest common divisor of two numbers is a computable function.

• Bézout's identity, a linear Diophantine equation

If f and g are computable, then so are: f + g, f * g, if f is unary, max(f,g), min(f,g), arg max{y ≤ f(x)} and many more combinations.

The following examples illustrate that a function may be computable though it is not known which algorithm computes it.

• The function f such that f(n) = 1 if there is a sequence of at least n consecutive fives in the decimal expansion of π, and f(n) = 0 otherwise, is computable. (The function f is either the constant 1 function, which is computable, or else there is a k such that f(n) = 1 if n < k and f(n) = 0 if n ≥ k. Every such function is computable. It is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, so we don't know which of those functions is f. Nevertheless, we know that the function f must be computable.)

• Each finite segment of an uncomputable sequence of natural numbers (such as the Busy Beaver function Σ) is computable. E.g., for each natural number n, there exists an algorithm that computes the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(n) — in contrast to the fact that there is no algorithm that computes the entire Σ-sequence, i.e. Σ(n) for all n. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarly, for any given value of n, such a trivial algorithm exists (even though it may never be known or produced by anyone) to compute Σ(0), Σ(1), Σ(2), ..., Σ(n).