Computable Function

computation

Definition

Computable Function

A function $f$ is called computable if there is an algorithm that takes any element $x$ from the domain of $f$ as an input and produces the function value $f(x)$ as output.

Note that the domain of $f$ can be made of arbitrary objects that can be encoded as finite strings over a suitable finite alphabet.

Partial vs. Total

Partial Function

Definition

Computable Partial Function

A (potentially partial) function $f:X\to Y$ is called computable if there exists an algorithm $A$ with the following properties:

• $A$ takes any $x\in X$ as input
• If $A$ halts on input $x$, it outputs $f(x)$
• $A$ runs forever on input $x$ iff $f$ is not defined at $x$

Link to original

Total Function

Definition

Computable Total Function

A total function $f:X\to Y$ is called computable if there exists an algorithm $A$ that takes any $x\in X$ as input, halts, and outputs a correct $f(x)$.

Trivially, this is a stricter form of computability than partial functions.

Link to original

Examples

Not every total Boolean function is computable

The statement “For every total function $h:{\mathbb{N}}^2\to \{0,1\}$, there exists a Turing machine that computes $h$” is false.

There are uncountably many such functions, but only countably many Turing machines. Hence most such functions are uncomputable.