Institute Output
After 100 Years, Can We Finally Crack Post’s Problem of Tag? A Story of Computational Irreducibility, and More
Stephen Wolfram
For Post, the failure to crack his system derailed his whole intellectual worldview. For me now, the failure to crack Post’s system in a sense just bolsters my worldview—providing yet more indication of the strength and ubiquity of computational irreducibility and the Principle of Computational Equivalence.
Multiway Turing Machines
Stephen Wolfram
Over the years I’ve studied the simplest ordinary Turing machines quite a bit, but I’ve barely looked at multiway Turing machines (also known as nondeterministic Turing machines or NDTMs). Recently, though, I realized that multiway Turing machines can be thought of as “maximally minimal” models both of concurrent computing and of the way we think about quantum mechanics in our Physics Project. So now this piece is my attempt to “do the obvious explorations” of multiway Turing machines.
Exploring Rulial Space: The Case of Turing Machines
Stephen Wolfram
Let’s say we find a rule that reproduces physics. A big question would then be: “Why this rule, and not another?” I think there’s a very elegant potential answer to this question, that uses what we’re calling rule space relativity—and that essentially says that there isn’t just one rule: actually all possible rules are being used, but we’re basically picking a reference frame that makes us attribute what we see to some particular rule. In other words, our description of the universe is a sense of our making, and there can be many other—potentially utterly incoherent—descriptions, etc.