Monoidal computer I: Basic computability by string diagrams

Dusko Pavlovic

    Research output: Contribution to journalArticleAcademicpeer-review

    15 Citations (Scopus)
    42 Downloads (Pure)

    Abstract

    We present a new model of computation, described in terms of monoidal categories. It conforms to 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.
    Original languageEnglish
    Pages (from-to)94-116
    Number of pages23
    JournalInformation and computation
    Volume226
    DOIs
    Publication statusPublished - May 2013

    Keywords

    • Computability
    • Diagrams
    • Monoidal computer
    • String

    Fingerprint Dive into the research topics of 'Monoidal computer I: Basic computability by string diagrams'. Together they form a unique fingerprint.

    Cite this