Turing completeness of water computing
Journal Publication ResearchOnline@JCUAbstract
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.
Journal
Journal of Membrane Computing
Publication Name
N/A
Volume
3
ISBN/ISSN
2523-8914
Edition
N/A
Issue
3
Pages Count
12
Location
N/A
Publisher
Springer
Publisher Url
N/A
Publisher Location
N/A
Publish Date
N/A
Url
N/A
Date
N/A
EISSN
N/A
DOI
10.1007/s41965-021-00081-3