Pavlovic D. Programs as Diagrams: From Categorical Computability to Computable Categories

Springer Cham, 2023. — 252 p. — (Theory and Applications of Computability) — eBook ISBN: 978-3-031-34827-3.It is not always clear what computer programs mean in the various languages in which they can be written, yet a picture can be worth 1000 words, a diagram 1000 instructions.In this unique textbook/reference, programs are drawn as string diagrams in the language of categories, which display a universal syntax of mathematics (Computer scientists use them to analyze the program semantics; programmers to display the syntax of computations). Here, the string-diagrammatic depictions of computations are construed as programs in a single-instruction programming language. Such programs as diagrams show how functions are packed in boxes and tied by strings. Readers familiar with categories will learn about the foundations of computability; readers familiar with computability gain access to category theory. Additionally, readers familiar with both are offered many opportunities to improve the approach.Topics and features:Delivers a ‘crash’ diagram-based course in theory of computation
Uses single-instruction diagrammatic programming language
Offers a practical introduction into categories and string diagrams as computational tools
Reveals how computability is programmability, rather than an ‘ether’ permeating computers
Provides a categorical model of intensional computation is unique up to isomorphism
Serves as a stepping stone into research of computable categoriesIn addition to its early chapters introducing computability for beginners, this flexible textbook/resource also contains both middle chapters that expand for suitability to a graduate course as well as final chapters opening up new research.