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 ?
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.
The first is the possibility that a particular problem is not effectively computable.
Some Problems in Economics Are Not Effectively Computable
On Effectively Computable Realizations of Choice Functions," Mathematical Social Sciences, 10, 1985a, 43-80.
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.
Lewis (1985a) makes an even stronger assertion in his paper showing that demand correspondences are not effectively computable (or "computationally viable"):
The relevant question is whether equilibria are effectively computable for the games economic agents actually play.
In a later paper, Lewis (1992b), shows a similar failure of Walrasian equilibrium and N-person noncooperative games to be 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.
Rust (1997) examines literature showing that a number of standard economic problems(12) are not effectively computable.

Full browser ?