computable function

(redirected from Effectively computable)

computable function

[kəm¦pyüd·ə·bəl ′fəŋk·shən]
(mathematics)
A function whose value can be calculated by some Turing machine in a finite number of steps. Also known as effectively computable function.
References in periodicals archive ?
(3.) "Recursive" means effectively computable, may be computed by a (Turing) machine.
Is entropy effectively computable? Remark, see http://www.math.sunysb.edu/~jack/compent.pdf, 2002.
The number of roads and the number of maps is in fact rather large, and the navigational problem-space can be very complicated; however, the situation is so well defined that we can express it in terms of effectively computable procedures and reduce it to matters of syntax.
The first is the possibility that a particular problem is not effectively computable. If a problem falls into this class, there is no algorithm at all that can solve it within the mathematical system expressing the model.
Some Problems in Economics Are Not Effectively Computable
All of the models of effective computability that have been proposed to date have given rise to the same class of effectively computable functions.
As the notion of effective computability was being developed, the shattering discoveries were made that there are functions and numbers that are not effectively computable, as well as mathematical problems that are undecidable.
Rust (1997) examines literature showing that a number of standard economic problems(12) are not effectively computable. For example, Rabin (1957) showed that there are games whose equilibrium strategies are not effectively computable, and a similar result was established by Binmore (1987).
It isn't clear whether these results [of Rabin and Binmore] have anything to say about the narrower and more relevant issue of whether rational behavior is possible in practical contexts since they rely on nonconstructive arguments to establish the existence of games whose equilibria are not effectively computable. The relevant question is whether equilibria are effectively computable for the games economic agents actually play.
Lewis (1985a) makes an even stronger assertion in his paper showing that demand correspondences are not effectively computable (or "computationally viable"):
In a later paper, Lewis (1992b), shows a similar failure of Walrasian equilibrium and N-person noncooperative games to be effectively computable. These papers are only the tip of the iceberg; Velupillai (1997) in "an attempt .
Problems that are not effectively computable are, as far as we know, beyond the reach of any physical device or human organization to solve, regardless of the resources available.

Full browser ?