The Wolfram|Alpha Blog is now part of the Wolfram Blog. Join us there for the latest on Wolfram|Alpha and other Wolfram offerings »
Taliesin Beynon

Tinkering with Turing Machines in Wolfram|Alpha

May 6, 2010 —
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.

Turing machine 1317953 center-compressed

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โ€.

Wolfram's 2-state 3-color Turing machine

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!

2 Comments

Wonderful. As “computation” becomes more central a topic, these tools of theoretical practice are important for education of students of all ages ๐Ÿ˜€

Posted by ImaginaryUnit May 11, 2010 at 2:50 pm

Great !
Turing Machine Explained

Posted by Dr. Rajeev Shrivastava February 1, 2011 at 9:22 am