[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Computing with energy and chemical reactions

  • Published:
Natural Computing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Taking inspiration from some laws of Nature—energy transformation and chemical reactions—we consider two different paradigms of computation in the framework of Membrane Computing. We first study the computational power of energy-based P systems, a model of membrane systems where a fixed amount of energy is associated with each object and the rules transform objects by manipulating their energy. We show that if we assign local priorities to the rules, then energy-based P systems are as powerful as Turing machines; otherwise, they can be simulated by vector addition systems, and hence are not universal. Then, we consider stochastic membrane systems where computations are performed through chemical networks. We show how molecular species and chemical reactions can be used to describe and simulate the functioning of Fredkin gates and circuits. We conclude the paper with some research topics related to computing with energy-based P systems and with chemical reactions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Bennett CH (1973) Logical reversibility of computation. IBM J Res Dev 17:525–532

    Article  MATH  Google Scholar 

  • Besozzi D, Cazzaniga P, Pescini D, Mauri G (to appear) A multivolume approach to stochastic modelling with membrane systems. In: Condon A, Harel D, Kok JN, Salomaa A, Winfree E (eds) Algorithmic bioprocesses. Natural computing series. Springer-Verlag, Berlin

  • Cao Y, Gillespie DT, Petzold LR (2006) Efficient step size selection for the tau-leaping simulation method. J Chem Phys 124:044109

    Article  Google Scholar 

  • Cazzaniga P, Pescini D, Besozzi D, Mauri G (2006) Tau leaping stochastic simulation method in P systems. In: Hoogeboom HJ, Păun Gh, Rozenberg G, Salomaa A (eds) Membrane computing. 7th international workshop, WMC 2006, LNCS 4361, Springer-Verlag, Berlin, pp 298–313

  • Dittrich P (2005) Chemical computing. In: Banâtre JP, Fradet P, Giavitto JL, Michel O (eds) Unconventional programming paradigms, UPP 2004, LNCS 3566, Springer-Verlag, Berlin, pp 19–32

  • Fredkin E, Toffoli T (1982) Conservative logic. Int J Theor Phys 21(3–4):219–253

    Article  MATH  MathSciNet  Google Scholar 

  • Freund R (2003) Energy-controlled P systems. In: Păun Gh, Rozenberg G, Salomaa A, Zandron C (eds) Membrane computing. Proceedings of the international workshop, WMC–CdeA 2002, LNCS 2597, Springer-Verlag, Berlin, pp 247–260

  • Freund R, Oswald M (2002) GP systems with forbidding context. Fundam Inf 49(1–3):81–102

    MATH  MathSciNet  Google Scholar 

  • Freund R, Leporati A, Oswald M, Zandron C (2005) Sequential P systems with unit rules and energy assigned to membranes. In: Margenstern M (ed) Machines, computations, and universality. 4th international conference, MCU 2004, LNCS 3354, Springer-Verlag, Berlin, pp 200–210

  • Frisco P (2004) The Conformon-P system: a molecular and cell biology-inspired computability model. Theor Comput Sci 312:295–319

    Article  MATH  MathSciNet  Google Scholar 

  • Gillespie DT (1977) Exact stochastic simulation of coupled chemical reactions. J Phys Chem 81:2340–2361

    Article  Google Scholar 

  • Gillespie DT (2007) Stochastic simulation of chemical kinetics. Ann Rev Phys Chem 58:35–55

    Article  Google Scholar 

  • Karp R, Miller R (1969) Parallel program schemata. J Comput Syst Sci 3(4):167–195. Also RC2053, IBM T.J. Watson Research Center, New York, April 1968

    Google Scholar 

  • Landauer R (1961) Irreversibility and heat generation in the computing process. IBM J Res Dev 5:183–191

    Article  MATH  MathSciNet  Google Scholar 

  • Landauer R (1982) Uncertainty principle and minimal energy dissipation in the computer. Int J Theor Phys 21(3–4):283–297

    Article  MATH  Google Scholar 

  • Leporati A, Zandron C, Mauri G (2004) Simulating the Fredkin gate with energy-based P systems. J Univers Comput Sci 10(5):600–619

    MathSciNet  Google Scholar 

  • Leporati A, Zandron C, Mauri G (2006) Reversible P systems to simulate Fredkin circuits. Fundam Inf 74:529–548

    MATH  MathSciNet  Google Scholar 

  • Matsumaru N, Centler F, Speroni di Fenizio P, Dittrich P (2005) Chemical organization theory as a theoretical base for chemical computing. Int J Unconv Comput 3:285–309

    Google Scholar 

  • Minsky ML (1967) Finite and infinite machines. Prentice-Hall, Englewood Cliffs

    MATH  Google Scholar 

  • Păun Gh (2000) Computing with membranes. J Comput Syst Sci 1(61):108–143. See also Turku Centre for Computer Science, TUCS Report No. 208, 1998

    Google Scholar 

  • Păun Gh (2002) Membrane computing—an introduction. Springer-Verlag, Berlin

    MATH  Google Scholar 

  • Păun Gh, Suzuki Y, Tanaka H (2001) P systems with energy accounting. Int J Comput Math 78(3):343–364

    Article  MATH  MathSciNet  Google Scholar 

  • Pescini D, Cazzaniga P, Ferretti C, Mauri G (2009) First steps toward a wet implementation for τ-DPP. In: Corne DW, Frisco P, Păun Gh, Rozenberg G, Salomaa A (eds) Membrane computing. 9th international workshop, WMC 2008, LNCS 5391, Springer-Verlag, Berlin, pp 355–373

  • Peterson JL (1981) Petri net theory and the modeling of systems. Prentice-Hall, Englewood Cliffs

    Google Scholar 

  • Toffoli T (1980) Reversible computing. MIT/LCS Technical Report 51

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano – Bicocca, Viale Sarca 336, 20126, Milano, Italy

    Alberto Leporati, Paolo Cazzaniga, Dario Pescini & Claudio Ferretti

  2. Dipartimento di Informatica e Comunicazione, Università degli Studi di Milano, Via Comelico 39, 20135, Milano, Italy

    Daniela Besozzi

Authors
  1. Alberto Leporati
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniela Besozzi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Paolo Cazzaniga
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dario Pescini
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Claudio Ferretti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alberto Leporati.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Leporati, A., Besozzi, D., Cazzaniga, P. et al. Computing with energy and chemical reactions. Nat Comput 9, 493–512 (2010). https://doi.org/10.1007/s11047-009-9160-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-009-9160-x

Keywords

Search

Navigation