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.

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.

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 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 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.