Combinators: A Centennial View

by Stephen Wolfram

Overview

Combinators have inspired ideas about computation ever since they were first invented in 1920, and in this innovative book, Stephen Wolfram provides a modern view of combinators and their significance. Informed by his work on the computational universe of possible programs and on computational language design, Wolfram explains new and existing ideas about combinators with unique clarity and stunning visualizations, as well as provides insights on their historical connections and the curious story of Moses Schönfinkel, inventor of combinators. Though invented well before Turing machines, combinators have often been viewed as an inaccessibly abstract approach to computation. This book brings them to life as never before in a thought-provoking and broadly accessible exposition of interest across mathematics and computer science, as well as to those concerned with the foundations of formal and computational thinking, and with the history of ideas.

Product Details

ISBN-13:	9781579550431
Publisher:	Wolfram Media, Inc.
Publication date:	06/17/2021
Pages:	376
Product dimensions:	7.00(w) x 10.00(h) x 1.00(d)

About the Author

Stephen Worfram is a distinguished scientist and best-selling author, and the creator of some of the world's most respected software systems, including Mathematica, Wolfram/Alpha and the Wolfram Language. For more than 30 years he has been the CEO of the global technology company Wolfram Research.

Table of Contents

Preface vii

Combinators: A Centennial View 3

Ultimate Symbolic Abstraction 3

Computing with Combinators 6

A Hundred Years Later… 12

Combinators in the Wild: Some Zoology 17

Visualizing Combinators 34

Updating Schemes and Multiway Systems 54

The Question of Evaluation Order 72

The World of the S Combinator 87

Causal Graphs and the Physicalization of Combinators 102

Combinator Expressions as Dynamical Systems 120

Equality and Theorem Proving for Combinators 125

Lemmas and the Structure of Combinator Space 133

Empirical Computation Theory with Combinators 145

The Future of Combinators 157

Historical & Other Notes 159

Combinators and the Story of Computation 165

The Abstract Representation of Things 165

What Is Mathematics-and Logic-Made Of? 167

Combinators Arrive 171

What Is Their Mathematics? 181

Gödel's Theorem and Computability 183

Lambda Calculus 186

Practical Computation 191

Combinators in Culture 195

Designing Symbolic Language 198

Combinators in the Computational Universe 203

Combinators All the Way Down? 208

Where Did Combinators Come From? Hunting the Story of Moses Schönfinkel 213

Decembers 1920 213

Who Was Moses Schönfinkel? 215

The Beginning of the Story 217

Going to College in Odessa 222

Gottingen, Center of the Mathematical Universe 228

Problems Are Brewing 234

The 1924 Paper 241

The "1927" Paper 247

To Moscow and Beyond… 257

Other Schönfinkels… 262

Haskell Curry 265

Schönfinkel Rediscovered 274

What Should We Make of Schönfinkel? 275

A Little Closer to Finding What Became of Moses Schönfinkel, Inventor of Combinators 281

1920, 2020 and a $20,000 Prize: Announcing the S Combinator Challenge 297

Hiding in Plain Sight for a Century? 297

The Basic 5etup 300

The Operation of the S Combinator Challenge 303

Excerpts from A New Kind of Science (2002) 307

Section 10: Symbolic Systems 307

Notes 310

Section 12: Universality in Turing Machines and Other Systems 315

Notes 319

A Bibliography of Combinators 325

Foundational Documents 325

Books 325

Surveys & Summaries 326

Combinators as Symbolic Expressions 327

Combinators as Mathematical Constructs 334

Combinator Computation 341

Extensions & Applications 350

Confusing Issues 352

Index 357