Monoidal computer. I: Basic computability by string diagrams
From MaRDI portal
Abstract: We present a new model of computation, described in terms of monoidal categories. It conforms the Church-Turing Thesis, and captures the same computable functions as the standard models. It provides a succinct categorical interface to most of them, free of their diverse implementation details, using the ideas and structures that in the meantime emerged from research in semantics of computation and programming. 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. The original motivation and the ultimate goal of this effort is to provide a convenient high level programming language for a theory of computational resources, such as one-way functions, and trapdoor functions, by adopting the methods for hiding the low level implementation details that emerged from practice. In the present paper, we make a first step towards this ambitious goal, and sketch a path to reach it. This path is pursued in three sequel papers, that are in preparation.
Recommendations
Cites work
- \(H^\ast\)-algebras and nonunital Frobenius algebras: first steps in infinite-dimensional categorical quantum mechanics
- A new description of orthogonal bases
- Cartesian bicategories. I
- Categorical logic of names and abstraction in action calculi
- Classical and quantum structuralism
- Coalgebras and cartesian categories
- Coherence for compact closed categories
- Computer-Aided Security Proofs for the Working Cryptographer
- Foundations of Cryptography
- Frobenius monads and pseudomonoids
- Geometry of abstraction in quantum computation
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3959364 (Why is no real title available?)
- scientific article; zbMATH DE number 3706504 (Why is no real title available?)
- scientific article; zbMATH DE number 3751225 (Why is no real title available?)
- scientific article; zbMATH DE number 46869 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- scientific article; zbMATH DE number 783754 (Why is no real title available?)
- scientific article; zbMATH DE number 3279108 (Why is no real title available?)
- scientific article; zbMATH DE number 3367095 (Why is no real title available?)
- Interacting Quantum Observables
- Kleene's amazing second recursion theorem
- Monoidal categories with natural numbers object
- Quantum and Classical Structures in Nondeterminstic Computation
- Quantum complexity theory
- Quantum measurements without sums
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Relating toy models of quantum computation: comprehension, complementarity and dagger mix autonomous categories
- Teleportation in general probalistic theories
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- The geometry of tensor calculus. I
- The lambda calculus. Its syntax and semantics. Rev. ed.
- Toy quantum categories (extended abstract)
- Why John von Neumann did not like the Hilbert space formalism of quantum mechanics (and what he liked instead)
Cited in
(20)- Monoidal computer. III: A coalgebraic view of computability and complexity (extended abstract)
- Kindergarden quantum mechanics graduates \textit{...or how I learned to stop gluing LEGO together and love the ZX-calculus}
- Contextual equivalence for signal flow graphs
- Tracing the man in the middle in monoidal categories
- The lax braided structure of streaming I/O
- Confluence of graph rewriting with interfaces
- Interacting Hopf algebras
- The monoidal structure of Turing machines
- Symmetric monoidal categories with attributes
- DisCoPy: monoidal categories in Python
- Turing automata and graph machines
- Smooth coalgebra: testing vector analysis
- Chasing diagrams in cryptography
- String diagram rewrite theory III: Confluence with and without Frobenius
- Programs as Diagrams
- Promonads and String Diagrams for Effectful Categories
- Testing randomness by Matching Pennies
- Operads for complex system design specification, analysis and synthesis
- String diagrams for premonoidal categories
- A robust graph-based approach to observational equivalence
This page was built for publication: Monoidal computer. I: Basic computability by string diagrams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q385721)
