Computable function

In computability theory computable functions or Turing computable functions are the basic objects of study. They make our intuitive notion of algorithm precise and according to the Church-Turing thesis they are exactly the functions that can be calculated using a mechanic calculation device.

Before the precise definition of computable function mathematicians often used the informal term effectively computable.

Definition

Generally a computable function is a partial function

The class of computable functions is equivalent to the class of functions defined by

• recursive functions
• lambda calculus
• Markov algorithms

Alternatively they can be defined as those algorithms that can be calculated by

• Turing machines
• Post systems
• register machines

Notes

Sometimes, for reasons of clarity, we write a computable function as

We can easily encode g into a new function

using a pairing function.

Examples

• constant function f : N^k→ N, f(n₁,...n_k) := n
• addition f : N²→ N, f(n₁,n₂) := n₁ + n₂
• greatest common divisor
• Bézout's identity, a linear Diophantine equation

Properties

• The set of computable functions is countable.
• Given two computable functions f and g then f+g, fg and fog are computable functions.