Volume 43, Number 5, 331-339, DOI: 10.1007/s00236-006-0024-x

On the number of nodes in universal networks of evolutionary processors

Artiom Alhazov, Carlos Martín-Vide and Yurii Rogozhin

View Related Documents

Abstract

We consider the networks of evolutionary processors (NEP) introduced by J. Castellanos, C. Martí n-Vide, V. Mitrana and J. Sempere recently. We show that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and moreover, NEPs with four nodes can generate any RE language. Thus, we improve existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we obtain optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet, and mNEPs with two nodes can generate any RE language; this is not possible for mNEPs with one node. Some open problems are formulated.

Fulltext Preview

Image of the first page of the fulltext document