Turing completeness of water computing

Henderson, Alec, Nicolescu, Radu, Dinneen, Michael J., Chan, T.N., Happe, Hendrik, and Hinze, Thomas (2021) Turing completeness of water computing. Journal of Membrane Computing, 3 (3). pp. 182-193.

[img] PDF (Published Version) - Published Version
Restricted to Repository staff only

View at Publisher Website: https://doi.org/10.1007/s41965-021-00081...
2


Abstract

We further develop water computing as a variant of P systems. We propose an improved modular design, which duplicates the main water flows by associated control flows. We first solve the three open problems of the previous design by demonstrating: how functions can be stacked without a combinatorial explosion of valves; how termination of the system can be detected; and how to reset the system. We then prove that the system is Turing complete by modelling the construction of μ-recursive functions. The new system is based on directed acyclic graphs, where tanks are nodes and pipes are arcs; there are no loops anymore, waterfalls strictly in a ‘top down’ direction. Finally, we demonstrate how our water tank system can be viewed as a restricted version of cP systems. We conclude with a list of further challenging problems.

Item ID: 75511
Item Type: Article (Research - C1)
ISSN: 2523-8914
Keywords: Membrane systems, Water-based computing, μ recursion
Copyright Information: © The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. 2021
Date Deposited: 19 Jul 2022 22:49
FoR Codes: 46 INFORMATION AND COMPUTING SCIENCES > 4613 Theory of computation > 461302 Computational complexity and computability @ 100%
SEO Codes: 28 EXPANDING KNOWLEDGE > 2801 Expanding knowledge > 280115 Expanding knowledge in the information and computing sciences @ 100%
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page