Turing Completeness of Water Computing

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, water falls 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.