Declarative and Imperative Approaches for Proving Turing Completeness of SPIDER
Emilia Golemanova, Tzanko Golemanov · 2020
Control Network Programming, or just CNP, and its supporting language named SPIDER, is a new programming paradigm combining features from the declarative, imperative and graphical programming. A Turing machine is a theoretical abstraction that expresses the extent of the power of the computational models. Any system that is Turing complete is sufficiently powerful to compute any algorithm. The paper provides a simple proof of the Turing completeness of SPIDER by declarative and imperative CNP implementations of the Turing machine behavior, thereby showing that Turing completeness is a consequence of a few basic and fundamental features inherent to SPIDER.