Traffic as a universal computer
1. Introduction
It has been postulated that if one possesses a device which can perform some basic logical functions, then such a device is capable of universal computation. That is, with enough component operations pieced together in various arrangements and orders, one should be able to perform any known or unknown computation. [1]
Earlier in our history, computation was performed by humans, such as manipulating an abacus, and more recently with mechanical wheels and linkages such as are found in a simple cash register. In our current level of technology, the basic logical functions are performed by silicon micro-electronics. As technology continues to improve, and our civilization continues to encourage the development of even faster means of computation, other media may replace the role of the silicon diodes. Quantum computing, biological analog computing using DNA proteins and even hybrid biological-silicon computation models are all being looked upon as possible successors to silicon in continuing the performance curve exemplified in Moore's Law.
One can only wonder where future civiliations may turn to solve their computational problems. In the Hitchhikers Guide to the Galaxy series of novels, the space travelers return to earth to discover that the planet Earth is simply a means for a super-intelligent extraterrestrial race to perform a complicated calculation, for which the final result happens to be 42. [2]
2. Boolean basics
The basic logical operations are AND (n), OR (U), and NOT (~). These are shown in the figure below, along with two other operators of interest, NAND and XOR.
These operators describe the state of a new condition (say C) based on the state of the input conditions (A and B). Let 0 represent a �false� condition and 1 represent a �true� condition. For example, let A be the condition that you have cookie batter. Let B be the condition that you have chocolate chips. Then you can represent the condition C, your ability to make chocolate chip cookies as C=AnB. The truth table below shows the resulting values of various logical operators on input conditions A and B.
Now, let�s use these operators to perform a basic arithmetic calculation, adding two 1-bit numbers, A and B, to get the 2-bit number C. In the figure below, the right hand side of the table shows the resulting values for the two binary place-holders (C1 is the �ones� digit, and C2 is the �zero� digit) resulting from the set of possible states of A and B.
By examination, it can be seen that the states C1 and C2 can be represented as:
C1=AnB;
C2=A XOR B=(An~B)U(~AnB)
So, configuring logic gates as follows should always result in the correct solution to the calculation:
For more complex calculations, such as adding more numbers with more than 1 binary bit and so on, other truth tables and logic gates could be constructed. All this aside, the important point is that they can all be constructed from these simple logical operations.
But how many of these operations are necessary for universal computation? Using DeMorgan�s Law, one can construct an AND from OR and NOT, or can construct an OR from and AND and NOT. Shown below:
3. Representing the logic gates in various media
In the previous section it was shown that if one obtains devices which can be combined and can perform the NOT operation as well as one of either AND or OR, such a device is capable of universal computation. That is, any known calculation or logical operation can be broken down into constituent parts and be represented as combinations of the two fundamental logical elements, as was shown in the example of simple addition.
Now, let�s consider ways of representing these functions physically. First, consider the flow of water through pipes. If there is any water flowing through a pipe, then that pipe has a value of �1�, otherwise �0�. To construct an OR function from two pipes is a simple matter of joining the two pipes.
More challenging is the representation of the NOT operator using water pipes. However, with enough mechanical precision, it can be achieved. One way would be as shown in the figure below. Next to pipe A, run another pipe which always has water flowing through it (as marked as a �1� on the diagram). Connect the two pipes with a linkage which forces the second pipe shut when water is flowing in pipe A. In design it would be important to be certain that a minimum amount of flow in pipe A would be sufficient to close the second pipe to a degree that would be considered to be �0� in subsequent operations from the output of that pipe.
Thus, since the water pipe system can perform OR as well as NOT, then a universal computer could be constructed out of water pipes.
Next consider a system of traffic. In this case, roads carry a stream of vehicles, rather than pipes carrying flow of water as in the previous example. Conceivably, a city planner has the ability to configure a network of roads, just as with a water pipe network. Flow could be controlled as ON (�0�) or OFF (�1�) as follows: �1� roads could be placed between points of high travel demand, say between a work area and residential area on a weekday evening. �0� roads could be placed so that it would be certain that they would not attract any users, say by connecting a work location to the desert or wilderness.
The urban designer would need to be clever enough to configure these two types of roads so as to have them intersect in various ways to perform the logical operations (to be explained below). The results of any downstream section of road from a logical operator (road junction) could be verified through a mechanical counting device, such as a road tube (air pressure), inductive loop sensor (a metal loop in the pavement surface that detects a metal vehicle passing over through the inductance that the vehicle causes), video image processing, or simply manual counting by staff in the field at the roadside. A sufficient flow of traffic on the road (say 100 vehicles per hour) would result in the road to be considered to be ON (�1�), otherwise �0�.
Now let�s see how one could construct the fundamental logical operators by intersecting the roads. The easiest to visualize, as in the water pipes example, is the OR operator. Again, this is created by joining (merging) two roads together. Since traffic flow on either of the upstream road segments is sufficient to cause traffic flow on the downstream segment, this configuration is capable of representing the OR operator.
The NOT operator in traffic turns out to be easier to implement than in the water pipes, with no mechanical apparatus needed. The STOP sign (and the driver�s ability to react in a predictable manner) is all that is needed. For this operation, a cross road with heavy traffic is forced to stop and wait for gaps to cross the traffic on Road A. If Road A has heavy traffic, then the drivers on the cross road will be unable to continue on their trip to the downstream measurement point. Thus, whatever the flow on Road A, the downstream end of the cross road will be the opposite, which represents the NOT operator.
Like the water pipes example, it has been shown that a road traffic system can be configured to perform the Boolean (logical) operations in a sequence so as to be capable of universal computation. Whatever the problem or calculation, it is only a matter of bringing together the right type of roads in the correct intersections (logical operators) in order to find the solution to the computation at downstream roads.
To go one step further with traffic, the XOR can be represented as a special type of two-way stop-controlled intersection. Unlike the previous junctions however, in this intersection the motorists would need to be advised by a sign, saying that they should only enter the intersection if there is no traffic on the opposing leg. Otherwise they may pass through. Due to unreasonable delay, motorists would probably not comply with this sign. So this type of operator would probably not be as successfully implemented as the two outlined previously.
An alternative method for generating �0� roads is also worth noting. This works by forcing a road to stop and wait for a gap to cross itself. Although this system would guarantee a �0� downstream, it would probably cause a swift public reaction at the city planner who built such a road and the public would demand that it be changed. Therefore, the conventional way to generate �0� roads is probably the most suitable.
Since the existing road network is so extensive (the US alone contains millions of miles of freeways, arterials, and collector roadways that may be suitable), rather than build a network of roads as described in this system, it may be possible to find a system which meets exactly the desired specifications. Further, the use of satellite imaging for surveillance of the road traffic conditions could be combined with the GIS-based search routine to find both the suitable road network for the computation at hand, and the resulting answer. With archiving of historic traffic data, indeed, the computation may have already been performed.
Although idealized as a discrete system, the deviation (or degradation) of the signal strength from a pure �1� or �0� in traffic implementation may lend itself to deliberate use of this feature in fuzzy logic applications.
1. Gary William Flake. The Computational Beauty of Nature. MIT Press, 1998.
2. Douglas Adams. So long, and thanks for all the fish.
 |
Back to the main page |