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 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.
A Turing machine simulation by P systems without charges
Manzoni, Luca;
2020-01-01
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 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 in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Leporati2020_Article_ATuringMachineSimulationByPSys.pdf
Accesso chiuso
Tipologia:
Documento in Versione Editoriale
Licenza:
Copyright Editore
Dimensione
1.46 MB
Formato
Adobe PDF
|
1.46 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
|
post Manzoni.pdf
Open Access dal 18/02/2021
Descrizione: final version at link: https://link.springer.com/article/10.1007/s41965-020-00031-5
Tipologia:
Bozza finale post-referaggio (post-print)
Licenza:
Digital Rights Management non definito
Dimensione
1.93 MB
Formato
Adobe PDF
|
1.93 MB | Adobe PDF | Visualizza/Apri |
|
11368_2962858_print.pdf
accesso aperto
Tipologia:
Bozza finale post-referaggio (post-print)
Licenza:
Digital Rights Management non definito
Dimensione
1.86 MB
Formato
Adobe PDF
|
1.86 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
