Accepting Networks of Genetic Processors are computationally complete

作者：Campos Marcelino; Sempere Jose M^*

来源：Theoretical Computer Science, 2012, 456: 18-29.

DOI：10.1016/j.tcs.2012.06.028

• Parallel Genetic Algorithms
• Networks of biologically-inspired processors
• Computational completeness

We propose a computational model that is inspired by genetic operations over strings such as mutation and crossover. The model, Accepting Network of Genetic Processors, is highly related to previously proposed ones such as Networks of Evolutionary Processors and Networks of Splicing Processors. These models are complete computational models inspired by DNA evolution and recombination. Here, we prove that the proposed model is computationally complete (it is equivalent to the Turing machine). Hence, it can accept any recursively enumerable language. In addition, we relate the proposed model with (parallel) Genetic Algorithms or Evolutionary Programs and we set these techniques as decision problem solvers.

• 出版日期2012-10-19