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