Computable function - Definition and Overview

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

<math>f:\subseteq \mathbb{N} \to \mathbb{N}<math>

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

<math>g:\subseteq \mathbb{N}^k \to \mathbb{N}<math>

We can easily encode g into a new function

<math>f:\subseteq \mathbb{N} \to \mathbb{N}<math>

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.