8 citations · 17 across the 10 of their papers we have counts for
4 papers · 1 filter
Combinators: A Centennial View
Stephen Wolfram
We give a modern computational introduction to the S,K combinators invented by Moses Schönfinkel in 1920, and present a variety of new results and ideas about combinators. We explo…
After 100 Years, Can We Finally Crack Post's Problem of Tag? A Story of Computational Irreducibility, and More
Stephen Wolfram
Empirical, theoretical and historical aspects of Post's "problem of tag" from 1921 are explored. Evidence of strong computational irreducibility is found. Despite their determinist…
Multiway Turing Machines
Stephen Wolfram
Multiway Turing machines (also known as nondeterministic Turing machines or NDTMs) with explicit, simple rules are studied. Even very simple rules are found to generate complex beh…
Combinators and the Story of Computation
Stephen Wolfram
We discuss the role of combinators in the development of the modern conception of computation over the course of the past century. We describe how ideas about formalism and mathema…