The Computable Approach to Economics

...... there are games in which the player who in theory can always win cannot do so in practice because it is impossible to supply him with effective instructions regarding how he should play in order to win. Rabin, 1957. The above is a statement of the first important result in what I have come to call Computable Economics. The key word in the Rabin quote is effective, meaning a procedure whose execution is specified in a finite series of instructions, each of which is finite in length and all the details of the execution are specified exactly, which, thus, leaves no room for magic, miracles, creative imagination and other such metaphysical entities. The exact meaning of effective is mathematically equivalent, under Church's Thesis to computability. Mathematical logic itself is divided into set theory, proof theory, model theory and recursion theory. The study of computable objects and domains is the subject matter of recursion theory. The formalisms of economic analysis is, in general, based on mathematical foundations relying on set theory or model theory (eg: nonstandard analysis). Thus, when Debreu reminisced, in his Nobel Lecture, on Economic Theory in the Mathematical Mode he was able to note: Especially relevant to my narrative is the fact that the restatement of welfare economics in set-theoretical terms forced a re-examination of several of the primitive concepts of the theory of general economic equilibrium. Debreu, 1984. Computable economics, on the other hand, and as I see it, is about basing economic formalisms on recursion theoretic fundamentals. This means we will have to view economic entities, economic actions and economic institutions as computable objects or algorithms (cf. Scarf, 1989). For the moment this broad definition must suffice. In this paper I will try to draw my picture with a broad brush on a rough canvas with selected examples. The specific, detailed, examples are three: rationality, learning and (arithmetical) games; I give them recursion theoretic content and draw the ensuing implications. These examples, I hope, will create the image I want to convey about the nature and scope of computable economics. The fine details of the drawing and the elaborations of its texture are the subject matter of other writings (cf. Velupillai, 1994,a,b) and the interested reader, that elusive creature, is referred to them for the deeper issues and some of the detailed proofs. The rest of this paper is structured as follows. In 2 there is a brief excursion into general methodological and epistomological issues that have arisen as a result of the new ontology implied by the philosophies underlying recursion theory - incompleteness and undecidability being the prime examples. In addition, I try to give this discussion a potted doctrine historical background in a mildly counterfactual sense. The subsequent sections are a sequence of examples, from standard economic theory. In each example, roughly speaking, the implicit question I pose is the following: what is the effective or computable content of these examples? Or, what is the computational complexity of this operator? And so on. Each example is chosen in such a way that it also enables me to introduce selected fundamental concepts and tools of recursion theory and show their workings in an economic setting.