10.2 Partial vs Total Functions

A computable process may fail to produce an output for some inputs, not because the input is malformed, but because the process never halts. This distinction leads to two kinds of functions: total functions, which are defined on every input, and partial functions, which may be undefined on some inputs.

In computability theory, partial functions are essential because algorithms are allowed to run forever. A computation that never halts produces no output, and this behavior must be represented mathematically.

Total Functions

A total function from $\mathbb{N}^n$ to $\mathbb{N}$ assigns an output to every possible input.

Definition 10.28 (Total Function)

An $n$ ary total function is a function:

f : \mathbb{N}^n \to \mathbb{N}

such that for every input:

(x_1,\dots,x_n)\in \mathbb{N}^n

there exists a value:

f(x_1,\dots,x_n)\in \mathbb{N}.

Thus a total function is defined everywhere on its domain.

Example 10.29

The addition function:

\operatorname{add}(x,y)=x+y

is total, because every pair of natural numbers has a sum.

The multiplication function:

\operatorname{mul}(x,y)=xy

is total, because every pair of natural numbers has a product.

The successor function:

S(x)=x+1

is total, because every natural number has a successor.

Partial Functions

A partial function may be undefined for some inputs. We write:

f : \mathbb{N}^n \rightharpoonup \mathbb{N}

to indicate that $f$ is a partial function.

The arrow $\rightharpoonup$ means that not every input is required to have an output.

Definition 10.30 (Partial Function)

An $n$ ary partial function from $\mathbb{N}^n$ to $\mathbb{N}$ is a rule that assigns a value:

f(x_1,\dots,x_n)\in \mathbb{N}

to some inputs:

(x_1,\dots,x_n)\in \mathbb{N}^n

and assigns no value to the remaining inputs.

The set of inputs on which $f$ is defined is called the domain of definition of $f$ and is denoted:

\operatorname{dom}(f).

Thus:

\operatorname{dom}(f) = \{(x_1,\dots,x_n)\in \mathbb{N}^n : f(x_1,\dots,x_n) \text{ is defined}\}.

If an input is not in $\operatorname{dom}(f)$ , then $f$ is undefined on that input.

Example 10.31

Define:

f(x)= \begin{cases} y & \text{if } x=2y \text{ for some } y\in\mathbb{N}, \\ \text{undefined} & \text{otherwise}. \end{cases}

This partial function is defined exactly on even natural numbers.

Its domain is:

\operatorname{dom}(f)=\{0,2,4,6,\dots\}.

For example:

f(8)=4,

but:

f(7)

is undefined.

Undefined Values and Nontermination

In computability theory, an undefined value usually represents nontermination.

If an algorithm computes a partial function $f$ , then:

f(x)=y

means that the algorithm halts on input $x$ and outputs $y$ .

By contrast:

f(x) \text{ is undefined}

means that the algorithm does not halt on input $x$ .

This interpretation is important. A partial function does not return a special error value. It returns no value at all.

Notation for Definedness

We write:

f(x)\downarrow

to mean that $f(x)$ is defined.

We write:

f(x)\uparrow

to mean that $f(x)$ is undefined.

For an $n$ ary function:

f(x_1,\dots,x_n)\downarrow

means that the computation halts with an output, while:

f(x_1,\dots,x_n)\uparrow

means that the computation does not halt.

Definition 10.32 (Equality of Partial Functions)

Let:

f,g : \mathbb{N}^n \rightharpoonup \mathbb{N}

be partial functions. We say that $f$ and $g$ are equal if they have the same domain of definition and agree on every input in that domain.

Equivalently:

f=g

if and only if for every input $\vec{x}\in\mathbb{N}^n$ :

if $f(\vec{x})\downarrow$ , then $g(\vec{x})\downarrow$ and $f(\vec{x})=g(\vec{x})$ ,

and if $g(\vec{x})\downarrow$ , then $f(\vec{x})\downarrow$ and $f(\vec{x})=g(\vec{x})$ .

This definition is stricter than merely saying that the functions agree where both are defined, because equality also requires the same undefined inputs.

Example 10.33

Let:

f(x)= \begin{cases} 0 & \text{if } x=0, \\ \text{undefined} & \text{otherwise}, \end{cases}

and:

g(x)=0

for every $x\in\mathbb{N}$ .

Then $f$ and $g$ agree at $0$ , but they are not equal as partial functions because:

f(1)\uparrow

while:

g(1)\downarrow.

Computable Partial Functions

A partial function is computable if there is an algorithm that produces the correct output whenever the function is defined and runs forever whenever the function is undefined.

Definition 10.34 (Partial Computable Function)

A partial function:

f : \mathbb{N}^n \rightharpoonup \mathbb{N}

is partial computable if there exists an algorithm such that, for every input $\vec{x}$ :

if $f(\vec{x})=y$ , then the algorithm halts on input $\vec{x}$ and outputs $y$ ,

and if $f(\vec{x})$ is undefined, then the algorithm does not halt on input $\vec{x}$ .

In recursive function theory, these are the partial recursive functions.

Total Computable Functions

A total computable function is a computable function that halts on every input.

Definition 10.35 (Total Computable Function)

A function:

f : \mathbb{N}^n \to \mathbb{N}

is total computable if there exists an algorithm that, for every input:

\vec{x}\in\mathbb{N}^n,

halts and outputs:

f(\vec{x}).

In recursive function theory, these are also called total recursive functions or general recursive functions.

Lemma 10.36

Every total computable function is a partial computable function.

Proof

Let:

f : \mathbb{N}^n \to \mathbb{N}

be total computable. By definition, there is an algorithm that halts on every input $\vec{x}$ and outputs $f(\vec{x})$ .

Since a total function is defined on all inputs, it may also be regarded as a partial function whose domain of definition is all of $\mathbb{N}^n$ .

The same algorithm witnesses that $f$ is partial computable, because for every input on which $f$ is defined, which is every input, the algorithm halts and returns the correct value. There are no undefined inputs to check.

Thus every total computable function is partial computable.

Lemma 10.37

Not every partial computable function is total.

Proof

Consider the partial function:

f(x)= \begin{cases} 0 & \text{if } x=0, \\ \text{undefined} & \text{if } x>0. \end{cases}

This function is partial computable. An algorithm computing it proceeds as follows: on input $x$ , check whether $x=0$ . If $x=0$ , halt and output $0$ . If $x>0$ , enter an infinite loop.

The algorithm correctly halts and outputs $0$ when $x=0$ , and it does not halt when $x>0$ .

However, $f$ is not total, because $f(1)$ is undefined.

Therefore some partial computable functions are not total.

Domains of Partial Computable Functions

The domain of a partial computable function is the set of inputs on which the corresponding computation halts.

If:

f : \mathbb{N}^n \rightharpoonup \mathbb{N}

is partial computable, then:

\operatorname{dom}(f)

is the set:

\{\vec{x}\in\mathbb{N}^n : f(\vec{x})\downarrow\}.

Such sets are called recursively enumerable or computably enumerable. They are exactly the sets whose members can be recognized by a computation that halts on members and may run forever on nonmembers.

Definition 10.38 (Semidecision)

A set:

A\subseteq\mathbb{N}

is semidecidable if there is an algorithm such that:

if $x\in A$ , then the algorithm halts on input $x$ ,

and if $x\notin A$ , then the algorithm does not halt on input $x$ .

A semidecision procedure confirms membership but may never confirm nonmembership.

Example 10.39

Let $A$ be the set:

A=\{x\in\mathbb{N} : x \text{ is even}\}.

This set is decidable, hence semidecidable, because there is an algorithm that checks whether $x$ is divisible by $2$ and halts in all cases.

A more interesting semidecidable set arises from a search problem. Suppose:

A=\{x\in\mathbb{N} : \exists y \; R(x,y)\},

where $R(x,y)$ is decidable.

Then $A$ is semidecidable. On input $x$ , search through:

y=0,1,2,\dots

and check whether $R(x,y)$ holds. If a witness is found, halt. If no witness exists, the search continues forever.

Definition 10.40 (Decision)

A set:

A\subseteq\mathbb{N}

is decidable if there is an algorithm that halts on every input $x$ and correctly determines whether:

x\in A.

Equivalently, the characteristic function:

\chi_A(x)= \begin{cases} 1 & \text{if } x\in A, \\ 0 & \text{if } x\notin A \end{cases}

is total computable.

Lemma 10.41

Every decidable set is semidecidable.

Proof

Let $A$ be decidable. Then there is an algorithm that halts on every input $x$ and determines whether $x\in A$ .

To semidecide $A$ , run this decision algorithm. If it says that $x\in A$ , halt. If it says that $x\notin A$ , enter an infinite loop.

This new algorithm halts exactly on the members of $A$ , so $A$ is semidecidable.

Lemma 10.42

A set $A\subseteq\mathbb{N}$ is decidable if and only if both $A$ and its complement:

\mathbb{N}\setminus A

are semidecidable.

Proof

First suppose that $A$ is decidable. Then $A$ is semidecidable by Lemma 10.41. Its complement is also decidable, because the decision procedure for $A$ can be used and the answer can be reversed. Therefore the complement is semidecidable.

Conversely, suppose that both $A$ and $\mathbb{N}\setminus A$ are semidecidable. Let $M_1$ be a semidecision procedure for $A$ , and let $M_0$ be a semidecision procedure for $\mathbb{N}\setminus A$ .

On input $x$ , run $M_1$ and $M_0$ in parallel. This can be done by alternating one computation step of $M_1$ with one computation step of $M_0$ .

Since every natural number either belongs to $A$ or belongs to its complement, one of these two procedures must eventually halt. If $M_1$ halts first, accept that $x\in A$ . If $M_0$ halts first, reject and conclude that $x\notin A$ .

Thus there is a halting decision procedure for $A$ , so $A$ is decidable.

Partiality from Minimization

The minimization operator naturally produces partial functions because the required witness may fail to exist.

Suppose:

f(x,y)

is a total computable function, and define:

g(x)=\mu y [f(x,y)=0].

Then $g(x)$ is defined exactly when there exists some $y$ such that:

f(x,y)=0.

If such a $y$ exists, the computation searches:

y=0,1,2,\dots

until it finds the least witness. If no such $y$ exists, the search continues forever.

Example 10.43

Let:

f(x,y)= \begin{cases} 0 & \text{if } y^2=x, \\ 1 & \text{otherwise}. \end{cases}

Then:

g(x)=\mu y [f(x,y)=0]

returns the least square root of $x$ when $x$ is a perfect square, and is undefined when $x$ is not a perfect square.

For example:

g(9)=3,

but:

g(10)\uparrow.

Total Extensions

A partial function may sometimes be extended to a total function by assigning arbitrary values to the inputs where it is undefined, but such an extension may lose the computational meaning of the original function.

Definition 10.44 (Total Extension)

Let:

f : \mathbb{N}^n \rightharpoonup \mathbb{N}

be a partial function. A total function:

g : \mathbb{N}^n \to \mathbb{N}

is a total extension of $f$ if:

g(\vec{x})=f(\vec{x})

for every:

\vec{x}\in\operatorname{dom}(f).

The values of $g$ outside $\operatorname{dom}(f)$ are not constrained.

Example 10.45

Let:

f(x)= \begin{cases} x+1 & \text{if } x \text{ is even}, \\ \text{undefined} & \text{if } x \text{ is odd}. \end{cases}

One total extension is:

g(x)= \begin{cases} x+1 & \text{if } x \text{ is even}, \\ 0 & \text{if } x \text{ is odd}. \end{cases}

This total function agrees with $f$ wherever $f$ is defined.

Lemma 10.46

A partial computable function need not have a computable total extension.

Proof

Let $K$ be a semidecidable set that is not decidable, such as the halting set introduced later in the chapter. Since $K$ is semidecidable, there is a partial computable function $f$ such that:

f(x)=0

if:

x\in K,

and:

f(x)\uparrow

if:

x\notin K.

Suppose $f$ had a computable total extension $g$ . Since $g$ extends $f$ , we would have:

g(x)=0

for every $x\in K$ .

This alone does not necessarily decide $K$ , because $g(x)$ may also equal $0$ outside $K$ . To obtain a sharper example, define a partial computable function:

h(x)= \begin{cases} 0 & \text{if } x\in K, \\ 1 & \text{if } x\notin K, \end{cases}

with domain all of $\mathbb{N}$ would already be a total decision function, which cannot exist when $K$ is undecidable.

Therefore the general claim must be stated carefully: some partial computable functions have computable total extensions, while others cannot be extended computably in a way that preserves additional intended information about undefinedness. Undefinedness itself is not a value that a total computable extension can record directly.

Computation Traces

A useful way to understand partiality is to view a computation as a sequence of finite stages.

At each stage, the computation has produced only finite information. If the computation eventually reaches a halting state, it produces an output. If it never reaches such a state, no output is produced.

Thus:

f(x)\downarrow

means that there exists a finite computation trace ending in an output.

And:

f(x)\uparrow

means that no finite halting trace exists.

This finite trace viewpoint is central in later proofs about the halting problem and recursively enumerable sets.

Totality as a Global Property

For a partial computable function:

f : \mathbb{N}^n \rightharpoonup \mathbb{N},

the statement that $f$ is total means:

\forall \vec{x}\in\mathbb{N}^n,\; f(\vec{x})\downarrow.

This is a global property of the computation. It requires knowing that every possible input eventually halts.

In many cases, verifying totality is difficult or impossible by algorithmic means. This fact is one of the main sources of undecidability phenomena in computability theory.