|
F. Peper, T. Isokawa, N. Kouda, N. Matsui
This paper describes a novel type of asynchronous cellular automata,
in which transitions of cells only take place
when triggered by transitions of their neighboring cells.
Called Self-Timed Cellular Automaton (STCA), the model
offers control over its cells' operations
to the same degree as in synchronous cellular automata,
while at the same time offers the flexibility
of its purely asynchronous counterparts.
We implement some simple functionalities on STCA,
like wires, crossings of wires, and NAND-gates,
and show that a synchronous cellular automaton with N states
can be simulated by an STCA with O(N . square_root(N)) states
in linear time.
This establishes the computational universality of STCA,
since synchronous cellular automata can,
if properly designed,
embed universal Turing Machines.
The STCA model offers promise for the realization
of cellular automaton-based computers
with logic devices and wires on the molecular scale,
a technology that is expected to take off in 10 to 15 years.
In this context, self-timing is especially useful>
for its compatibility with the asynchronous behavior of molecules.
and for avoiding delay problems associated with a central clock.
|