๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Limits on the computing power of biological systems

โœ Scribed by Michael Conrad; Arnon Rosenthal

Publisher
Springer
Year
1981
Tongue
English
Weight
457 KB
Volume
43
Category
Article
ISSN
1522-9602

No coin nor oath required. For personal study only.

โœฆ Synopsis

The theory of computational complexity and certain explicitly-stated hypotheses imply limitations on the information processing power of biological systems. Parallelism, special purpose organization, and analog mechanisms may provide speedup critical for life processes, but have little power in the face of exponential growth. We show that "polynomially simulatable" biological systems cannot exhibit dynamic behavior which produces the solution of an intractable problem. The argument implies that parallelism does not allow biological systems to defeat the exponential explosion, but rather is important because it allows polynomial time algorithms to be used more efficiently.

๐Ÿ“œ SIMILAR VOLUMES

On limits on the computational power of
On limits on the computational power of data-accumulating algorithms
โœ Stefan D Bruda; Selim G Akl ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 102 KB

In the data-accumulating paradigm, inputs arrive continuously in real time, and the computation terminates when all the already received data are processed before another datum arrives. Previous research states that a constant upper bound on the running time of a successful algorithm within this par

On the computational power of self-stabi
On the computational power of self-stabilizing systems
โœ James Abello; Shlomi Dolev ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 859 KB

The computational power of self-stabilizing distributed systems is examined. Assuming availability of any number of processors, each with (small) constant size memory we show that any computable problem can be realized in a self-stabilizing fashion. The result is derived by presenting a distributed

The limits of biological simulation
The limits of biological simulation
โœ Michael Conrad ๐Ÿ“‚ Article ๐Ÿ“… 1974 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 421 KB
On the computational power of context-fr
On the computational power of context-free PC grammar systems
โœ Niculae Mandache ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 132 KB

It is shown that non-returning parallel communicating grammar systems with -free contextfree components can generate any recursively enumerable language. Since it was proven that such systems can be simulated by returning PC grammar systems with context-free components, the result extends to those.