Back to Search
Start Over
A Turing machine simulation by P systems without charges
- Source :
- Proceedings of ACMC'2018, Proceedings of ACMC'2018, 2018, Auckland, New Zealand. pp.213--221
- Publication Year :
- 2020
- Publisher :
- Springer, 2020.
-
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 $\mathbf{P}$ 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.<br />Comment: Asian Branch of International Conference on Membrane Computing (ACMC 2018). arXiv admin note: text overlap with arXiv:1902.03879
- Subjects :
- FOS: Computer and information sciences
Computer science
P systems
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
01 natural sciences
Polarizationless P system
ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
membrane computing
computational complexity
Turing machine
symbols.namesake
Non-deterministic Turing machine
0202 electrical engineering, electronic engineering, information engineering
Complexity class
[INFO]Computer Science [cs]
Turing machine simulation
Time complexity
ComputingMilieux_MISCELLANEOUS
Discrete mathematics
Conjecture
Applied Mathematics
(L, L) -uniformity
INF/01 - INFORMATICA
Computer Science - Computational Complexity
Computational Theory and Mathematics
010201 computation theory & mathematics
Theory of computation
symbols
Nesting (computing)
020201 artificial intelligence & image processing
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Proceedings of ACMC'2018, Proceedings of ACMC'2018, 2018, Auckland, New Zealand. pp.213--221
- Accession number :
- edsair.doi.dedup.....db8e308862cd3aceba8b796c24bb4200