A Turing machine can be used to do any computation, as long as you get its program right. Let’s create a program to do something simple to see how to do it. Our program will subtract two numbers.
The first thing we need to do is to choose a code for what the patterns of chocolates mean. To encode the two numbers we want to subtract we will use sequences of dark chocolates separated by milk chocolates, one sequence for each number. The more dark chocolates before the next milk chocolate the higher the number will be. For example if we started with the pattern laid out as below then it would mean we wanted to compute 4 – 3. Why? Because there is a group of four dark chocolates and then after some milk chocolates a group of three more.
M M M D D D D M M D D D M M M M …
(M = Milk chocolate, D = Dark chocolate)
Here is a program that does the subtraction if you follow it when the pattern is laid out like that. It works for any two numbers where the first is the bigger. The answer is given by the final pattern. Try it yourself! Begin with a red lolly and follow the table below. Start at the M on the very left of the pattern above.
From the above starting pattern our subtraction program would leave a new pattern:
M M M D M M M M M M M M M M M …
There is now just a single sequence of dark chocolates with only one chocolate in it. The answer is 1!
Try lining up some chocolates and following the instructions yourself to see how it works.
Could you make the most powerful computer ever created…out of chocolates? It’s actually quite easy. You just have to have enough chocolates (and some lollies). It is one of computer science’s most important achievements.
Imagine you are in a sweet factory. Think big – think Charlie and the Chocolate Factory. A long table stretches off into the distance as far as you can see. On the table is a long line of chocolates. Some are milk chocolate, some dark chocolate. You stand in front of the table looking at the very last chocolate (and drooling). You can eat the chocolates in this factory, but only if you follow the rules of the day. (There are always rules!)
The chocolate eating rules of the day tell you when you can move up and down the table and when you can eat the chocolate in front of you. Whenever you eat a chocolate you have to replace it with another from a bag that is refilled as needed (presumably by Oompa-Loompas).
You also hold a single lolly. Its colour tells you what to do (as dictated by the rules of the day, of course). For example, the rules might say holding an orange one means you move left, whereas a red one means you move right. Sometimes the rules will also tell you to swap the lolly for a new one.
The rules of the day have to have a particular form. They first require you to note what lolly you are holding. You then check the chocolate on the table in front of you, eat it and replace it with a new one. You pick up a lolly of the colour you are told. You finally move left, move right or finish completely. A typical rule might be:
If you hold an orange lolly and a dark chocolate is on the table in front of you, then eat the chocolate and replace it with a milk one. Swap the lolly for a pink one. Finally, move one place to the left.
A shorthand for this might be: if ORANGE, DARK then MILK, PINK, LEFT.
You wouldn’t just have one instruction like this to follow but a whole collection with one for each situation you could possibly be in. With three colours of lollies, for example, there are six possible situations to account for: three for each of the two types of chocolate.
As you follow the rules you gradually change the pattern of chocolates on the table. The trick to making this useful is to make up a code that gives different patterns of chocolates different meanings. For example, a series of five dark chocolates surrounded by milk ones might represent the number 5.
See Chocoholic Subtraction for a set of rules that subtracts numbers for you as a result of shovelling chocolates into your face.
Our chocolate machine is actually a computer as powerful as any that could possibly exist. The only catch is that you must have an infinitely long table!
By powerful we don’t mean fast, but just that it can compute anything that any other computer could. By setting out the table with different patterns at the start, it turns out you can compute anything that it is possible to compute, just by eating chocolates and following the rules. The rules themselves are the machine’s program.
This is one of the most famous results in computer science. We’ve described a chocoholic’s version of what is known as a Turing machine because Alan Turing came up with the idea. The computer is the combination of the table, chocolates and lollies. The rules of the day are its program, the table of chocolates is its memory, and the lollies are what is known as its ‘control state’. When you eat chocolate following the rules, you are executing the program.
Sadly Turing’s version didn’t use chocolates – his genius only went so far! His machine had 1s and 0s on a tape instead of chocolates on a table. He also had symbols instead of lollies. The idea is the same though. The most amazing thing was that Alan Turing worked out that this machine was as powerful as computers could be before any actual computer existed. It was a mathematical thought experiment.
So, next time you are scoffing chocolates at random, remember that you could have been doing some useful computation at the same time as making yourself sick.