Comments Off
If you’re a regular reader of Boing Boing you might have seen this beautiful homemade Turing machine that tinkerer Mike Davey put together (it’s definitely worth watching the video). For those who don’t know, Turing machines are theoretical idealizations of computers. While not intended to be practical, they do allow mathematicians to construct rigorous proofs about what can be computed and what cannot. And now, you can experiment with them directly on Wolfram|Alpha!
To begin with, let’s ask Wolfram|Alpha to simulate the program that Mike Davey used in his video, a binary counter. Using Stephen Wolfram‘s notation, this one is 2-state 3-color machine number 1317953. It “counts” in binary, and marks each successive integer when the machine’s head returns to the initial position. We can more easily see how it computes the sequence 1,2,3,4,5… by only showing the steps when it returns to the center column.
Next we can try a Turing machine at random from the infinite “universe” of possible machines. Let’s say we find this particular Turing machine, and want to see how it behaves on different input tapes. We can try a tape filled with random colors, or a finite tape that wraps around, or a tape with an infinite pattern on it, or even a combination of the above. We can also try a random Turing machine that operates with many colors, such as “random 7-color Turing machine”.
Wolfram|Alpha also knows about various famous machines. For example, the Wolfram 2,3 Turing machine, shown in the image below, was proved by Alex Smith to be universal, or capable of simulating any computation (a feat that won him $25,000 from Wolfram Research). We can see what this machine does on a particular input tape, such as “evolution of Wolfram 2,3 on single 0 then all 2s for 60 steps”. For a better view, we can ask Wolfram|Alpha to compress its visualization in various ways, such as “wolfram 2,3 on blank tape, left-compressed”, or “wolfram 2,3 on blank tape, every 5th step”.
One class of famous Turing machines are called busy beavers. If there were a Turing Olympics, these machines would be the long-distance gold medalists—their job is to write as many colored cells as possible before eventually halting. In the 2-state 2-color rulespace, the current champion only holds out for 6 steps before stopping. More-complex Turing machines, with more colors and more states, can do better. It is easy for a Turing machine to go on forever, but to halt after exactly 47176870 steps is no mean feat, as this 5-state 2-color busy beaver does. And this 3-state 3-color machine, discovered by father-son team Terry and Shawn Ligocki, actually goes on for 119 quadrillion steps before halting!
That’s all from us, but there’s plenty more for you to discover. See the examples page for more things to try! Happy hunting!
Wonderful. As “computation” becomes more central a topic, these tools of theoretical practice are important for education of students of all ages 😀