出典:Wikipedia
出典:『Wikipedia』 (2009/02/19 17:47 UTC 版)
In 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).