A Turing machine simulation by P systems without charges

DOI10.1007/S41965-020-00031-5zbMATH Open1469.68043arXiv1902.03883OpenAlexW3124169376MaRDI QIDQ1982960FDOQ1982960

Antonio E. Porreca, Giancarlo Mauri, Luca Manzoni, Alberto Leporati, Claudio Zandron

Publication date: 14 September 2021

Published in: Journal of Membrane Computing (Search for Journal in Brave)

Abstract: It is well known that the kind of P systems involved in the definition of the P conjecture is able to solve problems in the complexity class $mathbfP$ by leveraging the uniformity condition. Here we show that these systems are indeed able to simulate deterministic Turing machines working in polynomial time with a weaker uniformity condition and using only one level of membrane nesting. This allows us to embed this construction into more complex membrane structures, possibly showing that constructions similar to the one performed in [1] for P systems with charges can be carried out also in this case.

Full work available at URL: https://arxiv.org/abs/1902.03883

Recommendations

• Simulating Turing machines with polarizationless P systems with active membranes
• An efficient simulation of polynomial-space Turing machines by P systems with active membranes
• A new method to simulate restricted variants of polarizationless P systems with active membranes
• Unconventional Computation
• Simulating elementary active membranes

zbMATH Keywords

P-systemsL-uniformity

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites Work

• Computing with membranes
• Title not available (Why is that?)
• Tissue P systems.
• The computational power of cell division in P systems: Beating down parallel computers?
• P systems with active membranes: Attacking NP-complete problems
• Title not available (Why is that?)
• Membrane computing and complexity theory: A characterization of PSPACE
• Title not available (Why is that?)
• The computational power of membrane systems under tight uniformity conditions
• Space complexity equivalence of P systems with active membranes and Turing machines
• Membrane division, oracles, and the counting hierarchy
• Computational efficiency of dissolution rules in membrane systems
• On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution
• Membrane Computing
• Characterising the complexity of tissue P systems with fission rules
• The counting power of P systems with antimatter
• Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation
• Computational Efficiency of Minimal Cooperation and Distribution in Polarizationless P Systems with Active Membranes
• Constant-Space P Systems with Active Membranes
• Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P
• Title not available (Why is that?)

Cited In (9)

• Bounding the space in P systems with active membranes
• Alternative space definitions for P systems with active membranes
• On maximal parallel application of rules in rewriting P systems
• A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules
• Evaluating space measures in P systems
• Automatic design of arithmetic operation spiking neural P systems
• Multi-learning rate optimization spiking neural P systems for solving the discrete optimization problems
• Title not available (Why is that?)
• From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules

This page was built for publication: A Turing machine simulation by P systems without charges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1982960)