### bounded minimization ==>

# minimization

<*logic*>
One of the simple function-building operations of recursive
function
theory. Roughly, if we are given a computable function f(x,y),
then we
posit
another function g which computes the least value of y (a natural
number)
such that f(x,y) = 0. We say that g is created from f by
minimization.
One
way that g might work is to start from 0 and test every natural
number in
order, stopping at the first value which makes f(x,y) = 0.
Also called ' (Greek letter mu).

Bounded minimization

To insure that g is a total function, we create it from f by
bounded
minimization. We pick a bound z and try every value 0...z as the
value of
y;
the first one to make f(x,y) = 0 is returned as the value of g; if
none
makes f(x,y) = 0, then g returns 0. Since g always returns a value,
it is
a
total function; since z is always finite, g is computable.

Unbounded minimization

If f(x,y) never equals 0, then g is undefined; hence g is a
partial,
hence incomputable, function. Think of g running on a computer;
when it
is
unbounded, it will run forever with some inputs. It might test
the values
0,
1, 2... in search of a value for y which will make f(x,y) = 0.
But if
there
is no such y, and if no bound is put on the search, then the search
will
never halt.

[Glossary of First-Order Logic]

<*2001-03-16*>

Try this search on OneLook / Google

**Nearby terms:**
mind « mind-body dichotomy « mind-body problem « minimization » minor premise » minor term » Minsky Marvin