AUTHOR PAGE
taliesin-beynon
Taliesin Beynon
Blog Posts from this author:
May 6, 2010– 2

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”. More »