J
2018
Generalized P colonies with passive environment
CIENCIALOVÁ, Lucie, Luděk CIENCIALA and Petr SOSÍK
Basic information
Original name
Generalized P colonies with passive environment
Authors
CIENCIALOVÁ, Lucie (203 Czech Republic, guarantor, belonging to the institution), Luděk CIENCIALA (203 Czech Republic, belonging to the institution) and Petr SOSÍK (203 Czech Republic, belonging to the institution)
Edition
Theoretical Computer Science, Amsterdam, Elsevier, 2018, 0304-3975
Other information
Type of outcome
Článek v odborném periodiku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
RIV identification code
RIV/47813059:19240/18:A0000210
Organization
Filozoficko-přírodovědecká fakulta – Slezská univerzita v Opavě – Repository
Keywords in English
computatuinal completeness; P colony; Register machine
Tags
International impact, Reviewed
Links
LQ1602, research and development project.
V originále
We study two variants of P colonies with initial content of P colony and so-called passive environment: P colonies with two objects inside each agent that can only consume or generate objects, and P colonies with one object inside each agent using rewriting and communication rules. We show that the first kind of P colonies with one consumer agent and one sender agent can generate all sets of natural numbers computed by register machines, and hence they are computationally complete in the Turing sense. Similarly, also the second kind of systems with three agents with rewriting/communication rules is computationally complete. The paper improves previously published universality results concerning generalized P colonies, and it also extends the knowledge about very simple multi-agent systems capable of universal computation.
Displayed: 20/10/2024 00:22