Your Own Turing Machine: Part II
Last time we built a Turing machine as a rainy-day project. Today, I’ll show you how to use it to do something useful, like add two numbers together.
Single-Head Addition
Now that we have our Turing machine, it’s time to write some programs for it! Last time, we wrote a simple incrementer to learn how the machine works. This time, we’ll write something (slightly) more complicated. Let’s try some basic arithmetic, starting with addition.
First, you will need to set up your Turing machine. Since we’re still working with only one tape, we’ll need to put both numbers we want to add on the same tape. Separate each number with a blank. For example, if I wanted to add the numbers 3 + 5, my tape would read 1-1-1-0-1-1-1-1-1. As before, place the head at the start of the first number.
Let’s assume we want to overwrite the tape with the answer. So, when we start the program, the tape will contain the two numbers we want to add. When we finish running the program, the tape will contain the sum of the two numbers.
There are lots of ways we could go about adding the two numbers, but there’s one very obvious way to do it. Squish the two numbers together! Sure, it sounds cheesy, but it’s a pretty efficient way to accomplish our task.
Here’s the outline:
– Move the head past the first number to the blank.
– Move the head past the blank.
– Move the head to the last digit of the second number.
– Remove the one and change it to a blank.
– Move the head to the blank between the numbers.
– Write a one.
– Reset the head to the start.
Each of these steps can be accomplished with simple loops to move past the written values, similar to the incrementer. However, we’ll need to add a little more logic to our loops, to handle the case when either operand is a zero.
Watch the adder program in action
Start by moving the head past the first number. This loop is similar to the one in the incrementer, however, we’ll need to “flip the loop” by moving the head before we check for the value. That way, we’ll be sure our head ends up where we mean it to be, regardless of what the first number is.
#1: Move the head right one space. Go to the next instruction.
#2: If the current value is 1, go to instruction #1. Otherwise, go to instruction number #3.
Next, we must move past the blank:
#3: Move the head right one space. Go to the next instruction.
Once past the blank, we need to find our way to the end of the second number. Use a loop to move the head past the second number, then retreat one space so that the head is on the last digit:
#4: If the current value is 1, go to instruction #5. Otherwise, go to instruction #6.
#5: Move the head right one space. Go to instruction #4.
#6: Move the head left one space. Go to the next instruction.
Now, we need to replace the last digit with a blank… but not so fast! What if the second number is a zero? We need to handle this special case. If the second number is a zero, we’ll just skip to the end and reset the head. Otherwise, we’ll merge the two numbers.
#7: If the current value is a 1, go to instruction #8. Otherwise, go to instruction #13.
#8: Write a blank. Go to the next instruction.
#9: Move the head left one space. Go to the next instruction.
Now, it is time to start moving the head back in the opposite direction. Seek to the left until we find the blank separating the values:
#10: If the current value is a 1, go to instruction #11. Otherwise, go to instruction #12.
#11: Move the head left one space. Go to instruction #10.
To combine the numbers together, replace the blank with a 1. This doesn’t change the value, because we already removed a 1 from the end of the second number:
#12: Write a 1. Go to the next instruction.
#13: Move the head left one space. Go to the next instruction.
We’ve calculated the sum! The tape should now read the sum of the two numbers. But, for good practice, we aren’t quite done… to do this right, we want to make sure we restore the head so that it points at the start of the value written to the tape. We can do this exactly the same way as we did in the incrementer, by moving until we find a blank, then stepping to the right.
#14: If the current value is a 1, go to instruction #15. Otherwise, go to instruction #16.
#15: Move the head to the left one space. Go to instruction #14.
#16: Move the head right one space. End program.
And we’re done. Try it out and see how it works!
Here’s the complete program listing:
-Adder-
#1: Move the head right one space. Go to the next instruction.
#2: If the current value is 1, go to instruction #1. Otherwise, go to instruction number #3.
#3: Move the head right one space. Go to the next instruction.
#4: If the current value is 1, go to instruction #5. Otherwise, go to instruction #6.
#5: Move the head right one space. Go to instruction #4.
#6: Move the head left one space. Go to the next instruction.
#7: If the current value is a 1, go to instruction #8. Otherwise, go to instruction #13.
#8: Write a blank. Go to the next instruction.
#9: Move the head left one space. Go to the next instruction.
#10: If the current value is a 1, go to instruction #11. Otherwise, go to instruction #12.
#11: Move the head left one space. Go to instruction #10.
#12: Write a 1. Go to the next instruction.
#13: Move the head left one space. Go to the next instruction.
#14: If the current value is a 1, go to instruction #15. Otherwise, go to instruction #16.
#15: Move the head to the left one space. Go to instruction #14.
#16: Move the head right one space. End program.
Multi-Head Addition
A multiple-head Turing machine doesn’t have any computational advantage over a single-head Turing machine–anything you can compute on one, you can compute on the other–but multi-head Turing machines can sometimes make your programs easier to conceptualize, especially for complicated algorithms.
From here on out, we’ll use a multi-head machine. To show how a multi-head\multi-tape machine works in comparison to a single-head machine, we’ll implement addition again, this time using three heads and three tapes instead of one.
To setup your Turing machine for a multi-headed operation, we need to create one tape for each head. Lay out your tape index cards in three rows. Place one head above each tape row.
The first and second tapes will hold our two “addends”, or numbers we want to add together. Place the first number you want to add in the first tape. Place the second number you want to add in the second tape. The third tape will hold the result. Set the third tape to blank.
The outline for a multi-head addition operation is much easier to follow:
– Copy the value from the first tape to the third tape
– Append the value from the second tape to the third tape
– Reset all three heads
Not only is this program more intuitive to read, it also eliminates the need to check for zero values.
Example of the multi-head adder
Let’s walk through the code:
#1: If the current value of head #1 is 1, then go to instruction #2. Otherwise, go to instruction #5.
#2: With head #3, write a 1.
#3: Move head #3 to the right one space.
#4: Move head #1 to the right one space. Go to instruction #1.
What this segment does is copy the value of the first tape to the third tape. Every time head #1 reads a 1, head #3 writes a 1. This segment keeps looping until tape #1 runs out of 1’s.
The next section is essentially the same, except that it copies data from tape #2 to tape #3:
#5: If the current value of head #2 is 1, then go to instruction #6. Otherwise, go to instruction #9.
#6: With head #3, write a 1.
#7: Move head #3 to the right one space.
#8: Move head number #2 to the right one space. Go to instruction #5.
Tape #3 now holds our result! All that’s left is to reset the heads to start. Here is the complete listing:
-Multi-head Adder-
#1: If the current value of head #1 is 1, then go to instruction #2. Otherwise, go to instruction #5.
#2: With head #3, write a 1.
#3: Move head #3 to the right one space.
#4: Move head #1 to the right one space. Go to instruction #1.
#5: If the current value of head #2 is 1, then go to instruction #6. Otherwise, go to instruction #9.
#6: With head #3, write a 1.
#7: Move head #3 to the right one space.
#8: Move head number #2 to the right one space. Go to instruction #5.
#9: Move head #1 to the left one space.
#10: If the current value of head #1 is 1, go to instruction #11. Otherwise, go to instruction #12.
#11: Move head #1 to the left one space. Go to instruction #10.
#12: Move head #1 to the right one space.
#13: Move head #2 to the left one space.
#14: If the current value of head #2 is 1, go to instruction #15. Otherwise, go to instruction #16.
#15: Move head #2 to the left one space. Go to instruction #14.
#16: Move head #2 to the right one space.
#17: Move head #3 to the left one space.
#18: If the current value of head #3 is one, go to instruction #17. Otherwise, go to instruction #19.
#19: Move head #3 to the right one space. End program.
Subtraction
Hopefully, by now you’re starting to get a grasp on how to write simple programs for your Turing machine.
I’m not going to post a complete program listing for subtraction, as it’s pretty much the same as addition (if you can’t figure it out, ask me and I’ll help you out). If you build a three-tape setup, where tapes #1 and #2 store the numbers you want to subtract and tape #3 stores the result, then you can implement subtraction by copying the value from tape #1 to tape #3, then decrementing tape #3 by the value of tape #2. Very straight-forward.
There’s only one gotcha you need to look out for in subtraction: what happens if the second number is larger than the first number? You could, of course, choose to ignore this case. A better thing to do would be to finally bust out those paperclips and use the state register. If you decrement a value from tape #3, but the current value of tape #3 is already zero, change the state by adding a paperclip to indicate that the result you are writing on tape #3 is a negative value. If you don’t want to use a state register, you can accomplish the same thing by using the first cell on tape #3 to indicate whether the value is positive or negative. If the value is blank, the result is positive. If the value is 1, the result is negative. That is more-or-less what modern computers do. In any case, there are lots of good ways to handle the scenario–the important thing is that you check for it.
Questions? Ideas? More programs you’d like to see? Post a comment!
Tags: addition, computer, math, programming, subtraction, turing, turing machine