Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-038 | 24th May 2000 00:00

On Computation with Pulses


Publication: 13th June 2000 09:25
Downloads: 3557


We explore the computational power of formal models for computation
with pulses. Such models are motivated by realistic models for
biological neurons, and by related new types of VLSI (``pulse stream

In preceding work it was shown that the computational power of formal
models for computation with pulses is quite high if the pulses
arriving at a computational unit have an approximately linearly rising
or linearly decreasing initial segment. This property is satisfied by
common models for biological neurons. On the other hand several
implementations of pulse stream VLSI employ pulses that are
approximately piecewise constant (i.e.~step functions).

In this article we investigate the relevance of the shape of pulses in
formal models for computation with pulses. It turns out that the
computational power drops significantly if one
replaces pulses with linearly rising or decreasing initial segments by
piecewise constant pulses. We provide an exact characterization of the
latter model in terms of a weak version of a random access machine
(RAM). We also compare the language recognition capability of a
recurrent version of this model with that of deterministic finite
automata and Turing machines.

ISSN 1433-8092 | Imprint