Mirowski's capacity to stimulate interesting debates is well known. And equally recognized is his capacity to see through a discipline, like that of economics, with the freshness of one who can spot unseen connections and ideas. Here Mirowski makes a step forward by presenting a neologism, that of the Markomata, with the claim that it can unify and help to further the research efforts of different researchers (whose research is described in Section 2) by providing a new tool for the understanding of the functions of markets.
One might agree or disagree with the way in which Mirowski characterizes research of the orthodoxy as well as research of the academic groups and researchers, but his research plan and his methodological suggestion is clear: if one characterizes markets as devices computing something, it is natural that one theorizes about them as if they were computing mechanisms (i.e. digital automata) from the very beginning.
Let's therefore consider this point in more detail. The mathematical theory of automata is embraced by what is known as the (Meta)mathematical theory of computability (also classical recursion theory). Inside computability different abstract notions of computational mechanisms are studied, and extremely important theorems are used and derived in order to understand what it is that it is computable and how. There is a general consensus that one of the most powerful automata, if not the most powerful automatan, is the Turing machine. And here the notion of “most powerful” has to be understood in the precise terms (developed inside computability) of computational capacity, that is, Church–Turing thesis: anything which is computable is computable by a Turing machine. Here the concept of universal Turing machine, which is able to simulate any other computational device, is also extremely useful. But this does not imply that the Turing machine is the only computing mechanism capable of computational universality.
One would expect Mirowski to embrace computability theory and to use the results developed there for his construction (and analysis) of markets. These results, just to mention a few, are that of the Halting Problem, degrees of solvability, undecidability, Gödel consistency and incompleteness theorems.
Moreover one would expect Mirowski to refer to the existing literature on the applications of “the abstract theory of computation” to economics, where computability theory and Turing machines equivalents are used at full power in the analysis of theoretical economic problems. The surprise is that Mirowski, not only disregards the contribution of those who have applied Turing machine equivalents to simulate computational processes, but goes further by restricting the Markomata to the nondeterministic finite automata.1 But a finite automaton is a passive device with a finite short-term memory and the only way to record any information is by changing its state, while a Turing machine is a more complex device equipped with long-term memory and with, most importantly, the ability to interact with the outer world through the tape.2
In short, finite automata perform trivial computations by changing their internal state, which are pre-defined (i.e. already computed), while a Universal Turing machine can perform, by transforming the symbols written on the tape(s), any computation that any other device can. This makes a hell of a difference!
Mirowski insists in rejecting the use of a Turing machine using different arguments. On page 24 Mirowski writes: “…the theory of Turing machines ignores limitations of space and time in the process of calculation, whereas the theory of automata immediately takes them into account”. What Mirowski might have in mind is the fact that a Turing machine is in principle equipped with a tape that can be enlarged, but this is not to say that the tape is infinite (one assumes it is possible to glue more tape at either end, but only if needed, Odifreddi, p. 46). And certainly a Turing machine computation takes place not at infinite speed. The most basic Turing machine is a set of simple instructions to be performed by a mechanism, originally a human being. It is a very limited machine designed precisely to take into account limitations of space and time. It uses a finite alphabet, it has a finite number of states, and the tape can sequentially shift only one step to the right or one step to the left. How more limited can a mechanism be? Regardless of all these limitations a universal Turing machine can simulate, when fed with the proper input tape, any other computing device. Therefore, how can we make any sense of the idea expressed by Mirowski, that “the theory of (finite) automata takes limitations of space and time immediately into account”? (While the Turing machines should not?) This can only mean that the Markomata is designed from the outset to perform trivial computations where no surprises would emerge and certainly no evolution could take place (on this point see also below). It is equivalent to assuming that a market can be described by a simple finite mapping from given quantities to given prices.
Mirowski goes even further by devoting a full section (4.4.3) to assert that “No markomata possesses the power of a Turing machine”. Here Mirowski asserts that “no extant market appears to possess the analogous capacity of an infinite working memory, then it follows directly that no markomata possesses the computational capacity of a Turing machine”.
Here some comments are appropriate. There exist an infinite number of finite states Turing machines as well as an infinite number of finite automata. If we agree that the market ‘computes’ something it follows that we know (following the Church–Turing thesis) that there exist Turing machines that can ‘simulate’ that computation (and hence deliver associated to the same input the same output). Moreover, and most importantly, we know that the Turing machines that perform the ‘simulation’ must have done it with limited memory, space and time. This is so because a halted Turing machine, by construction, cannot have used unbounded space, time and memory.
On the contrary, we cannot be sure that a lower level automaton (with respect to Turing machines equivalents, following Chomsky's hierarchy) would be able to simulate the computations of any market. One has to postulate (restrict) the computational capacity to that of finite automata. And this is what Mirowski seems to be doing.
Mirowski argues further that markomata cannot be some Turing machines because “…if some markomata did possess the computational capacity of a Turing machine, it would be capable of simulating the operation of any other market, and the way would be open to the collapse of the diversity ecology of markomata to a uniform homogeneity of market form. Since we have never witnessed such a homogeneous economy in economic history, and do not observe it now (even with the innovation of computer-assisted smart markets), we deduce that no functioning markomata has ever attained the power of a Turing machine”.
Here by Turing machine Mirowski must mean ‘universal’ Turing machine. This is a very peculiar argument. To postulate that markets are properly simulated by finite automata is arguable, but logically acceptable, but to claim that this postulate is justified by the fact that a computational device of the computational capacity of a Turing machine ‘would be capable of simulating the operation of any other market’ is difficult to understand.
Now, according to the Church–Turing thesis, for any device computing something there exists a Turing machine simulating that specific computational device, and hence as long as the market ‘computes’ something, a Turing machine performing the same computation exists. But what does this mean? It means that this to-be-simulated computational device has to be encoded in a proper way into the tape, which has to be fed as an input of the Turing machine or of the universal Turing machine. Quite trivially, for example, there exists a Turing machine that performs the addition of two natural numbers (written on a tape) and the universal Turing machine would be fed with a tape that would have enough information for the Turing machine to simulate the Turing machine that performs the addition. Let's consider a simple sum 3 + 2 = 5 (see Davis, 1958(1973), pp. 11–13). The addition Turing machine will be fed with a proper encoding of 3 and 2 and would halt, with output 5. The Universal Turing machine would be fed with the encoding of the Turing machine performing the summation and a proper encoding of 3 and 2, but would still halt delivering 5. The beauty of the Universal Turing machine lays with the fact that the tape fed to the machine contains information on the program performing a certain task as well as the encoding of the inputs. But a description of the program has to be provided.
Analogously, once a precise theory of the markets’ data generating processes is given one can construct Turing machines replicating these processes. But the fact that there exists a universal Turing machine that simulates the Turing machines that simulate the markets’ data generating processes can be useful, but it is not essential. Therefore it cannot be the case that “if some markomata did possess the computational capacity of a Turing machine, it would be capable of simulating the operation of any other market, and the way would be open to the collapse of the diversity ecology of markomata to a uniform homogeneity of market form.”
Mirowski's postulate that Markomata can be simulated by finite automata has also the consequence of limiting the number of conceptual tools he can use. In my view Mirowski cannot apply the concepts of the halting problem and of von Neumann's self-replicating mechanisms to his low complexity markomata: he needs Turing machines equivalents.
Mirowski, in his Section 4.3 about the Teleology of Markomata uses the undecidability of the halting problem to doubt about the existence of the ‘law of supply and demand’ at the aggregative level. While it is known that there exists a halting problem for Turing machines, the equivalent for finite automata does not exist.3 Therefore, in order to make sense of the agreeable statement that “when a markomata fails it appears unable to halt” one needs to consider a non-halting markomata as if it were a Turing machine equivalent. In my view either Mirowski drops his postulate that markomata are equivalent to finite automata, or he must not associate the undecidability of the halting problem to markomata.
Another area where computational universality requiring Turing machine equivalence seems to be essential is in evolution. John von Neumann's work on the formalization of the ‘notion of evolution where abstract logical entities, in the process of replicating copies of themselves, might be able to produce offspring of greater computational capacity than they themselves possessed’ required the concept of computational universality. It seems that there is a great deal of consensus that for evolution to take place, one needs as a necessary condition the existence of a ‘universal constructor’ able, at least, to simulate the computations of a universal Turing machine: anything of lower complexity will not do. As known, a model for this universal constructor is that of the cellular automata (on this point see Poundstone, 1985 and Odifreddi, 1989, pp. 172–3;Arbib, 1987, Chapter 7, ‘Automata that Construct as well as Compute’; von Neumann, 1966).
To conclude and summarize, the concept of markomata is obviously a very interesting one, and so are the suggestions and considerations made by Mirowski. As I have argued above, it is the unnecessary Mirowski postulate that markomata can be simulated at most by finite automata equivalents, which could be problematic. In my view, Mirowski's theoretical construction and/or research agenda needs Turing machine equivalents. This is clearly so for the cases of the undecidability of the halting problem and of the evolving self-reproducing markomata.
References
Arbib, 1987 M. Arbib, Brains, Machines, and Mathematics, Springer-Verlag, New York (1987).
Davis, 1958 Davis, M., 1958(1982). Computability and Unsolvability. Dover, New York.
Davis and Weyuker, 1983 M. Davis and E. Weyuker, Computability, Complexity, and Languages (1st ed.), Academic Press, New York (1983).
Hopcroft and Ullman, 1979 J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesly Publishing Company, USA (1979).
Odifreddi, 1989 P. Odifreddi, Classical Recursion Theory, Elsevier, Amsterdam (1989).
Poundstone, 1985 W. Poundstone, The Recursive Universe, William Morrow and Company, New York (1985).
von Neumann, 1966 J. von Neumann, Theory of Self-Reproducing Automata, University of Illinois Press, Urbana/Chicago (1966).
1 Given that the deterministic finite automata can simulate non-deterministic finite automata (see Hopcroft and Ullman, 1979, p. 22) I will not distinguish between them and refer simply to finite automata.
2 Odifreddi (1989, p.52–53) compare a Turing machine and a finite automaton by writing: “A finite automaton is basically a passive device, producing only output from an input by a series of internal changes. Moreover, it has only a finite short-term memory, since the only way it is able to record is by changing its state. A Turing machine is a more complex device, and it may be seen as a finite automaton supplied with an external, potentially infinite long-term memory, and with the ability to of interacting with the outer world (the tape) in a dynamical, active way (through the head)”. Davis and Weyuker (1983, p. 149–150) formulate things a little differently, but the essence is the same, “The point of view of computability theory is exemplified in the behaviour of a Turing machine in which a read-write head moves back and forth on an infinite tape, with no preset limit on the number of steps required to reach termination. At the opposite pole one can imagine a device that moves from left to right on a finite input tape …the so-called finite automata. …a finite automaton can be thought of as a very limited computing device which, after reading a string of symbols on the input tape, either accepts the input or rejects it, depending upon the state the machine is in when it has finished reading the tape”.
3 The theorem of computational theory Mirowski refers to holds for programs written in the language L(α), that is a language whose programs can be simulated by Turing machines, but not all of these programs can be simulated by finite automata. In fact, Davis and Weyuker show that programs written in the programming language L(α) can compute the primitive recursive functions and predicates and from there they follow the steps of classical recursion theory to obtain computability results on total and partially recursive functions and so on and so forth. In short, for a Universal Turing machine it is not said that for any given input tape it is possible to determine whether the Turing machine will halt or not, but in the case of the finite automata it will be always possible to do so. Intuitively, this is so because the finite automata maps a finite number of inputs into a finite number of terminal states, while the same is not valid for the universal Turing machine.
Comments (0)
You don't have permission to comment on this page.