Range problem

In computability theory, a range problem is a weakened form of a search problem. It consists of two functions f_l and f_u (the lower and upper bounds) and a linear ordering < on the ranges of f₁ and f₂. A Turing machine solves a range problem if, for any x, the machine eventually halts with an output y such that f₁(x) < y < f₂(x).

For example, given any function f with range in R and any g : N → R, the strong range problem StrongRange_g(f) is given by lower bound

$f(x)\cdot\left(1-\frac{1}{1-g(\vert x\vert)}\right)$

and upper bound

$f(x)\cdot\left(1-\frac{1}{1+g(\vert x\vert)}\right)$.

Note that g is passed the length of x, not the value, which need not even be a number.

This article incorporates material from range problem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.