Mathematical logic and foundations Definition

Computable function

Builds on Turing machine Natural numbers

Definition

Let $k \ge 1$ and let $f \colon \N^k \rightharpoonup \N$ be a partial function, where $\N$ is the set of natural numbers. Fix an encoding of tuples of natural numbers as words on the input alphabet, for example in unary separated by a marker. The function $f$ is computable, or partial computable, if there is a Turing machine $M$ with the following property for every $\bar x \in \N^k$ .

If $f(\bar x)$ is defined, then $M$ halts on input $\bar x$ with the code of $f(\bar x)$ on its tape.
If $f(\bar x)$ is undefined, then $M$ does not halt on input $\bar x$ .

A total computable function is a computable function defined at every point of $\N^k$ .

Remarks

Example: addition $(x, y) \mapsto x + y$ is computable. With unary codes $1^x 0 1^y$ , a machine that replaces the $0$ by $1$ and erases the last $1$ halts with $1^{x+y}$ on its tape.

Non-example: the function $h(e) = 1$ if the machine with index $e$ halts on input $e$ , and $h(e) = 0$ otherwise, is total but not computable. No machine satisfies clause 1 for $h$ ; see the halting problem.

A partial function is computable if and only if it is partial general recursive. The definition does not depend on the choice of a reasonable encoding or a variant of Turing machines.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`D9AWNH60RM`
URI	`m2://D9AWNH60RM`
Kind	definition
Writing	W0 stub
MSC	03D20, 03D10
Defines	Computable function
Uses	Turing machine, Natural numbers
Changed	2 November 2026

Computable function

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here