Chocoholic subtraction

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 ...

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 instructions below. Start at the M on the very left of the pattern above.

Red lolly

if your lolly is RED and the chocolate is MILK then the new chocolate is MILK, the new lolly is RED and you move to the RIGHT

if your lolly is RED and the chocolate is DARK then the new chocolate is DARK, the new lolly is ORANGE and you move to the RIGHT

Orange lolly

if your lolly is ORANGE and the chocolate is MILK then the new chocolate is MILK, the new lolly is PINK and you move to the RIGHT

if your lolly is ORANGE and the chocolate is DARK then the new chocolate is DARK, the new lolly is ORANGE and you move to the RIGHT

Pink lolly

if your lolly is PINK and the chocolate is MILK then the new chocolate is MILK, the new lolly is PINK and you move to the RIGHT

if your lolly is PINK and the chocolate is DARK then the new chocolate is MILK, the new lolly is GREEN and you move to the RIGHT

Green lolly

if your lolly is GREEN and the chocolate is MILK then the new chocolate is MILK, the new lolly is VIOLET and you move to the LEFT

if your lolly is GREEN and the chocolate is DARK then the new chocolate is DARK, the new lolly is BLUE and you move to the LEFT

Blue lolly

if your lolly is BLUE and the chocolate is MILK then the new chocolate is MILK, the new lolly is BLUE and you move to the LEFT

if your lolly is BLUE and the chocolate is DARK then the new chocolate is MILK, the new lolly is PINK and you move to the RIGHT

Violet lolly

if your lolly is VIOLET and the chocolate is MILK then the new chocolate is MILK, the new lolly is VIOLET and you move to the LEFT

if your lolly is VIOLET and the chocolate is DARK then the new chocolate is MILK, the new lolly is NONE and you STOP

The answer!

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.