2
$\begingroup$

I am interested in economics from the perspective of mathematical physics and complexity theory. An important set of systems in complex systems are systems that are Turing Complete and are cases of universal computation.

This raises the issue of whether a virtual Turing Computer can be constructed in economics. Can accounting be considered a case of a universal computer? I find it interesting that the Ethereum cryptocurrency's support for smart contracts is Turing Complete.

$\endgroup$
  • 4
    $\begingroup$ I'm trying to figure out how this even makes sense. There is no single "programming language" for economics, and the field is awash in approximations and outright guesses. $\endgroup$ – Hot Licks Sep 18 '17 at 1:40
  • 1
    $\begingroup$ @HotLicks because of my interest in mathematical physics, I look at physical systems and ask, what mathematic model is guaranteed to be general enough to completely encompass and bound the physical system in question. By identifying economics as Turning Complete we can immediately dispense with "approximations and outright guesses". $\endgroup$ – Daniel Geisler Sep 18 '17 at 1:51
  • $\begingroup$ There's nothing wrong with mathematics, of course. But you can't even describe the purchase of a soft drink from a pop machine precisely enough to consider the math "complete". $\endgroup$ – Hot Licks Sep 18 '17 at 1:55
  • $\begingroup$ @HotLicks I differ. My mathematical background is in dynamics. The entire Universe in all its glory can mathematically be encoded in an infinite matrix whose state evolves instant to instant by a specified function. Or you could also use cellular automata to ensure that you can model any possible physical process. Mathematical physics allows one to show that mathematical truths have implications in physics like Noether's work in connecting symmetry and conservation laws. tetration.org/IF.pdf $\endgroup$ – Daniel Geisler Sep 18 '17 at 3:41
  • $\begingroup$ @HotLicks At first I was with you, but it seems this is actually an important issue. See answers. $\endgroup$ – luchonacho Sep 18 '17 at 9:48
4
$\begingroup$

According to Vela Velupillai, Orthodox Economic Theory is not Turing Complete, because it is "replete with uncomputabilites". On this 2009's article he states:

Economic theory, at every level and at almost all frontiers – be it microeconomics or macroeconomics, game theory or IO – is now almost irreversibly dominated by computational, numerical and experimental considerations. Curiously, though, none of the frontier emphasis from any one of these three points of view – computational, numerical or experimental – is underpinned by the natural algorithmic mathematics of either computability theory or constructive analysis. In particular, the much vaunted field of computable general equilibrium theory, with explicit claims that it is based on constructive and computable foundations is neither the one, nor the other. Similarly, Newclassical Economics, the dominant strand in Macroeconomics, has as its formal core so-called Recursive Macroeconomic Theory. The dominance of computational and numerical analysis, powerfully underpinned by serious approximation theory, is totally devoid of computable or constructive foundations.

The reasons for this paradoxical lack of interest in computability or constructivity considerations, even while almost the whole of economic theory is almost completely dominated by numerical, computational and experimental considerations, are quite easy to discern: the reliance of every kind of mathematical economics on real analysis for formalization. [...]

Anyone with a modicum of expertise in recursion theory, constructive analysis or even nonstandard analysis in its constructive modes, would find, in any reading from these more algorithmically oriented perspectives, the citadel of economic theory, game theory and IO replete with uncomputabilities, undecidabilities and non-constructivities – even elements of incompleteness.

Section 2 of that paper explores some examples of uncomputability in economic theory.

This author is one of the leading figures in the field called "Computable Economics", which is an attempt to produce Turing Complete economic theory. In 2000 he compiled a book on the subject. There is also a 2009 handbook of Computable Economics. The 2000's book opens with a quote that hints why Game Theory is not Turing Complete:

[T]here 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: 148; emphasis added)

Then, the authors state:

The key word is “effective,” referring to a procedure whose execution is specified in a finite series of instructions, each of which is finite in length and where all the details of the execution are specified exactly, thereby leaving no room for magic, miracles, or other such metaphysical entities. The exact meaning of “effecitivity” is mathematically equivalent, under the Church–Turing thesis, to “computability.”

So, as I understand this, there are some games for which there is no algorithm that could help us "compute" such optimal wining strategy in practice. Hence, Game Theory is uncomputable, ergo Turing incomplete.

Herbert Simon is perhaps the highest profile, relatively mainstream economist contributing toward Computable Economics. Actually, he got both the Nobel Prize in Economics and the ACM Turing Award (regarded as the "nobel prize for computing").

$\endgroup$
  • $\begingroup$ Wonderfull, this is exactly the type of information I was looking for. I consider this question as answered although it will take me a bit of time to read all the relevant research listed here. Once again, my thanks. $\endgroup$ – Daniel Geisler Sep 18 '17 at 13:51
  • $\begingroup$ @DanielGeisler You are welcome. It is a great question! I was not aware of this field or criticism to economics, and I'm looking forward to get deeper into it! $\endgroup$ – luchonacho Sep 18 '17 at 13:53
4
$\begingroup$

I am not a CS guy so this answe may be flawed in many ways. Take it more as a long comment and please give some feedback.

Economists view Ethereum as a pure Arrow-Debreu market economy. In an AD economy you can write fully contingent contracts specifying commodity trades conditional on any future event at any particular date. Therefore, an AD economy is, by definition Turing complete. In that sense, for economists Ethereum is a cool implementation of an ideal but nothing new.

The problem is that, as Arrow himself recognized (but not Debreu!), this model of the economy is not realistic in any way because there are frictions to contracting, undescribable events, unawareness, asymmetric information, uninsurable risks, etc.

At a more fundamental level, economics has another problem that seems to me to relate to the halting problem. if an economic system was decidable, then the agents in the economic model would have to either know the answer or not know the answer. In the former case, there would often be an eternal loop, since the answer to the problem would be part of the problem itself (this is the essence of the Lucas critique). If you assume they do not know the answer then you are imposing a certain rule on their actions that will not be universal and therefore would not allow for Turing completeness on the whole economy.

$\endgroup$
  • $\begingroup$ Do you have a link to a paper relates to the comment "Economists view Ethereum as a pure Arrow-Debreu market economy"? I am interested on it (and could give more support to that statement in the answer too). $\endgroup$ – luchonacho Sep 18 '17 at 9:47
  • 1
    $\begingroup$ I do not have a precise reference but I have heard it from quite a few and it is indeed quite natural. Fernandez-Villaverde has a paper on cryptocurrencies and holds that view. My thoughts on Arrow are also inspired by the words of some of his former students and Paul Milgrom at a conference in Faro, Portugal. Augur argues for very much the same thing (medium.com/@AugurProject/augur-master-plan-42dda65a3e3d) $\endgroup$ – Fato Sep 18 '17 at 10:14
  • $\begingroup$ Do you have any evidence that Debreu was not aware of any limitations of the model in terms of realism? I find that rather hard to believe (and I don't.) $\endgroup$ – Michael Greinecker Sep 18 '17 at 13:43
  • 1
    $\begingroup$ not hard evidence. some of it is here. sss.ias.edu/files/papers/econpaper73.pdf peter hammond said something like 'for arrow, AD was the start. for debreu, the culmination of his work.' $\endgroup$ – Fato Sep 18 '17 at 13:52
  • $\begingroup$ Hm. I agree with what Peter Hammond said, but this is a statement about Debreu's research output, not his views on the realism of the model. I read a lot of Debreu's work and he seems to mostly avoid discussing realism at all. $\endgroup$ – Michael Greinecker Sep 25 '17 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.