|
|
|
|
|
Range ProblemIn computability theory, a range problem is a weakened form of a search problem. It consists of two functions fl and fu (the lower and upper bounds) and a linear ordering < on the ranges of f1 and f2. A Turing machine solves a range problem if, for any x, the machine eventually halts with an output y such that f1(x) < y < f2(x). For example, given any function f with range in R and any g : N → R, the strong range problem StrongRangeg(f) is given by lower bound -
and upper bound - .
Note that g is passed the length of x, not the value, which need not even be a number.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|