Related Experiment Videos
Bio-steps beyond Turing
Cristian S Calude1, Gheorghe Păun
1Department of Computer Science, The University of Auckland, Bag 92019, Auckland, New Zealand. cristian@cs.auckland.ac.nz
Bio Systems
|November 6, 2004
Summary
Biologically computing agents may compute Turing uncomputable functions, challenging previous assumptions in molecular computing. This study introduces accelerated P systems, inspired by biological mechanisms, to explore non-computability in brains and potential extraterrestrial intelligence.
Area of Science:
- Theoretical computer science
- Molecular computing
- Computational biology
Background:
- The question of whether biological systems can compute Turing uncomputable functions remains largely unexplored.
- Existing speed-up methods in computing often rely on non-determinism.
Purpose of the Study:
- To investigate the theoretical possibility of biological computing agents computing Turing uncomputable functions.
- To introduce and analyze accelerated P systems based on biological principles.
Main Methods:
- Formulating results within the framework of membrane computing (P systems).
- Proving universality results for deterministic P systems.
- Developing accelerated P systems by modifying hardware components like reactor size and communication channels.
Main Results:
- Demonstrating that deterministic P systems can achieve universality, forming the basis for accelerated systems.
- Introducing two biologically inspired acceleration postulates for P systems.
- Highlighting that acceleration in these systems is a hardware feature, not environmental.
Conclusions:
- The theoretical possibility exists for biological agents to compute functions previously considered Turing uncomputable.
- Accelerated P systems offer a novel approach to exploring computational limits in biological and artificial intelligence.
- The study opens new avenues for research at the intersection of computation, biology, and astrobiology.