8 citations · 12 across the 5 of their papers we have counts for
6 papers
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…
Exploring Rulial Space: The Case of Turing Machines
Stephen Wolfram
As an example of the concept of rulial space, we explore the case of simple Turing machines. We construct the rulial multiway graph which represents the behavior of all possible Tu…
A Class of Models with the Potential to Represent Fundamental Physics
Stephen Wolfram
A class of models intended to be as minimal and structureless as possible is introduced. Even in cases with simple rules, rich and complex behavior is found to emerge, and striking…