Back to Search Start Over

A Turing machine simulation by P systems without charges

Authors :
Giancarlo Mauri
Claudio Zandron
Luca Manzoni
Antonio E. Porreca
Alberto Leporati
Leporati, A
Manzoni, L
Mauri, G
Porreca, A
Zandron, C
Leporati, Alberto
Manzoni, Luca
Mauri, Giancarlo
Porreca, Antonio E.
Zandron, Claudio
Dipartimento di Informatica Sistemistica e Comunicazione (DISCo)
Università degli Studi di Milano-Bicocca [Milano] (UNIMIB)
Calcul Naturel (CANA)
Laboratoire d'Informatique et Systèmes (LIS)
Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Università degli Studi di Milano-Bicocca = University of Milano-Bicocca (UNIMIB)
Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
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

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