Accepting networks of genetic processors are computationally complete

Abstract

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 Elsevier B.V. All rights reserved.