Turing completeness of water computing
Tóm tắt
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
$$\mu$$
-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.
Tài liệu tham khảo
Maass, W., Schnitger, G., & Szemerédi, E. (1987). “Two tapes are better than one for off-line Turing machines,” in Proceedings of the nineteenth annual ACM symposium on Theory of computing, pp. 94–100.
Mahatantila, K., Chandrajith, R., Jayasena, H., & Ranawana, K. (2008). Spatial and temporal changes of hydrogeochemistry in ancient tank cascade systems in Sri Lanka: evidence for a constructed wetland. Water and Environment Journal, 22(1), 17–24.
Emch, A. (1901). Two hydraulic methods to extract the \(n\)th root of any number. The American Mathematical Monthly, 8(1), 10–12.
Trogemann, G., Nitussov, A.Y., & Ernst, W. (2001). Computing in Russia: the history of computer devices and information technology revealed. Vieweg Braunschweig.
Phillips, A. W. (1950). Mechanical models in economic dynamics. London School of Economics and Political Science.
Ryder, W.H. (2009). A System Dynamics View of the Phillips Machine. In 27th International Conference of the System Dynamics Society.
Moylan, M. J. (1968). Fluid logic in simple terms. Transatlantic Arts.
Arulanandham, J. J., Calude, C. S., & Dinneen, M. J. (2003). Solving SAT with Bilateral Computing. Romanian Journal of Information Science and Technology, 6(1–2), 9–18.
Ishdorj, T.-O., Ochirbat, O., & Naimannaran, C. (2020). A \(\mu\)-fluidic biochip design for spiking neural P systems. International Journal of Unconventional Computing 15, 1.
Adamatzky, A. (2019) A brief history of liquid computers. Philosophical Transactions of the Royal Society B 374, 1774.
Taberlet, N., Marsal, Q., Ferrand, J., & Plihon, N. (2018). Hydraulic logic gates: Building a digital water computer. European Journal of Physics, 39(2), 025801.
Hinze, T., Happe, H., Henderson, A., & Nicolescu, R. (2020). Membrane computing with water. Journal of Membrane Computing, 2(2), 121–136.
Păun, G. (2000). Computing with membranes. Journal of Computer and System Sciences, 61(1), 108–143.
Sosík, P. (2019). P systems attacking hard problems beyond NP: A survey. Journal of Membrane Computing, 1(3), 198–208.
Valencia-Cabrera, L., Pérez-Hurtado, I., & Martínez-del Amor, M. Á. (2020). Simulation challenges in membrane computing. Journal of Membrane Computing, pp. 1–11.
Alhazov, A., Freund, R., & Ivanov, S. (2021). P systems with limited number of objects. Journal of Membrane Computing, 3(1), 1–9.
Nicolescu, R., Henderson, A. (2018). An introduction to cP Systems. In Enjoying Natural Computing: Essays Dedicated to Mario de Jesús Pérez-Jiménez on the Occasion of His 70th Birthday (C. Graciani, A. Riscos-Núñez, G. Păun, G. Rozenberg, and A. Salomaa, eds.), vol. 11270 of Lecture Notes in Computer Science, pp. 204–227, Springer, Berlin
Zappa, F., Esculapio, S . (2017).Microcontrollers. Hardware and Firmware for 8-bit and 32-bit devices. LIGHTNING SOURCE Incorporated.
Calude, C., & Sântean, L. (1990). On a theorem of Günter Asser. Mathematical Logic Quarterly, 36(2), 143–147.
Robinson, J. (1950). General recursive functions. Proceedings of the American Mathematical Society, 1(6), 703–718.
Severin, D. E., et al. (2008). Unary primitive recursive functions. Journal of Symbolic Logic, 73(4), 1122–1138.
Calude, C. (2011). Theories of computational complexity. Elsevier, Amsterdam
Ionescu, M., Păun, G., & Yokomori, T. (2006). Spiking neural P systems. Fundamenta Informaticae 71(2), 279–308.
Martín-Vide, C., Păun, G., Pazos, J., & Rodríguez-Patón, A. (2003). Tissue P systems. Theoretical Computer Science, 296(2), 295–326.