Ponencia
Simulating Turing Machines with Polarizationless P Systems with Active Membranes
Autor/es | Gazdag, Zsolt
Kolonits, Gábor Gutiérrez Naranjo, Miguel Ángel |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2014 |
Fecha de depósito | 2018-04-09 |
Publicado en |
|
ISBN/ISSN | 978-3-319-14369-9 0302-9743 |
Resumen | 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. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | TIN2012-37434 |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Simulating Turing Machines.pdf | 355.3Kb | [PDF] | Ver/ | |