Networks of Uniform Splicing Processors: Computational Power and Simulation

Sandra Gómez-Canaval, Victor Mitrana, Mihaela Păun, José Angel Sanchez Martín and José Ramón Sánchez Couso
Additional contact information
Sandra Gómez-Canaval: Departamento de Sistemas Informáticos, Universidad Politécnica de Madrid, C/Alan Turing s/n, 28031 Madrid, Spain
Victor Mitrana: Departamento de Sistemas Informáticos, Universidad Politécnica de Madrid, C/Alan Turing s/n, 28031 Madrid, Spain
Mihaela Păun: National Institute for Research and Development of Biological Sciences, Independentei Bd. 296, 060031 Bucharest, Romania
José Angel Sanchez Martín: Departamento de Sistemas Informáticos, Universidad Politécnica de Madrid, C/Alan Turing s/n, 28031 Madrid, Spain
José Ramón Sánchez Couso: Departamento de Sistemas Informáticos, Universidad Politécnica de Madrid, C/Alan Turing s/n, 28031 Madrid, Spain

Mathematics, 2020, vol. 8, issue 8, 1-16

Abstract: We investigated the computational power of a new variant of network of splicing processors, which simplifies the general model such that filters remain associated with nodes but the input and output filters of every node coincide. This variant, called network of uniform splicing processors , might be implemented more easily. Although the communication in the new variant seems less powerful, the new variant is sufficiently powerful to be computationally complete. Thus, nondeterministic Turing machines were simulated by networks of uniform splicing processors whose size depends linearly on the alphabet of the Turing machine. Furthermore, the simulation was time efficient. We argue that the network size can be decreased to a constant, namely six nodes. We further show that networks with only two nodes are able to simulate 2-tag systems. After these theoretical results, we discuss a possible software implementation of this model by proposing a conceptual architecture and describe all its components.

Keywords: theory of computation; computational models; Turing machine; 2-tag system; splicing; splicing processor; network of uniform splicing processors; Apache Giraph; Apache Spark; Spark GraphX architecture; NSUP engine (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/8/1217/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/8/1217/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:8:p:1217-:d:389111

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().