Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections

Details Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections

2009-07-29

arxiv.org/abs/0907.5130v1

EPTCS 3, 2009, pp. 173-182

Computer Science

Formal Languages and Automata Theory

Scientific paper

10.4204/EPTCS.3.16

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.

Affiliated with

Also associated with

No associations

Rating

Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521682