Structural Machines as a Mathematical Model of Biological and Chemical Computers

Mark Burgin, Andrew Adamatzky

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.


Keywords


model of computation, algorithm, structural machine, Turing machine, Physarum machine, bio-inspired computing, computing automaton, slime mould, unconventional computing, computational efficiency

Full Text:

PDF

References


Adamatzky, Andrew (2001). Computing in nonlinear media and automata collectives. CRC Press.

Adamatzky, Andrew (2007). Physarum machines: encapsulating reaction–diffusion to compute spanning tree. Natur- wissenschaften 94(12), 975.

Adamatzky, Andrew (2014). Slime mould electronic oscillators. Microelectronic Engineering 124, 58–65.

Adamatzky, Andrew (2016). Advances in Unconventional Computing. Volume 1: Theory. Vol. 22. Springer.

Adamatzky, Andrew and Richard Mayne (2015). Actin automata: Phenomenology and localizations. International

Journal of Bifurcation and Chaos 25(02), 1550030.

Adamatzky, Andrew, Benjamin De Lacy Costello and Tetsuya Asai (2005). Reaction-diffusion computers. Elsevier.

Blum, Lenore, Mike Shub, Steve Smale et al. (1989). On a theory of computation and complexity over the real numbers: np-completeness, recursive functions and universal machines. Bulletin (New Series) of the American Mathematical Society 21(1), 1–46.

Burgin, Mark (2003). From neural networks to grid automata. Modelling and Simulation.

Burgin, Mark (2005). Measuring power of algorithms, programs, and automata. Artificial Intelligence and Computer Science pp. 1–61.

Burgin, Mark (2012). Structural Reality. Nova Science Publishers.

Burgin, Mark and Eugene A Bratalskii (1986). The principle of asymptotic uniformity in complex system modeling. Operation Research and Automated Control Systems pp. 115–122.

Burgin, Mark and Eugene Eberbach (2009a). On foundations of evolutionary computation: An evolutionary automata approach. Handbook of Research on Artificial Immune Systems and Natural Computing: Applying Complex Adaptive Technologies pp. 342–360.

Burgin, Mark and Eugene Eberbach (2009b). Universality for Turing machines, inductive Turing machines and evolutionary algorithms. Fundamenta Informaticae 91(1), 53–77.

Calude, C and M Dinneen (2015). Unconventional computation and natural computation. In: 14th International Conference, UCNC. Springer.

Chomsky, Noam (1956). Three models for the description of language. IRE Transactions on information theory 2(3), 113–124.

Cooper, S Barry (2013). What makes a computation unconventional?. In: Computing Nature. pp. 255–269. Springer.

Deutsch, David (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. Vol. 400. The Royal Society. pp. 97–117.

Elgot, Calvin C and Abraham Robinson (1964). Random-access stored-program machines, an approach to program- ming languages. Journal of the ACM 11(4), 365–399.

Erokhin, Victor, Gerard David Howard and Andrew Adamatzky (2012). Organic memristor devices for logic elements with memory. International Journal of Bifurcation and Chaos 22(11), 1250283.

Feynman, Richard P (1986). Quantum mechanical computers. Foundations of physics 16(6), 507–531.

Freedman, Michael, Alexei Kitaev, Michael Larsen and Zhenghan Wang (2003). Topological quantum computation.

Bulletin of the American Mathematical Society 40(1), 31–38.

Gale, Ella, Andrew Adamatzky and Ben de Lacy Costello (2015). Slime mould memristors. BioNanoScience 5(1), 1– 8.

Graves, Alex, Greg Wayne and Ivo Danihelka (2014). Neural turing machines. arXiv preprint arXiv:1410.5401.

Hopcroft, John E, Rajeev Motwani and Jeffrey D Ullman (2001). Introduction to automata theory, languages, and computation. ACM SIGACT News 32(1), 60–65.

Kendon, Viv, Angelika Sebald and Susan Stepney (2015). Heterotic computing: past, present and future. Phil. Trans.

R. Soc. A 373(2046), 20140225.

Kieu, Tien D (2003). Computing the non-computable. Contemporary Physics 44(1), 51–71.

Kirkpatrick, DG, JD Radke and G Toussaint (1985). Computational geometry.

Kolmogorov, Andrei N (1953). On the concept of algorithm. Uspekhi Mat. Nauk 8(4), 175–176.

Kolmogorov, Andreı N and Vladimir A Uspensky (1958). K opredeleniu algoritma. Uspekhi Matematicheskikh Nauk [Russian Mathematical Surveys] 13(4), 3–28.

Kung, H and C Leiserson (1978). Science, CMUDoC: Systolic arrays for (VLSI). CMUCS.

Martınez, Genaro J, Andrew Adamatzky and Harold V McIntosh (2017). A computation in a cellular automaton collider rule 110. In: Advances in Unconventional Computing. pp. 391–428. Springer.

Matsumoto, Kenji, Tetsuo Ueda and Yonosuke Kobatake (1986). Propagation of phase wave in relation to tactic responses by the plasmodium of physarum polycephalum. Journal of Theoretical Biology 122(3), 339–345.

Mayne, Richard, Andrew Adamatzky and Jeff Jones (2015). On the role of the plasmodial cytoskeleton in facilitating intelligent behavior in slime mold Physarum polycephalum. Communicative & integrative biology 8(4), e1059007.

Nakagaki, Toshiyuki, Hiroyasu Yamada and Agota Toth (2000). Intelligence: Maze-solving by an amoeboid organism. Nature 407(6803), 470.

Paun, Gheorghe (2000). Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143. Paun, Gheorghe and Grzegorz Rozenberg (2002). A guide to membrane computing. Theoretical Computer Science

(1), 73–100.

Petri, Carl A (1962). Fundamentals of a theory of asynchronous information flow.

Schumann, Andrew and Andy Adamatzky (2011). Physarum spatial logic. New Mathematics and Natural Computation 7(03), 483–498.

Schumann, Andrew and Krzysztof Pancerz (2014). Towards an object-oriented programming language for Physarum polycephalum computing: A Petri net model approach. Fundamenta Informaticae 133(2-3), 271–285.

Schumann, Andrew and Krzysztof Pancerz (2015). Physarumsoft-a software tool for programming Physarum ma- chines and simulating Physarum games. In: Computer Science and Information Systems (FedCSIS), 2015 Federated Conference on. IEEE. pp. 607–614.

Shannon, Claude E (1941). Mathematical theory of the differential analyzer. Studies in Applied Mathematics 20(1- 4), 337–354.

Shepherdson, John C and Howard E Sturgis (1963). Computability of recursive functions. Journal of the ACM (JACM) 10(2), 217–255.

Siccardi, Stefano and Andrew Adamatzky (2016). Quantum actin automata and three-valued logics. IEEE Journal on Emerging and Selected Topics in Circuits and Systems 6(1), 53–61.

Siccardi, Stefano, Jack A Tuszynski and Andrew Adamatzky (2016). Boolean gates on actin filaments. Physics Letters A 380(1), 88–97.

Stephenson, Steven L, Henry Stempen and Ian Hall (1994). Myxomycetes: a handbook of slime molds. Timber Press Portland, Oregon.

Stepney, Susan, Samuel L Braunstein, John A Clark, Andy Tyrrell, Andrew Adamatzky, Robert E Smith, Tom Addis, Colin Johnson, Jonathan Timmis, Peter Welch et al. (2005). Journeys in non-classical computation i: A grand challenge for computing research. International Journal of Parallel, Emergent and Distributed Systems 20(1), 5– 19.

Trahtenbrot, BA (1974). Algorithms and computing automata. moscow, sovetskoye radio.

Von Neumann, John, Arthur W Burks et al. (1966). Theory of self-reproducing automata. IEEE Transactions on Neural Networks 5(1), 3–14.

Weihrauch, Klaus (2000). Introduction to computable analysis. texts in theoretical computer science.

Whiting, James GH, Ben PJ de Lacy Costello and Andrew Adamatzky (2015). Transfer function of protoplasmic tubes of Physarum polycephalum. Biosystems 128, 48–51.


Refbacks

  • There are currently no refbacks.