TAG: Turing Machines
June 23, 2010– 9

Today (June 23, 2010) would have been Alan Turing‘s 98th birthday—if he had not died in 1954, at the age of 41.

I never met Alan Turing; he died five years before I was born. But somehow I feel I know him well—not least because many of my own intellectual interests have had an almost eerie parallel with his.

And by a strange coincidence, Mathematica‘s “birthday” (June 23, 1988) is aligned with Turing’s—so that today is also the celebration of Mathematica‘s 22nd birthday.

I think I first heard about Alan Turing when I was about eleven years old, right around the time I saw my first computer. Through a friend of my parents, I had gotten to know a rather eccentric old classics professor, who, knowing my interest in science, mentioned to me this “bright young chap named Turing” whom he had known during the Second World War.

One of the classics professor’s eccentricities was that whenever the word “ultra” came up in a Latin text, he would repeat it over and over again, and make comments about remembering it. At the time, I didn’t think much of it—though I did remember it. Only years later did I realize that “Ultra” was the codename for the British cryptanalysis effort at Bletchley Park during the war. In a very British way, the classics professor wanted to tell me something about it, without breaking any secrets. And presumably it was at Bletchley Park that he had met Alan Turing.

A few years later, I heard scattered mentions of Alan Turing in various British academic circles. I heard that he had done mysterious but important work in breaking German codes during the war. And I heard it claimed that after the war, he had been killed by British Intelligence. At the time, at least some of the British wartime cryptography effort was still secret, including Turing’s role in it. I wondered why. So I asked around, and started hearing that perhaps Turing had invented codes that were still being used.

I’m not sure where I next encountered Alan Turing. Probably it was when I decided to learn all I could about computer science—and saw all sorts of mentions of “Turing machines”. But I have a distinct memory from around 1979 of going to the library, and finding a little book about Alan Turing written by his mother, Sara Turing.

And gradually I built up quite a picture of Alan Turing and his work. And over the 30 years that have followed, I have kept on running into Alan Turing, often in unexpected places. More »

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 »