Transducers based on networks of polarized evolutionary processors

Abstract We consider a new type of transducer that does not scan sequentially the input word. This transducer is actually a network of polarized evolutionary processors ( NPEP ) which receives a word as input and collects in the output node, when the computation halts, the translation of the input word. We prove that these transducers can simulate the work of generalized sequential machines on every input. Furthermore, all words obtained by a given finite state transducer by the shortest computations on a given word can also be computed by the new transducers. Unlike the case of generalized sequential machines, every recursively enumerable language can be the transduction, defined by the new transducer, of a very simple regular language.