Definition:Minimization

Definition

Function

Let $f: \N^{k+1} \to \N$ be a total function.

Let $n = \left({n_1, n_2, \ldots, n_k}\right) \in \N^k$ be fixed.

Then the minimization operation on $f$ is written as:

$\mu y \left({f \left({n, y}\right) = 0}\right)$

and is specified as follows:

$\mu y \left({f \left({n, y}\right) = 0}\right) = \begin{cases} \text{the smallest } y \in \N \text{ such that } f \left({n, y}\right) = 0 & : \text{if there exists such a } y \\ \text{undefined} & : \text{otherwise} \end{cases}$

Note that if $f: \N^{k+1} \to \N$ is a total function, and $g: \N^k \to \N$ is given by:

$g \left({n}\right) = \mu y \left({f \left({n, y}\right) = 0}\right)$

then, in general, $g$ will be a partial function.

Partial Function

Let $f: \N^{k+1} \to \N$ be a partial function.

Let $n = \left({n_1, n_2, \ldots, n_k}\right) \in \N^k$ be fixed.

Then the minimization operation on $f$ is written as:

$\mu y \left({f \left({n, y}\right) = 0}\right)$

and is specified as follows:

$\mu y \left({f \left({n, y}\right) = 0}\right) = \begin{cases} z & : f \left({n, z}\right) = 0 \text { and } f \left({n, y}\right) \text{ defined and } \forall y: 0 \le y < z: f \left({n, y}\right) \ne 0 \\ \text{undefined} & : \text{otherwise} \end{cases}$

The partial function:

$g \left({n}\right) \approx \mu y \left({f \left({n, y}\right) = 0}\right)$

obtained in this way (see Partial Function Equality) is said to be obtained from $f$ by minimization.

Note the following:

It is not enough for there to exist $z$ such that $f \left({n, z}\right) = 0$.

We need to insist that $f \left({n, y}\right)$ is actually defined for all $y$ less than $z$.

Otherwise, if we were to try and find $z$ by the recursive technique of trying all $z$ from $0$ up, we would never actually get up as far as $z$ because the undefined value of $f$ for some $y$ getting in the way.

In the context of URM programs, this is significant, as an undefined output from a function is determined by a non-terminating program.

Relation

Let $\mathcal R \left({n_1, n_2, \ldots, n_k, y}\right) $ be a $k+1$-ary relation on $\N^{k+1}$.

Let $n = \left({n_1, n_2, \ldots, n_k}\right) \in \N^k$ be fixed.

Then the minimization operation on $\mathcal R$ is written as:

$\mu y \mathcal R\left({n, y}\right)$

and is specified as follows:

$\mu y \mathcal R \left({n, y}\right) = \begin{cases} \text{the smallest } y \in \N \text{ for which } \mathcal R \left({n, y}\right) \text{ holds} & : \text{if there exists such a } y \\ \text{undefined} & : \text{otherwise} \end{cases}$

We can consider the definition for a function to be a special case of this.

Compare the bounded minimization operation which is always a total function.