Abstract
Alan Turing began a new area in science; he discovered that there are universal computers, which in principal are very simple. Up to now this is the basis of a modern computing theory and practice. In the paper one considers Turing computability in the frame of P (membrane) systems and other distributive systems. An overview of the recent results about small universal P and DNA systems and some open problems and possible directions of investigation are presented.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adleman, L.: Molecular Computation of Solutions to Combinatorial Problems. Science 226, 1021–1024 (1994)
Alhazov, A., Freund, R., Rogozhin, Y.: Computational Power of Symport/Antiport: History, Advances, and Open Problems. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2005. LNCS, vol. 3850, pp. 1–30. Springer, Heidelberg (2006)
Alhazov, A., Krassovitskiy, A., Rogozhin, Y.: Circular Post Machines and P Systems with Exo-insertion and Deletion. In: Gheorghe, M., Păun, G., Rozenberg, G., Salomaa, A., Verlan, S. (eds.) CMC 2011. LNCS, vol. 7184, pp. 73–86. Springer, Heidelberg (2012)
Alhazov, A., Kogler, M., Margenstern, M., Rogozhin, Y., Verlan, S.: Small Universal TVDH and Test Tube Systems. International Journal of Foundations of Computer Science 22(1), 143–154 (2011)
Alhazov, A., Kudlek, M., Rogozhin, Y.: Nine Universal Circular Post Machines. Computer Science Journal of Moldova 10, 3(30), 247–262 (2002)
Alhazov, A., Rogozhin, Y., Verlan, S.: A Small Universal Splicing P System. In: Gheorghe, M., Hinze, T., Păun, G., Rozenberg, G., Salomaa, A. (eds.) CMC 2010. LNCS, vol. 6501, pp. 95–102. Springer, Heidelberg (2010)
Alhazov, A., Rogozhin, Y., Verlan, S.: On Small Universal Splicing Systems. Fundamenta Informaticae (in press)
Alhazov, A., Verlan, S.: Minimization Strategies for Maximally Parallel Multiset Rewriting Systems. TUCS Report No. 862 (2008), and arXiv:1009.2706v1 [cs.FL], and Theoretical Computer Science 412, 1581–1591 (2011)
Cocke, J., Minsky, M.: Universality of Tag Systems with P = 2. Journal of the Association for Computing Machinery 11(1), 15–20 (1964)
Csuhaj-Varjú, E., Kari, L., Păun, G.: Test Tube Distributed Systems Based on Splicing. Computers and Artificial Intelligence 15(2–3), 211–232 (1996)
Csuhaj-Varjú, E., Margenstern, M., Vaszil, G., Verlan, S.: Small Computationally Complete Symport/Antiport P systems. Theoretical Computer Science 372(2-3), 152–164 (2007)
Csuhaj-Varjú, E., Verlan, S.: On Length-Separating Test Tube Systems. Natural Computing 7(2), 167–181 (2008)
Freund, R., Alhazov, A., Rogozhin, Y., Verlan, S.: Communication P Systems. In: Păun, G., Rozenberg, G., Salomaa, A. (eds.) The Oxford Handbook of Membrane Computing, ch. 5, pp. 118–143 (2010)
Freund, F., Freund, R.: Test Tube Systems: When Two Tubes are Enough. In: Rozenberg, G., Thomas, W. (eds.) Developments in Language Theory, Foundations, Applications and Perspectives, pp. 338–350. World Scientific Publishing Co., Singapore (2000)
Frisco, P., Zandron, C.: On Variants of Communicating Distributed H Systems. Fundamenta Informaticae 48(1), 9–20 (2001)
Frisco, P.: Computing with Cells: Advances in Membrane Computing. Oxford University Press (2009)
Head, T.: Formal Language Theory and DNA: An Analysis of the Generative Capacity of Recombinant Behaviors. Bulletin of Mathematical Biology 49, 737–759 (1987)
Head, T., Păun, G., Pixton, D.: Language Theory and Molecular Genetics. Generative Mechanisms Suggested by DNA Recombination. In: [41], ch. 7, vol. 2
Korec, I.: Small Universal Register Machines. Theoretical Computer Science 168, 267–301 (1996)
Lipton, R.J.: DNA Solution of Hard Computational Problems. Science 268, 542–545 (1995)
Margenstern, M.: Frontier Between Decidability and Undecidability: A Survey. Theoretical Computer Science 231(2), 217–251 (2000)
Margenstern, M.: Surprising Areas in the Quest for Small Universal Devices. Electronic Notes in Theoretical Computer Science 225, 201–220 (2009)
Margenstern, M., Pavlotskaya, L.: On the Optimal Number of Instructions for Universality of Turing Machines Connected with a Finite Automaton. International Journal of Algebra and Computation 13(2), 133–202 (2003)
Margenstern, M., Rogozhin, Y.: A universal time-varying distributed H system of degree 1. In: Jonoska, N., Seeman, N.C. (eds.) DNA 2001. LNCS, vol. 2340, pp. 371–380. Springer, Heidelberg (2002)
Margenstern, M., Rogozhin, Y., Verlan, S.: Time-Varying Distributed H Systems of Degree 2 Can Carry Out Parallel Computations. In: Hagiya, M., Ohuchi, A. (eds.) DNA 2002. LNCS, vol. 2568, pp. 326–336. Springer, Heidelberg (2003)
Chen, J., Reif, J.H. (eds.): DNA 2003. LNCS, vol. 2943, pp. 48–53. Springer, Heidelberg (2004)
Margenstern, M., Verlan, S., Rogozhin, Y.: Time-varying distributed H systems: an overview. Fundamenta Informaticae 64, 291–306 (2005)
Minsky, M.: Computation, Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)
De Mol, L.: Tag Systems and Collatz-like Functions. Theoretical Computer Science 390, 92–101 (2008)
Neary, T., Woods, D.: The Complexity of Small Universal Turing Machines: A Survey. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 385–405. Springer, Heidelberg (2012)
Pavlotskaya, L.: Solvability of the Halting Problem for Certain Classes of Turing Machines. Mathematical Notes 13(6), 537–541 (1973); Translated from Matematicheskie Zametki 13(6), 899–909 (1973)
Păun, G.: Computing with Membranes. Journal of Computer and System Sciences 1(61), 108–143 (2000); Also TUCS Report No. 208 (1998)
Păun, G., Yokomori, T.: Membrane Computing Based on Splicing. In: Winfree, E., Gifford, D.K. (eds.) DNA Based Computers V. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 54, pp. 217–232. American Mathematical Society (1999)
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Heidelberg (1998)
Păun, G., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press (2010)
Post, E.L.: Formal Reductions of the General Combinatorial Decision Problem. American Journal of Mathematics 65(2), 197–215 (1943)
Priese, L., Rogozhin, Y., Margenstern, M.: Finite H-systems with 3 Test Tubes are not Predictable. In: Altman, R., Dunker, A., Hanter, L., Klein, T. (eds.) Proceedings of Pacific Simposium on Biocomputing, pp. 545–556. World Sci.Publ., Singapore (1998)
Robinson, R.M.: Minsky’s Small Universal Turing Machine. International Journal of Mathematics 2(5), 551–562 (1991)
Rogozhin, Y.: Small Universal Turing Machines. Theoretical Computer Science 168(2), 215–240 (1996)
Rogozhin, Y., Verlan, S.: On the Rule Complexity of Universal Tissue P Systems. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2005. LNCS, vol. 3850, pp. 356–362. Springer, Heidelberg (2006)
Rozenberg, G., Salomaa, A.: Handbook of Formal Languages, vol. 3. Springer, Heidelberg (1997)
Shannon, C.E.: A Universal Turing Machines with Two Internal States. Automata Studies, Ann. of Math. Stud. 34, 157–165 (1956)
Turing, A.M.: On Computable Real Numbers, with an Application to the Entscheidungsproblem. Proc. London Math. Soc. Ser. 2 42, 230–265 (1936)
Verlan, S.: A Boundary Result on Enhanced Time-Varying Distributed H Systems with Parallel Computations. Theoretical Computer Science 344(2-3), 226–242 (2005)
Verlan, S.: Communicating Distributed H Systems with Alternating Filters. In: Jonoska, N., Păun, G., Rozenberg, G. (eds.) Aspects of Molecular Computing. LNCS, vol. 2950, pp. 367–384. Springer, Heidelberg (2003)
Verlan, S.: Head Systems and Application to Bio-Informatics. PhD thesis, LITA, Université de Metz, Metz, France (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rogozhin, Y., Alhazov, A. (2013). Turing Computability and Membrane Computing. In: Csuhaj-Varjú, E., Gheorghe, M., Rozenberg, G., Salomaa, A., Vaszil, G. (eds) Membrane Computing. CMC 2012. Lecture Notes in Computer Science, vol 7762. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36751-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-36751-9_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36750-2
Online ISBN: 978-3-642-36751-9
eBook Packages: Computer ScienceComputer Science (R0)