DJJ's site navigation page

Research papers.

We recall the philosophical story of Buridan's donkey (or ass, dog, etc), who, when faced with two equally appealing bales of hay (or barley and oats, or carrots) could not make up its mind which to eat and so died of starvation.

Jean Buridan, Paris, circa 1295-1358. Philosopher and theologian. Attributed.

There is a movement afoot to "remove the clock" from advanced computing engines, and make computation asynchronous. See, for example, the IEE review for Sept 2004, pages 36-39. {No clock, no bus, no sweat by Roger Dettmer}

We have discussed how the problem of metastability in electronic arbitration circuits will affect the reliability of asynchronous parallel computing machines, in a paper in the Complex Systems conference at Rockhampton, Queensland in 1994.

The purpose of this brief page is to put the Buridan's donkey paradox of metastability into the context of the theory of dynamical systems which exhibit deterministic chaos, and to make a link with the Zeno paradox which is also concerned with the calculus, limit points, and the representation of numbers.

Experiments may easily be performed which put an electronic arbitration circuit into a metastable state, from which it may take an indefinite time to settle. It is argued that a certain proportion of multiple-channel asynchronous communication events will provoke such metastability.

As with the simple mechanical problem of balancing a pencil on its point, it is found that the time taken to leave the unstable fixed point depends on how close the system is set (in the absence of noise) to the fixed point in the first place.

To chose the fixed point exactly has zero probability in the domain of real numbers. For any small error epsilon there will be a time to arbitration T(epsilon) which increases logarithmically as (1/epsilon).

In the case of Buridan's donkey, the animal (postulated) presumably has a fixed life span L, and will therefore certainly die before making the decision if T(epsilon) exceeds L. Otherwise, however, if we are prepared to wait long enough, the postulated animal will always make up its mind.

The relevance to asynchronous self-timed computation is that attempts to speed up reliable computation by this means are doomed to failure... there is always a trade-off between speed and accuracy.

Buridan's donkey is postulated to sit at a limit point, which is in every respect similar to the limit of the sequence of intervals in Zeno's paradox. There is as much sense in talking about the physical reality of one limit point as of the other.

In deterministic chaos, the determinism depends on an infinite amount of knowledge about the initial state of the system under consideration, however simple it may be. As soon as we relax the requirement for an infinite amount of information, the system remains predictable only within certain bounds and for a certain maximum time.

A reader suggested adding noise to shake the system off its metastable point. Such noise should not affect the final logic state of the system, which has a certain noise-immunity.

However, it is not clear that noise will serve to lessen the time in metastability. It may even stabilise the unstable fixed point. A mechanical example of this is to drive an inverted pendulum with a noisy signal, vertically at the fulcrum (base) which can lead to the stabilisation of the inverted state, which then is subject to chaotic fluctuations.

Another suggestion is to add error-correction algorithms to the final results of any such computation. This might work, at a penalty of speed. However, the problem with metastability is that one does not know, a-priori, how long to wait before assuming that the output has settled. This is similar to the trapping behaviour of a chaotic circuit - which one knows will trap eventually but one has no information about how long it may take to trap.

There is the concept of the J-number, a universal finite number which is a function of the product of (speed, accuracy, number of parallel arbitrations) in a system. It is not clear how one might set about deriving a numerical estimate of such a limit. In any case, this would depend critically on the metrics used to estimate speed, accuracy, and parallelism. But there is an important principle that the J-number is not infinite; there does exist a limit.

Such behaviour would set ultimate limits on computability by any practical engine.

Copyright © D.Jefferies 2002, 2004.

D.Jefferies email 14th September 2004