Video work logs
January 5, 2021
January 9, 2021
January 10, 2021
January 11, 2021
January 18, 2021
January 23, 2021
January 25, 2021
January 28, 2021
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. And as I’ve found so often in the computational universe, even cases with some of the very simplest possible rules yield some significant surprises….
Ordinary vs. Multiway Turing Machines
An ordinary Turing machine has a rule such as
✕

that specifies a unique successor for each configuration of the system (here shown going down the page starting from an initial condition consisting of a blank tape):
✕
