Range problem

Range problem

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 "f"1 and "f"2. A Turing machine solves a range problem if, for any "x", the machine eventually halts with an output "y" such that "f"1("x") < "y" < "f"2("x").

For example, given any function "f" with range in R and any "g" : N &rarr; R, the strong range problem StrongRange"g"("f") is given by lower bound

:f(x)cdotleft(1-frac{1}{1-g(vert xvert)} ight)

and upper bound

:f(x)cdotleft(1-frac{1}{1+g(vert xvert)} ight).

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Range imaging — is the name for a collection of techniques which are used to produce a 2D image showing the distance to points in a scene from a specific point, normally associated with some type of sensor device.The resulting image, the range image , has pixel… …   Wikipedia

  • Range encoding — is a data compression method defined by G N N Martin in his 1979 paper on Range encoding: an algorithm for removing redundancy from a digitized message [http://www.compressconsult.com/rangecoder/#download Range Encoder ] ] . Range encoding is… …   Wikipedia

  • Range voting — (also called ratings summation, average voting, cardinal ratings, score voting, 0–99 voting, or the score system or point system) is a voting system for one seat elections under which voters score each candidate, the scores are added up, and the… …   Wikipedia

  • Problem-oriented policing — (POP), coined by University of Wisconsin Madison professor Herman Goldstein, is a policing strategy that involves the identification and analysis of specific crime and disorder problems, in order to develop effective response strategies in… …   Wikipedia

  • range — n 1 *habitat, biotype, station 2 Range, gamut, reach, radius, compass, sweep, scope, orbit, horizon, ken, purview can denote the extent that lies within the powers of something to cover, grasp, control, or traverse. Range is the general term… …   New Dictionary of Synonyms

  • Range searching — The range searching problems and data structures are a fundamental topic of computational geometry. The range searching problem finds applications not only in areas that deal with processing geometrical data (like geographical information systems …   Wikipedia

  • Problem of evil — Part of a series on God General conceptions …   Wikipedia

  • Range segmentation — A range image contains 3D information about a scene including the depth of each pixel. Segmenting a range image is the task of dividing the image into regions so that all the points of the same surface belong to the same region, there is no… …   Wikipedia

  • Problem play — The problem play is a form of drama that emerged during the 19th century as part of the wider movement of realism in the arts. It deals with contentious social issues through debates between the characters on stage, who typically represent… …   Wikipedia

  • Problem of Apollonius — In Euclidean plane geometry, Apollonius problem is to construct circles that are tangent to three given circles in a plane (Figure 1); two circles are tangent if they touch at a single point. Apollonius of Perga (ca. 262 BC ndash; ca. 190 BC)… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”