A Turing machine simulation by P systems without charges
From MaRDI portal
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 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.
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
Cites work
- scientific article; zbMATH DE number 1583885 (Why is no real title available?)
- scientific article; zbMATH DE number 5671765 (Why is no real title available?)
- scientific article; zbMATH DE number 2118901 (Why is no real title available?)
- A gap in the space hierarchy of P systems with active membranes
- Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P
- Characterising the complexity of tissue P systems with fission rules
- Computational efficiency of dissolution rules in membrane systems
- Computational efficiency of minimal cooperation and distribution in polarizationless P systems with active membranes
- Computing with membranes
- Constant-space P systems with active membranes
- Membrane Computing
- Membrane computing and complexity theory: A characterization of PSPACE
- Membrane division, oracles, and the counting hierarchy
- On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution
- P systems with active membranes: Attacking NP-complete problems
- Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation
- Space complexity equivalence of P systems with active membranes and Turing machines
- The computational power of cell division in P systems: Beating down parallel computers?
- The computational power of membrane systems under tight uniformity conditions
- The counting power of P systems with antimatter
- Tissue P systems.
Cited in
(11)- A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules
- From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules
- A new method to simulate restricted variants of polarizationless P systems with active membranes
- On maximal parallel application of rules in rewriting P systems
- Bounding the space in P systems with active membranes
- Alternative space definitions for P systems with active membranes
- Simulating Turing machines with polarizationless P systems with active membranes
- Evaluating space measures in P systems
- Automatic design of arithmetic operation spiking neural P systems
- scientific article; zbMATH DE number 1735649 (Why is no real title available?)
- Multi-learning rate optimization spiking neural P systems for solving the discrete optimization problems
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)
