Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Simulating Turing Machines with Polarizationless P Systems with Active Membranes
verfasst von : Zsolt Gazdag, Gábor Kolonits, Miguel A. Gutiérrez-Naranjo
Erschienen in: Membrane Computing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We prove that every single-tape deterministic Turing machine working in
$$t(n)$$
time, for some function
$$t:\mathbb {N}\rightarrow \mathbb {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
$$\log t(n)$$
is space constructible, then the members of the uniform family can be constructed by a family machine that uses
$$O(\log t(n))$$
space.