Presentation
Simulating Turing Machines with Polarizationless P Systems with Active Membranes
Author/s | Gazdag, Zsolt
Kolonits, Gábor Gutiérrez Naranjo, Miguel Ángel |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2014 |
Deposit Date | 2018-04-09 |
Published in |
|
ISBN/ISSN | 978-3-319-14369-9 0302-9743 |
Abstract | We prove that every single-tape deterministic Turing machine working in
t(n)
t(n)
time, for some function
t:N→N
t:N→N
, can be simulated by a uniform family of polarizationless P systems with active membranes. ... We prove that every single-tape deterministic Turing machine working in t(n) t(n) time, for some function t:N→N t:N→N , can be simulated by a uniform family of polarizationless P systems with active membranes. Moreover, this is done without significant slowdown in the working time. Furthermore, if logt(n) logt(n) is space constructible, then the members of the uniform family can be constructed by a family machine that uses O(logt(n)) O(logt(n)) space. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España |
Project ID. | TIN2012-37434 |
Citation | Gazdag, Z., Kolonits, G. y Gutiérrez Naranjo, M.Á. (2014). Simulating Turing Machines with Polarizationless P Systems with Active Membranes. En CMC 2014: 15th International Conference on Membrane Computing (229-240), Prague, Czech Republic: Springer. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Simulating Turing Machines.pdf | 355.3Kb | [PDF] | View/ | |