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 ?
Recursive" means effectively computable, may be computed by a (Turing) machine.
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.
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.
If insistence that models embody computational routines describing what firms actually must do to carry out their tasks leads to problems whose solutions are not effectively computable or that are intractably complex, it should be a signal that these limits must be respected in our efforts to model economic behavior realistically.
Rust (1997) examines literature showing that a number of standard economic problems(12) 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.
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 ?