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.

PDF (Published Version) - Published Version Restricted to Repository staff only

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.

Actions (Repository Staff Only)

Item Control Page