Table I also suggests that no extant markomata has the power of a Turing Machine. The standard double auction requires even more prodigious memory capacity, given that sequences of bids and asks stored in different identifiable memory locations must be retrieved and compared, and therefore should exhibit the computational capacity of (at least) a linear bounded automaton. Sealed bid order execution requires an ordering of submitted bids, which can be captured by a first-in first-out memory stack: hence the ‘pushdown’. While the posted price format possesses no memory capacity and therefore qualifies as a finite automaton, a sealed bid auction requires the comparison of a submitted bid to an ordered array of previously entered bids stored in a memory, and therefore qualifies as one of a number of k-headed pushdown automata. Table I above suggests that some forms of automata may be mapped into different formats of order execution familiar from the literatures of experimental economics and market microstructure.
![automaton theory automaton theory](https://image.slidesharecdn.com/automatatheory-180802142625/95/automata-theory-5-638.jpg)
The reason that the markomata hierarchy does not collapse down to a single flat uniformity is that more computationally complex markets situated higher in the Chomsky hierarchy perform other functions over and above those performed by the markets that they simulate: for instance, futures markets may seek to arbitrage price discrepancies as well as track the spot markets in their purview. The theory of computation informs us that certain specific market forms can simulate other market forms as long as they are composed of markomata of greater or equal computational capacity. This would be the case even if the futures markets were operated as a double auction, whereas the spot markets were operated as a sealed-bid auction. In an abstract computational sense, the futures market ‘encapsulates’ the model of the spot market within its own algorithms.
![automaton theory automaton theory](http://3.bp.blogspot.com/-2MBLWd5ocQk/Td_sSRsgG4I/AAAAAAAAANc/UwLb1SPoZqk/s1600/automata_theory.jpg)
Likewise, the dealer-organized wholesale market ‘simulates’ the posted-price markets of the retailer, while superimposing other functions. For instance, the futures market for red no.6 wheat ‘simulates’ the spot market for red no.6 wheat, in the sense that it can perform the same operations, augmented by other related operations, in the course of ‘tracking’ the wheat market. The idea of one markomata simulating the operation of another is quite familiar to market practitioners, even though it has been absent up until now in economic theory. This leads to the important notion of ‘markomata simulation’. However, the hierarchy is inclusive, in the sense that the more powerful automaton can perform all the calculations of the automaton lower down in the hierarchy, because it can simulate the operation of machines of lesser computational capacity. Furthermore, there exist some problems that cannot be solved even at the most powerful level of the hierarchy some strings are Turing non-computable on the Turing Machine. One implication of the Chomsky hierarchy is that some problems, which are unsolvable at the lower levels of computational capacity, can be shown to be solvable at the higher levels. Data dissemination, order routing, clearing, record-keeping, and all the rest might themselves be composed of automata of various degrees of computational capacity any real-world market is formally characterized by the composition of these component automata and this begins to reveal the true combinatorial explosion of forms inherent in the theory of markomata. At this early stage, it is important to note that it is merely the order execution function that is captured by this NDF, and not the entire range of functions potentially performed by any real-world instantiation of the posted-price market. A single unit of the commodity is offered at a single price, where the alphabet concerned is the rational numbers order execution either matches that number as bid by the purchaser, or is rejected.
![automaton theory automaton theory](https://image.slidesharecdn.com/3-160118100913/95/intro-automata-theory-6-638.jpg)
In one (arbitrary) initial economic example, the order execution function of a very rudimentary market, such as the posted- or fixed-price market, will be modeled as a nondeterministic finite automaton. Suppose we set out to formalize one function of one simple market as an automaton. If the transition function T maps an existing state of Ŧ into more than one state, then it is called a nondeterministic finite automaton (NDF). After reading a symbol on the tape, it either accepts or rejects it, depending upon the state that the device is in it then enters the next state prescribed by the transition function. A finite automaton can be thought of as an extremely limited computing device with no external memory capacity but a single working tape, which it can read only once. A finite automaton Ŧ defined over an alphabet α = called final accepting states causes Ŧ to halt. The most rudimentary description of a market begins with the notion of a finite automaton. Philip Mirowski, in Philosophy of Economics, 2012 3.2 Markets as automata