A New Model of Computation Drawn with String Diagrams
Monoidal computer I: Basic computability by string diagrams (2012)
Dusko Pavlovic introduces a model of computation built on monoidal categories that captures exactly the computable functions of standard models, in line with the Church-Turing Thesis. Its key feature is string diagrams, a sound and complete graphical formalism that offers an intuitive interface for abstract reasoning about computation while hiding implementation details. The long-term goal is a high-level programming language for a theory of computational resources, such as one-way and trapdoor functions; this paper sketches the path, pursued in three sequels.
The salient feature of the language of monoidal categories is that it is supported by a sound and complete graphical formalism, string diagrams, which provide a concrete and intuitive interface for abstract reasoning about computation.