Random Explorations in Automata Theory
Gary J. Shannon
Mar. 2, 2003
Clocks: Synchronous, Asynchronous, Phase-Synchronous, Sequential and More
In a synchronous automaton every cell or node is updated simultaneously at a regular interval. There is an implied master clock that ticks at a steady pace and all updates to the automaton happen in step with this clock.
An asynchronous automaton has each node updating at a rate independant of that of any other node. Changes that take place infinitely fast can not be defined since the neighborhood that needs to be examined for the update is also changing infinitely fast. We must assume, therefore, that even in an asychronous matrix there is a certain charactistic rate at which changes can take place. This rate might be thought of as the time required by a node to recover after a change before another change can occur, or it might be characterized as the propigation delay of the links. Neurons, for example, experience a refractory period after firing during which they cannot fire again regardless of inputs, and transmission lines of any kind suffer from some propigation delay, so in a real automaton it might be a combination of these two effects that limits the rate of update. Either way the net result is that updates to a node take place only at some fixed, finite rate of speed. In an ideal matrix constructed of perfectly identical components the node update rate will be identical for all nodes, yet no two nodes will be guaranteed to be updating simultaneously.
A coupled asynchronous automaton will have each node updating no faster than its maximum rate but possibly slower. The initiation of an update event is triggered only by a change taking place in a neighboring node. Thus a node will remain quiescent as long as none of its neighbors changes, but will respond, either instantaneously or after some finite propigation delay, to a changed neighbor by initiating an update event. If the propigation delay is zero then any change anywhere in the matrix will propigate instantly through all connected quiescent nodes, but will not propigate through a node which has recently changed unless that node's refractory period has elapsed.
A phase-synchronous automaton is one is which only a fixed subset of the nodes are update at a given time with the remaining nodes being updated at some later clock tick. For example, an automaton might have half of its nodes updated on every odd clock tick and the other half updated on every even clock tick. Phase synchronous automata are classified by how many discrete phases exist in one complete update cycle. Thus a 4-phase automaton would require 4 clock ticks to update every node at least once.
There are a few possible variations of the phase-synchronous matrix.
All nodes are updated at each phase but a different rule is applied at each phase. For example a 2-phase matrix might apply one rule on the even numbered clock ticks and a second rule on the odd ticks.
A subset of the nodes is updated in each phase and a different rule is applied to each subset. For example a 2-phase matrix might apply the first rule to half of the nodes on the even clock ticks and a second rule to the remaining nodes on the odd ticks.
All nodes are updated with every phase of the cycle but certain links are active only at certain phases. For example there might be three species of links, those that convey neighbor information on the odd tick only, those that convey neighbor information on the even tick only and those that convey neighbor information on all ticks.
In a sequential automaton only one node is updated at time and the next node to be udated is selected either from a fixed update schedule, or as a result of the outcome of the rule. In the second case the sequential automaton is identical with the Turing machine.