کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433694 | 689605 | 2016 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Small (purely) catalytic P systems simulating register machines Small (purely) catalytic P systems simulating register machines](/preview/png/433694.png)
The paper contributes to the topic of (purely) catalytic P systems. Catalytic P systems represent the original and likely the simplest class of membrane computing models. It is known that (purely) catalytic P systems with two (respectively three) catalysts and one membrane can simulate any Minsky register machine and, hence, they are computationally complete. However, the problem of minimal size of such a universal catalytic P system remains open for about ten years. We improve known results about small catalytic P systems simulating register machines in three different modes (generating, accepting, computing functions). Together with some specific universal register machine [7], one could eventually construct a small universal catalytic P system. As a consequence, we also improve the previous construction of a minimal catalytic P system generating a non-semilinear set, diminishing the number of necessary rules from 29 to 24.
Journal: Theoretical Computer Science - Volume 623, 11 April 2016, Pages 65–74