Turing Machines were invented by Alan Turing before the first computers were created as a model of computation. It strips the idea of what computation is down to a very simple idea of a machine.
Here are ideas and resources for teaching Turing Machines. See also the teach computing ISAAC Resources for a more traditional description and resources linked to specific exam boards.
The Chocolate Turing Machine
Make working Turing Machines out of chocolate (symbols after all can be anything). There is no reason why a computer shouldn’t taste nice too.
Read the original cs4fn article in issue 14 or download just the article here
Slides about Turing Machines
The following are the slides delivered at the CAS London Conference Feb 2020
Resources Pack for Building a Chocolate Turing Machine
Sadly you will have to supply your own chocolate (and chocolate factory) as I haven’t found a way to provide downloadable chocolate (sorry)
Sample Instruction Tables can be found in the above slides.
Of course it doesn’t have to be chocolate – anything can be used as symbols and state values (eg why not use Lego or similar instead).
Role Playing a Turing Machine
Another way to illustrate a Turing Machine and explain the concepts is by having students act out a role playing version,
Have a series of students act as the infinite tape. They stand in a line holding cards with symbols on, initially all BLANK (or use a specific symbol for this). Strictly, you need an infinite line of students. Despite rising class sizes most schools will not manage this so explain to the class that they have to imagine this (and more students can always be added infinitely as needed.
A further person acts as the State Register recording the current state. They hold a coloured card. Initially, this is the start state (for my Turing Machines, I use GREEN as the start state.)
Use a hat for the Tape Head. Place it on the head of the person in the tape who is in the initial position.
Show the instruction table as a slide.
Set up the initial tape by replacing some blanks for symbol cards (eg 1).
Now run the Turing Machine, by finding the row in the Instruction Table that matches the state register colour and symbol on the tape under the tape head (hat). Change the symbol, move the head (hat) and change the state accordingly.
Keep doing this until you hit a stop state (which will have no corresponding rows in the table.
As you step through the program, explain what is happening, and how the Turing Machine is working. Encourage students to ask questions.
A good follow up activity is to let groups of students now dry run Turing Machines themselves (either on paper or as chocolate machines). This will aid understanding and help uncover misunderstandings. They can then write their own to do simple tasks.
A short story about Turing Machines
More to Come.
Brought to you by cs4fn, Queen Mary University of London, with funding from the Institute of Coding, CAS London and the NCCE/Isaac Computing