آیا سیستم های اقتصادی می تواند به عنوان دستگاه های محاسبات دیده می شود؟

We briefly discuss ideas about computable economics, and comment on the contributions of A.A. Lewis and K.V. Velupillai. We then sketch the mathematical background for the Tsuji et al. (Tsuji, M., da Costa, N.C.A., Doria, F.A., 1998. The incompleteness of theories of games. Journal of Philosophical Logic 27, 553–564) result on the undecidability and incompleteness of game theory and of the theory of competitive markets, using that result in the concluding sections of the paper to examine the (possible) empirical interpretation of economic and social systems as computing devices.

The central question in this paper arose out of a discussion of one of the authors4 with K.V. Velupillai. Plainly, can we look at economic or social systems as if they were computing devices in some reasonable sense? By a computing device we mean either a Turing machine, an analog device or one of the conjectured extensions of both (see Doria and Costa, 2006) as in the hypercomputation theories. However throughout this paper, when we talk about “computability” or “algorithm” we always mean Turing-machine computability or Turing machine algorithms. That question may be formulated in the realm of computational economics, and computational economics can be seen as a discipline that encompasses three different (and assuredly nonequivalent) ways of looking at economic and social systems: • Can we computationally5 predict the behavior of some (economic, social) phenomenon X? Can we compute quantitative data about X? • Can we formulate in a constructive way the main results from mathematical economics? • Finally, can we look at economic (and social) processes as computing devices? We will deal in this paper with the last question above, which we stress: Can we look at economic and social processes as some sort of computing devices? If we restrict our search about the subject to the last 30 years, we see that several of the main contributions to the area have been made by A.A. Lewis and K.V. Velupillai. Our interest in their work has to do with the emphasis they place on the metamathematical phenomena that bear on mathematical economics; this should help to clarify our main question.6 1.1. Goals of this paper We use the Tsuji et al. (1998) incompleteness theorem for game theory in the light of the results by Lewis and Velupillai in order to try to understand whether it makes sense to interprete actual economic systems and processes as computing devices. As an aside, we discuss the Tsuji et al. result and explain its meaning for a wider audience in the economics community. The central point we wish to stress, a point which is very clear from the work of Lewis and Velupillai, is: once you build your argument within a framework that includes enough arithmetic to develop recursive function theory in it, then you get Gödel incompleteness everywhere, that is, you get undecidable sentences of all sorts, including those that deal with interesting or pressing theoretical questions. For a detailed presentation of the main concepts we require here from computer science see Machtey and Young (1979) and Rogers (1967). For a summary of the main ideas directed to the economics community see Velupillai (2000).

We restate a discussion already made (Costa, Doria and Tsuji 1998, introduction) since it deals with several key points about the previous results: We consider the questions arising from this second point of view; i.e. we show that when we see game theory as a formal axiomatized theory, some unsuspected incompleteness phenomena appear that establish limits to the external epistemological power of the theory of games. It should be stressed that analogous results could be obtained for any mathematized microeconomic theory — here game theory is used for being an archetypal example in economic theory. […][…] In this external epistemological approach the most striking result in the metamathematics of economic models was the proof by Lewis that the (formal) theory of Walrasian models with a computable presentation is an undecidable theory. (A weaker but equally interesting result by Lewis is the proof of the Gödel-incompleteness of the theory of Hamiltonian models.) In a similar vein Prasad demonstrated the existence of a class of countably infinite games for which the problem of finding a Nash equilibrium is algorithmically unsolvable. When faced with the same question in the finite situation, Prasad remarks: “For such games (i.e., with finite numbers of players and strategies) it is easy to describe a computational procedure for finding Nash equilibria. Since the problem is inherently finite, one approach would be to consider exhaustively all possible strategy combinations and to check if any player can gain from unilateral deviation.” (Prasad, 1991). Let us think a bit about that. Prasad argues that we can check for Nash equilibria in finite Nash games since the set of strategies is finite; out of its finiteness we can make a finite list of things that matter in the game and by brute force comparison we end up with the desired equilibria. That approach certainly holds when we look at the problem in an extensional way, that is, when the sets of strategies and utilities are considerd by themselves without the mediation of any formal language. Such is the case in all informal approaches. Yet when we go from the domain of informal mathematics into that of formalized or axiomatized theories, we cease to handle directly our intuitive, almost concrete initial objects. Formalized theories are about strings of symbols that purport to represent our intuitions about concrete objects. When we look at finite games within axiomatic theories, those naive intuitions about their solvability break down. As we have already seen, the Tsuji et al. result has consequences even outside an axiomatic framework since it can be stated as an undecidability result. 4.1. Koppl Recently Koppl (2007, p. 840) stressed a few central ideas in da Costa and Doria (2005): [The authors] reveal just how pervasive noncomputability is. It is surprising to learn just how little we can figure out about the mathematical world even of classical analysis. They cite favorably “Wolfram’s conjecture” that “undecidability exists everywhere, even in trivial physical theories.” They show that even finite games can be undecidable. This almost bizarre result merits attention. In one sense any finite game is trivially decidable. If we have a finite number of players, each of whom has a finite number of strategies, then we can list every strategy combination and its corresponding payoff vector. We can simply run down this finite list and see which entries, if any, are Nash equilibria. Citing Prasad (1991)[…][…] they say “by brute force comparison we end up with the desired equilibria.” So far so good. But this result, they point out, assumes we have a complete list of all strategies and payoffs “without the mediation of any formal language.” Often, however, we have no such list available to us. Instead we describe strategies and payoffs obliquely through formal language. […][…] Thus, finite games that seem so trivially decidable can be described with “complicated expressions, which may be the case when we are dealing with a model …… of some market.” And for some games so described, it is not possible to compute the Nash equilibria […][…] That is precisely the point. 4.2. Algorithmic undecidability and Gödel incompleteness matter for mathematical economics The common ground shared by the work of Lewis, Velupillai, and then Tsuji et. al. can be summed up in a slogan: undecidability and incompleteness do matter for mathematical economics, and they have practical consequences. This is a summary of our views on the matter: • Algorithmic trading. For a market whose players are Turing machines, we have the Lewis and Velupillai undecidability results. But suppose that we restrict our traders to finite automata. It can be shown that even in that case we will have to deal with undecidability and the Gödel incompleteness phenomenon, if we axiomatize our theory within an axiomatic framework large enough to include the required concepts. • Other practical questions. Let us consider here a practical, quite immediate question. One of the perennial controversies in the Brazilian economic debate (for the last 15 years at least; notice that are writing in February 2008)13 has to do with whether the country’s economy has reached some kind of equilibrium, steady-state or not. Of course that debate has ideological and political constraints, and it is never acceptably settled out of the empirical data available, but such a controversy raises the following theoretical question: Given some mathematical model for an arbitrary, real-world, market economy, can we algoritmically decide whether it has reached some equilibrium set of prices? Let us stress the point: we must have some kind of mathematical model for the real-world situation in order to apply the undecidability and incompleteness results described here. Then, if the model is sufficiently complicated, undecidability creeps up. • Are planned economies possible? The results we present here have an immediate consequence for a question of both historical and practical importance: the controversy on economic planning (we mean the Barone, von Mises, Lange and Hayek controversy, the “socialist calculation debate”). For general mathematical models, the matter is algorithmically unsolvable. The central problem of economic planning may be formulated as some kind of allocation problem. Very frequently allocation is to be done on the basis of maximizing (or minimizing) simple functions over finite sets. However trouble begins when the problem of planning is reduced to the problem of determining equilibria in finite noncooperative Nash games, which is formally equivalent to the determination of equilibrium prices in a competitive market, given the conditions spelled out above. (On allocation problems see the next item.) One believed, and hoped (a kind of Laplacian hope), that given the equations defining an economy, some gigantic, superduper computer would always be able to calculate the equilibrium prices, therefore allowing (at least theoretically) the existence of an efficient global policy maker. However the results quoted in this paper disprove that conjecture. • Computation of minimum costs might lead to formally undecidable sentences. If the conjecture stated in da Costa and Doria (in press) and da Costa et al. (2007) holds then the actual computation of minimum costs in allocation problems may turn out to be undecidable even within strong axiomatic frameworks, if the so-called P<NPP<NP hypothesis is proved independent of ZFC or even of stronger theories.