It is known that the polarizationless P systems of the kind involved in the definition of the P conjecture are able to solve problems in the complexity class P by leveraging their uniformity condition. Here, we show that they are indeed able to simulate a deterministic Turing machine 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 for P systems with charges can be carried on.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2020). A Turing machine simulation by P systems without charges. JOURNAL OF MEMBRANE COMPUTING, 2(2), 71-79 [10.1007/s41965-020-00031-5].
A Turing machine simulation by P systems without charges
Leporati, Alberto
;Manzoni, Luca;Mauri, Giancarlo;Porreca, Antonio E.;Zandron, Claudio
2020
Abstract
It is known that the polarizationless P systems of the kind involved in the definition of the P conjecture are able to solve problems in the complexity class P by leveraging their uniformity condition. Here, we show that they are indeed able to simulate a deterministic Turing machine 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 for P systems with charges can be carried on.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Leporati-2020-JMEC-VoR.pdf
Solo gestori archivio
Tipologia di allegato:
Publisher’s Version (Version of Record, VoR)
Licenza:
Tutti i diritti riservati
Dimensione
1.46 MB
Formato
Adobe PDF
|
1.46 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
