Computing with Cells in Environment: P Colonies
Erzsébet Csuhaj-Varjú, Jozef Kelemen, Alica Kelemenová, Gheorghe Paun and György Vaszil
We propose and investigate a class of abstract computing devices composed from as simple as possible agents acting and evolving in a shared environment. The device is of a type similar to the so-called tissue P systems known in the field of membrane computing, with cell components being of a very simple form. Moreover, we suppose no direct communication among cells, they communicate only via the changing environment which is completely uniform at the beginning (only one kind of symbols is present). Still, in this extremely weak framework we prove that these devices are able to compute what Turing machines can compute; several different universality results are given, obtained by varying the size and the number of the cells.