Small Universal Tissue P Systems with Symport/Antiport Rules
Lists
Only you see this
Abstract
In this note, we consider the problem of looking for small universal one-symbol tissue P systems with symport/antiport rules. It is proved that six cells suffice to generate any recursively enumerable set of natural numbers by such a onesymbol tissue P system with symport/antiport rules, under the restriction that only one channel is allowed between two cells or between a cell and the environment. As for the case of allowing two channels between a cell and the environment, it is shown that the computational completeness can be obtained by one-symbol tissue P systems with symport/antiport rules having at most five cells. These results partially answer an open problem formulated by Artiom Alhazov, Rudolf Freund and Marion Oswald.
BibTeX
@article{zhang2012small,
author = {Xingyi Zhang and Bin Luo and Linqiang Pan},
title = {{Small Universal Tissue P Systems with Symport/Antiport Rules}},
journal = {Int. J. Comput. Commun. Control},
year = {2012},
doi = {10.15837/ijccc.2012.1.1432},
}| Universality Frontier for Asynchronous Cellular Automata | arXiv · 2025 |
| Time-free solution to independent set problem using P systems with active membranes | arXiv · 2021 |
| Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines | The Annals of Mathematics · 1961 |
| Solving Vertex Cover Problem by Means of Tissue P Systems with Cell Separation | Int. J. Comput. Commun. Control · 2010 |
| Self-replication and Computational Universality | arXiv · 2025 |
| Stone Age Distributed Computing | arXiv · 2012 |