Today in History – May 28, 1936 – “Turing Machine” paper submitted, his first paper on decidability. Turing’s achievements at Cambridge had been on account of his work in probability theory. However, he had been working on the decidability questions since attending Max Newman‘s course on the foundations of mathematics. In 1936 he published “On Computable Numbers, with an application to the Entscheidungsproblem.” It is in this paper that Turing introduced an abstract machine, now called a “Turing machine”, which moved from one state to another using a precise finite set of rules (given by a finite table) and depending on a single symbol it read from a tape.

This is a classic paper that I hand out every year to students in my automata theory class to read about and write a summary. Turing machines are abstract, however, today students can get hands-on experience with Turing machines in a number of ways. First there are many simulation tools available for experimenting with Turing machines. I’ll name just a few such as Turing’s World (now out of print), Deus Ex Machina used in Taylor’s book “Models of Computation and Formal Languages, and JFLAP. JFLAP is an extensive tool for building and simulating finite state machines, pushdown automata, and several versions of Turing machines. In addition one can experiment with LL and SLR parsing, L-Systems, and several construction proofs such as converting a NFA to a DFA to a minimal state DFA, or converting an NPDA to a CFG.

For example, shown below is a snapshot of a Turing machine for a^nb^nc^n built in JFLAP. With such tools, one can watch a trace of an input string being processed in the Turing machine.

A second way students can experience Turing machines is to build an edible Turing machine out of blueberry muffins and icing. Here is an example of such a Turing machine built in 2003 for the language ww, where the alphabet is a and b. Don’t worry about the muffins being stale, they all got eaten.

Check out the Engineering Pathway’s educational resources on the Turing Machine, Alan Turing, and history of computing. For more educational resources, see our computer science education and computer engineering education community pages. The Engineering Pathway also hosts Engineering Education communities in all ABET-accredited disciplines.