文章基本信息
- 标题：Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections
- 本地全文：下载
- 作者：Remco Loos ; Florin Manea ; Victor Mitrana 等
- 期刊名称：Electronic Proceedings in Theoretical Computer Science
- 电子版ISSN：2075-2180
- 出版年度：2009
- 卷号：3
- 页码：173-182
- DOI：10.4204/EPTCS.3.16
- 出版社：Open Publishing Association
- 摘要：In this paper, we present some results regarding the size complexity of Accepting Networks of Evolutionary Processors with Filtered Connections (ANEPFCs). We show that there are universal ANEPFCs of size 10, by devising a method for simulating 2-Tag Systems. This result significantly improves the known upper bound for the size of universal ANEPFCs which is 18.
We also propose a new, computationally and descriptionally efficient simulation of nondeterministic Turing machines by ANEPFCs. More precisely, we describe (informally, due to space limitations) how ANEPFCs with 16 nodes can simulate in O(f(n)) time any nondeterministic Turing machine of time complexity f(n). Thus the known upper bound for the number of nodes in a network simulating an arbitrary Turing machine is decreased from 26 to 16.
