Structural Machines as a Mathematical Model of Biological and Chemical Computers

Abstract

To rigorously describe and study the living morphological computers, we develop a formal model of algorithms
and computations called a structural machine providing theoretical tools for exploration of possibilities of biological
computations and extension of their applications. We study properties of structural machines demonstrating how
they can model the most popular in computer science model of computation — Turing machine. We also prove that
structural machines can solve some problems more eciently than Turing machines. We also show how structural
machines model a programmable amorphous biological computer called a Physarum machine, as well as an inductive
Turing machine.