ACM Books – serie

This book explores the profound legacy of Alan Turing, and how his five great ideas have been developed by the winners of the Turing Prize to shape the digital world we live in today. These five groundbreaking concepts—universal computability and insolvability, cryptography, electronic digital computers and software, artificial intelligence (AI), and computational biology—serve as the pillars of the narrative.Turing's Children makes the complex ideas in the work of the Turing prize winners accessible to a broad audience. It traces the evolution of these ideas from abstract mathematical principles to their real-world applications, demonstrating their influence on everyday life. Readers will discover how Turing's legacy is woven into the fabric of modern technology: from the smartphones in our pockets and secure online banking, to the development of life-saving drugs and the conversational abilities of AI systems like ChatGPT.The book weaves together historical anecdotes, profiles of pioneering scientists, and vivid examples of current innovations. It offers a comprehensive view of how Turing's vision continues to inspire breakthroughs across science and technology. Turing's Children reveals the enduring relevance of Turing's ideas and the ongoing quest to push the boundaries of what machines—and humanity—can achieve.

Today’s large language models excel at pattern recall yet falter on long-range planning, self-critique, context loss, and the tendency of maximum-likelihood training to reward popularity over quality. MACI offers a promising route to AGI by orchestrating specialized LLM agents through explicit protocols rather than enlarging a single model. Several modules remedy complementary weaknesses: adversarial-collaborative debate surfaces hidden assumptions; critical-reading rubrics filter incoherent arguments; information-theoretic signals steer dialogue quantitatively; transactional memory enables reliable long-horizon execution; and a dual-agent ethical court adjudicates outputs. Crucially, MACI also modulates linguistic behavior, tuning each agent’s contentiousness and emotional tone, so the collective explores ideas from contrasting, affect-aware perspectives before converging.Fourteen aphorisms distill the framework’s philosophy, includingIntelligence emerges from regulated collaboration, not isolated brillianceExploration must remain in tension with exploitation.Across healthcare diagnosis, investment support, scheduling, supply-chain management, and news-bias mitigation, MACI ensembles deliver significant improvements in reasoning depth, planning horizon, and reliability compared with similar-sized single models. By uniting structured debate, information-theoretic coordination, persistent memory, affect-aware discourse, and deliberative ethics, MACI demonstrates that rigorously validated multi-agent collaboration provides a practical, interpretable path toward robust general intelligence.

Professor Stephen A. Cook is a pioneer of the theory of computational complexity. His work on NP-completeness and the P vs. NP problem remains a central focus of this field. Cook won the 1982 Turing Award for "his advancement of our understanding of the complexity of computation in a significant and profound way." This volume includes a selection of seminal papers embodying the work that led to this award, exemplifying Cook's synthesis of ideas and techniques from logic and the theory of computation including NP-completeness, proof complexity, bounded arithmetic, and parallel and space-bounded computation. These papers are accompanied by contributed articles by leading researchers in these areas, which convey to a general reader the importance of Cook's ideas and their enduring impact on the research community. The book also contains biographical material, Cook's Turing Award lecture, and an interview. Together these provide a portrait of Cook as a recognized leader and innovator in mathematics and computer science, as well as a gentle mentor and colleague.

Professor Stephen A. Cook is a pioneer of the theory of computational complexity. His work on NP-completeness and the P vs. NP problem remains a central focus of this field. Cook won the 1982 Turing Award for "his advancement of our understanding of the complexity of computation in a significant and profound way." This volume includes a selection of seminal papers embodying the work that led to this award, exemplifying Cook's synthesis of ideas and techniques from logic and the theory of computation including NP-completeness, proof complexity, bounded arithmetic, and parallel and space-bounded computation. These papers are accompanied by contributed articles by leading researchers in these areas, which convey to a general reader the importance of Cook's ideas and their enduring impact on the research community. The book also contains biographical material, Cook's Turing Award lecture, and an interview. Together these provide a portrait of Cook as a recognized leader and innovator in mathematics and computer science, as well as a gentle mentor and colleague.

This book introduces and provides an analysis of the basic concepts of algorithms, data, and computation and discusses the role of algorithms in ruling and shaping our world. It provides a clear understanding of the power and impact on humanity of the pervasive use of algorithms.From Algorithms to Thinking Machines combines a layman's approach with a well-founded scientific description to discuss both principles and applications of algorithms, Big Data, and machine intelligence. The book provides a clear and deep description of algorithms, software systems, data-driven applications, machine learning, and data science concepts, as well as the evolution and impact of artificial intelligence.After introducing computing concepts, the book examines the relationships between algorithms and human work, discussing how jobs are being affected and how computers and software programs are influencing human life and the labor sphere. Topics such as value alignment, collective intelligence, Big Data impact, automatic decision methods, social control, and political uses of algorithms are illustrated and discussed at length without excessive technical detail. Issues related to how corporations, governments, and autocratic regimes are exploiting algorithms and machine intelligence methods to influence people, laws, and markets are extensively addressed. Ethics principles in software programming and human value insertion into artificial intelligence algorithms are also discussed.

This book describes the development and use of supercomputers in the period 1960 - 1996, a time that can be called the Seymour Cray Era. For more than three decades, Cray's computer designs were seen as the yardstick against which all other efforts were measured. Initially, this yardstick was sheer computing speed. However, the supercomputer world gradually became more complex and other factors became equally important.The initial development of supercomputers was commissioned and financed by the Los Alamos and Lawrence Livermore National Laboratories, which had huge computational needs in connection with nuclear weapons development. The computers designed by Cray satisfied those needs, while these computers were also sold to a few dozen other big research organizations and weather agencies. From the 98 s, a variety of companies started to compete with the Cray designs by offering supercomputers that used a new architectural approach, MPP: massively parallel processing. This new architecture, based on using tens of thousands of relatively simple microprocessors, subsequently began to dominate high-performance computing and marked the end of the Seymour Cray Era.This book is important reading for anyone working in the area of high-performance computing, providing essential historical context for the work of a legendary pioneer and the computers he became famous for designing. It will also be valuable to students of computing history and, more generally, to readers interested in the history of science and technology. For advanced students, the book illustrates how innovation in its very essence is a socio-technical process: not just a matter of developing the "best technology," but also of making appropriate choices concerning the interaction of human and technical factors in product design.

This book outlines a methodology to develop formally verified Just-in-Time compilers. Just-in-Time compilation is a technique to execute programs, where execution is interleaved with optimizations of the program itself. These compilers often produce fast executions, so much so that their use has grown greatly for dynamic programming languages. Most modern web browsers today use Just-in-Time compilation to speed up the execution of the JavaScript programs they execute.However, the techniques used in Just-in-Time compilers can be particularly complex. This complexity can be a source of bugs and vulnerabilities. How can you make sure that your Just-in-Time compiler is bug-free? For traditional ahead-of-time compilers, many techniques have been developed to prevent compilation bugs. One such technique is formally verified compilation, where the compiler itself comes with proof that the semantics of the compiled program correspond to the semantics of the source program. But Just-in-Time compilers are more recent, less understood, and have been the target of far fewer verification efforts.To bring formal verification to Just-in-Time compilation, the book identifies a set of specific verification challenges and presents novel solutions for each of them. Such challenges include dynamic optimizations, speculative optimizations, deoptimizations, and the interleaving of interpretation and machine code generation. The author repurposes proof techniques from formally verified ahead-of-time compilers like CompCert. Following this methodology, readers can develop Just-in-Time compilers and formally prove that they behave as prescribed by the semantics of the program they execute. All proofs within the book have been mechanized in the Coq proof assistant.

Large language models can write poetry, pass bar exams, and generate fluent code. Yet they continue to fail in the domains where intelligence must be accountable: distinguishing causation from correlation, recognizing when evidence is insufficient, preserving commitments over time,and correcting their own reasoning failures. This book argues that the transition from pattern matching to genuine reasoning requires a System-2 layer grounded in coordinated diagnosis, audit, causal validation, memory, and meta-cognitive control.The volume develops this architecture from first principles through operational protocols. Semantic Anchoring (UCCT) demonstrates how contextual constraints can bind latent model representations into governed reasoning processes rather than prior-driven completion. Regulated Causal Anchoring (RCA) and RAudit diagnose sycophancy, pathological skepticism, and trace-output inconsistency without relying exclusively on ground-truth supervision. The Causal Abstraction Bridge and the CausalTSK benchmark reveal where models collapse from interventional and counterfactual reasoning back into associative prediction.Epistemic Regret Minimization (ERM) identifies causal shortcuts and failures of warranted inference, while Reinforcement Learning from Epistemic Regret (RLER) transforms those reasoning failures into a structured learning signal. Trivium introduces temporal accountability through a Causal Transaction Log, and Quadrivium integrates contextual, causal, temporal, and meta-cognitive regulation into a unified System-2 MACI architecture.The author's central thesis is that Artificial General Intelligence (AGI) will not emerge from scaling monolithic pattern-completion systems alone. AGI will require architectures capable of explaining why an answer is warranted, refusing conclusions when evidence remains indeterminate, and improving through epistemic failure.Written for researchers, advanced students, and practitioners, this book presents a framework for AI systems that are not merely impressive, but auditable, corrigible, and trustworthy. It is suitable for graduate-level courses in artificial intelligence, multi-agent systems, causal reasoning, and trustworthy AI.

Large language models can write poetry, pass bar exams, and generate fluent code. Yet they continue to fail in the domains where intelligence must be accountable: distinguishing causation from correlation, recognizing when evidence is insufficient, preserving commitments over time,and correcting their own reasoning failures. This book argues that the transition from pattern matching to genuine reasoning requires a System-2 layer grounded in coordinated diagnosis, audit, causal validation, memory, and meta-cognitive control.The volume develops this architecture from first principles through operational protocols. Semantic Anchoring (UCCT) demonstrates how contextual constraints can bind latent model representations into governed reasoning processes rather than prior-driven completion. Regulated Causal Anchoring (RCA) and RAudit diagnose sycophancy, pathological skepticism, and trace-output inconsistency without relying exclusively on ground-truth supervision. The Causal Abstraction Bridge and the CausalTSK benchmark reveal where models collapse from interventional and counterfactual reasoning back into associative prediction.Epistemic Regret Minimization (ERM) identifies causal shortcuts and failures of warranted inference, while Reinforcement Learning from Epistemic Regret (RLER) transforms those reasoning failures into a structured learning signal. Trivium introduces temporal accountability through a Causal Transaction Log, and Quadrivium integrates contextual, causal, temporal, and meta-cognitive regulation into a unified System-2 MACI architecture.The author's central thesis is that Artificial General Intelligence (AGI) will not emerge from scaling monolithic pattern-completion systems alone. AGI will require architectures capable of explaining why an answer is warranted, refusing conclusions when evidence remains indeterminate, and improving through epistemic failure.Written for researchers, advanced students, and practitioners, this book presents a framework for AI systems that are not merely impressive, but auditable, corrigible, and trustworthy. It is suitable for graduate-level courses in artificial intelligence, multi-agent systems, causal reasoning, and trustworthy AI.

Biomedical systems—such as pacemakers and automated insulin pumps—are Cyber-Physical Systems (CPSs) that must operate safely and reliably at all times. This book introduces a systematic design methodology for Medical CPSs (MCPSs) using the synchronous approach, which ensures deterministic and reactive execution—key to safety-critical performance.Through a detailed case study of a pacemaker and a modeled human heart, this book demonstrates how the synchronous approach enables accurate modeling, verification, and automated code generation. Using the SCCharts language, readers learn how to model the cardiac conduction system and a DDD-mode pacemaker, derive embedded implementations, and validate them via a synchronous heart simulator.The book then covers formal verification using the UPPAAL model checker, followed by run-time verification methods that form the foundation for preventing adversarial attacks. It concludes with references to open-source tools and future research directions relevant to the CPS community.This is a clear, practical guide to designing safe and verifiable medical cyber-physical systems.

This book is an introduction to data structures and algorithms for functional programming languages, with a focus on proofs. Starting with sorting and searching, it moves on to priority queues and advanced design and analysis techniques: dynamic programming, amortized analysis, splay trees, skew heaps and pairing heaps. The final part of the book covers a number of selected fun topics: graph algorithms, string search, Huffman's algorithm for generating optimal codes and alpha-beta pruning of game trees.The book covers both correctness (does the algorithm do what it is supposed to do?) and running time analysis (does the algorithm terminate within a specified number of steps?). It does so in a unified manner with inductive proofs about functional programs and their running time functions.What sets this book apart from existing books on algorithms is that all proofs have been machine-checked, by the proof assistant Isabelle. That is, in addition to the text in the book, which requires no knowledge of proof assistants!, the Isabelle definitions and proofs are available online. The structured nature of Isabelle proofs permits even novices to follow the high-level arguments.This book is aimed at teachers and students (it has been classroom-tested for a number of years) but is also a reference work for programmers and researchers who are interested in the (verified!) details of some algorithm or proof.

This book describes how to think about computer programs, and how to use mathematics as part of that thinking. Many books and online tutorials teach the basics of coding: the syntax of the language, and how to translate an algorithm into code. But how do you come up with that algorithm? And how can you be confident that the algorithm is correct?The first part of the book considers small programs that use a loop, and how to demonstrate their correctness using loop invariants. It also covers some algorithms and algorithmic techniques that every programmer should know. The second half of the book considers slightly larger programs. It teaches the basics of modularisation, splitting up a program into manageable chunks. It teaches about abstract datatypes, values within a program that can be treated as mathematical values: how to specify their behaviours formally; and how to treat them as abstract mathematical objects when programming. It also teaches how to use data structures to represent abstract datatypes, and what it means for such a representation to be correct. And it presents some abstract datatypes and data structures that every programmer should know.The book is aimed at those who want to obtain a better understanding of programs they work on, and so become better programmers. The target audience ranges from those who are just starting out, to professional programmers. The book aims to be pragmatic: the philosophy is to include enough formality to be convincing and to guide the programmer towards correct code, without getting bogged down in the mathematics.

This text is about compositional programming, where programs are constructed by composing prewritten software building blocks. Three modern compositional paradigms are covered, listed in order of decreasing emphasis:A Software Product Line is a design for a family of programs. Each program is composed from predefined increments of program functionality. The Linux Kernel is the largest known product line whose family size exceeds 102000 distinct programs.Model Driven Engineering is a general-purpose engineering methodology to support system design, analysis, construction, and evolution. Software designs are expressed as models. Transformations are composed to convert models into other models for analysis, to produce documentation and/or source.Streaming Applications are dataflow graphs whose nodes (called boxes) are computations with input and output data streams; boxes are wired/composed together to produce a custom program (aka software circuit). Examples are Unix pipe-and-filters and distributed stream processing.The book is aimed at both practitioners and advanced students, assuming some familiarity with programming in Java. It draws on the author's unique personal insights from over four decades of experience as an academic at a leading research university as well as a hands-on developer of software tools. Written in an engaging style, the text highlights important contributions toward principled software engineering and composable designs made by researchers in diverse areas such as formal methods, programming languages, software system development, testing and deployment, databases, and networks. Parts of the book can be read and enjoyed as a historical narrative, while others can be studied more deeply to reflect on open research challenges and opportunities. In a world where AI and machine learning offer seductive yet untapped opportunities to generate software automatically, this book is a reminder of how and why the mathematical foundations of software construction still matter.

This volume is a celebration of Leslie Valiant's scientific and intellectual achievements. It contains eight of Valiant's most impactful research works, along with accompanying contributions providing modern perspectives on these landmark papers in the context of contemporary research in complexity theory, parallel computing, computational learning theory, and machine learning. It also contains a biography of Leslie Valiant, an interview with him, and his Turing Award lecture.In 2010, Valiant received the ACM's Turing Award for "transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing." His research contributions have also been recognized with the International Mathematical Union's Nevanlinna Prize in 1986, the Knuth Prize in 1997, and many other awards.Leslie Valiant has made deep contributions to an unusually broad range of areas within theoretical computer science. Perhaps his most celebrated contribution has been his paper "A Theory of the Learnable," which gave birth to the field of computational learning theory and provided much of the intellectual foundation for the highly successful development of modern machine learning. His pioneering research in computational complexity inaugurated the study of the complexity of counting problems, defining the fundamental "counting complexity" class #P and showing that a wide range of natural counting problems are complete for this class. Valiant defined algebraic analogues of the complexity classes P and NP and established the first completeness results for these classes; this groundbreaking work opened new vistas for the field of algebraic complexity theory that continue to be explored to this day. Valiant also made seminal contributions to the field of parallel computing through his development of the highly impactful Bulk Synchronous Parallel (BSP) model as a "bridging" model between parallel software and parallel hardware, and he gave an unexpected randomized message-routing algorithm for parallel computers, which has been highly influential.

This volume is a celebration of Leslie Valiant's scientific and intellectual achievements. It contains eight of Valiant's most impactful research works, along with accompanying contributions providing modern perspectives on these landmark papers in the context of contemporary research in complexity theory, parallel computing, computational learning theory, and machine learning. It also contains a biography of Leslie Valiant, an interview with him, and his Turing Award lecture.In 2010, Valiant received the ACM's Turing Award for "transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing." His research contributions have also been recognized with the International Mathematical Union's Nevanlinna Prize in 1986, the Knuth Prize in 1997, and many other awards.Leslie Valiant has made deep contributions to an unusually broad range of areas within theoretical computer science. Perhaps his most celebrated contribution has been his paper "A Theory of the Learnable," which gave birth to the field of computational learning theory and provided much of the intellectual foundation for the highly successful development of modern machine learning. His pioneering research in computational complexity inaugurated the study of the complexity of counting problems, defining the fundamental "counting complexity" class #P and showing that a wide range of natural counting problems are complete for this class. Valiant defined algebraic analogues of the complexity classes P and NP and established the first completeness results for these classes; this groundbreaking work opened new vistas for the field of algebraic complexity theory that continue to be explored to this day. Valiant also made seminal contributions to the field of parallel computing through his development of the highly impactful Bulk Synchronous Parallel (BSP) model as a "bridging" model between parallel software and parallel hardware, and he gave an unexpected randomized message-routing algorithm for parallel computers, which has been highly influential.

This book explores the profound legacy of Alan Turing, and how his five great ideas have been developed by the winners of the Turing Prize to shape the digital world we live in today.These five groundbreaking concepts—universal computability and insolvability, cryptography, electronic digital computers and software, artificial intelligence (AI), and computational biology—serve as the pillars of the narrative.Turing's Children makes the complex ideas in the work of the Turing prize winners accessible to a broad audience. It traces the evolution of these ideas from abstract mathematical principles to their real-world applications, demonstrating their influence on everyday life. Readers will discover how Turing's legacy is woven into the fabric of modern technology: from the smartphones in our pockets and secure online banking, to the development of life-saving drugs and the conversational abilities of AI systems like ChatGPT.The book weaves together historical anecdotes, profiles of pioneering scientists, and vivid examples of current innovations. It offers a comprehensive view of how Turing's vision continues to inspire breakthroughs across science and technology. Turing's Children reveals the enduring relevance of Turing's ideas and the ongoing quest to push the boundaries of what machines—and humanity—can achieve.

Today's large language models excel at pattern recall yet falter on long-range planning, self-critique, context loss, and the tendency of maximum-likelihood training to reward popularity over quality. MACI offers a promising route to AGI by orchestrating specialized LLM agents through explicit protocols rather than enlarging a single model. Several modules remedy complementary weaknesses: adversarial-collaborative debate surfaces hidden assumptions; critical-reading rubrics filter incoherent arguments; information-theoretic signals steer dialogue quantitatively; transactional memory enables reliable long-horizon execution; and a dual-agent ethical court adjudicates outputs. Crucially, MACI also modulates linguistic behavior, tuning each agent's contentiousness and emotional tone, so the collective explores ideas from contrasting, affect-aware perspectives before converging.Fourteen aphorisms distill the framework's philosophy, including "Intelligence emerges from regulated collaboration, not isolated brilliance" and "Exploration must remain in tension with exploitation." Across healthcare diagnosis, investment support, scheduling, supply-chain management, and news-bias mitigation, MACI ensembles deliver significant improvements in reasoning depth, planning horizon, and reliability compared with similar-sized single models. By uniting structured debate, information-theoretic coordination, persistent memory, affect-aware discourse, and deliberative ethics, MACI demonstrates that rigorously validated multi-agent collaboration provides a practical, interpretable path toward robust general intelligence.

Today's large language models excel at pattern recall yet falter on long-range planning, self-critique, context loss, and the tendency of maximum-likelihood training to reward popularity over quality. MACI offers a promising route to AGI by orchestrating specialized LLM agents through explicit protocols rather than enlarging a single model. Several modules remedy complementary weaknesses: adversarial-collaborative debate surfaces hidden assumptions; critical-reading rubrics filter incoherent arguments; information-theoretic signals steer dialogue quantitatively; transactional memory enables reliable long-horizon execution; and a dual-agent ethical court adjudicates outputs. Crucially, MACI also modulates linguistic behavior, tuning each agent's contentiousness and emotional tone, so the collective explores ideas from contrasting, affect-aware perspectives before converging.Fourteen aphorisms distill the framework's philosophy, including "Intelligence emerges from regulated collaboration, not isolated brilliance" and "Exploration must remain in tension with exploitation." Across healthcare diagnosis, investment support, scheduling, supply-chain management, and news-bias mitigation, MACI ensembles deliver significant improvements in reasoning depth, planning horizon, and reliability compared with similar-sized single models. By uniting structured debate, information-theoretic coordination, persistent memory, affect-aware discourse, and deliberative ethics, MACI demonstrates that rigorously validated multi-agent collaboration provides a practical, interpretable path toward robust general intelligence.

As the global mental health crisis intensifies, the gap between the need for and the availability of quality care continues to widen. This book explores a promising and innovative solution: human–artificial intelligence (AI) collaboration. Drawing inspiration from years of research in AI, human–computer interaction, and psychology, this work presents a new paradigm for mental healthcare that focuses on augmenting human capabilities with AI rather than replacing them.The central aim of this book is to demonstrate, through rigorous scientific evaluation, how AI can empower both support providers and support seekers. For providers, particularly untrained but well-intentioned peer-to-peer mental health supporters, the book introduces a reinforcement learning system that provides real-time feedback to improve crucial skills like empathetic communication. For individuals seeking mental health support, it details an AI-powered tool that makes evidence-based self-guided interventions, such as cognitive restructuring, more accessible and effective by reducing cognitive and emotional barriers.Beyond developing these systems, the book establishes a novel and essential framework for their systematic evaluation. It provides a guide for conducting clinical trials for AI-based interventions and presents a computational analysis that critically assesses the behavior of large language models (LLMs) in therapeutic roles, revealing how they can mimic low-quality human practices.By bridging psychological principles with advanced machine learning, this book provides a blueprint for developing, implementing, and evaluating effective human–AI collaboration systems. It is essential reading for researchers in HCI and AI, clinical psychologists, practitioners, and policymakers dedicated to shaping the future of accessible and high-quality mental health support.

As the global mental health crisis intensifies, the gap between the need for and the availability of quality care continues to widen. This book explores a promising and innovative solution: human–artificial intelligence (AI) collaboration. Drawing inspiration from years of research in AI, human–computer interaction, and psychology, this work presents a new paradigm for mental healthcare that focuses on augmenting human capabilities with AI rather than replacing them.The central aim of this book is to demonstrate, through rigorous scientific evaluation, how AI can empower both support providers and support seekers. For providers, particularly untrained but well-intentioned peer-to-peer mental health supporters, the book introduces a reinforcement learning system that provides real-time feedback to improve crucial skills like empathetic communication. For individuals seeking mental health support, it details an AI-powered tool that makes evidence-based self-guided interventions, such as cognitive restructuring, more accessible and effective by reducing cognitive and emotional barriers.Beyond developing these systems, the book establishes a novel and essential framework for their systematic evaluation. It provides a guide for conducting clinical trials for AI-based interventions and presents a computational analysis that critically assesses the behavior of large language models (LLMs) in therapeutic roles, revealing how they can mimic low-quality human practices.By bridging psychological principles with advanced machine learning, this book provides a blueprint for developing, implementing, and evaluating effective human–AI collaboration systems. It is essential reading for researchers in HCI and AI, clinical psychologists, practitioners, and policymakers dedicated to shaping the future of accessible and high-quality mental health support.