首页|The power of synchronizing rules in membrane computing
The power of synchronizing rules in membrane computing
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Membrane computing provides computational devices inspired by living cells (called membrane systems) that are proved to be computationally universal. It is a theoretical challenge to find the minimum of resources to get the full power of a Turing machine. The major contribution of this paper is to present such a system with only ONE membrane and without ANY additional ingredient (like cooperation, division, catalysts) in which the synchronization between non-cooperative rules (of length at most three) plays an essential role. Furthermore, such a system is able to solve the SAT NP-complete problem in polyno-mial time. (c) 2022 Elsevier Inc. All rights reserved.
NSTL
Elsevier
