Creating a Turing Machine in Python – Part 3

Now that our Turing machine is up and running, it’s time to add some more interesting machines. We will stick with unary Turing machines and implement one for Decrement, Addition and Subtraction each.

Before we do so, however, let’s add some logging to visualize how the Turing machine is working and help us debug it.

Logging

We will handle the logging in a single method inside the TuringMachine class, that I called _log_process. Notice again the underscore which makes it clear to consumers of the machine that this is an internal/protected method and shouldn’t be used from outside.

def _log_process(self, step):
    print('\nTape after step {0}: '.format(step))
    print('[', end='')

    for i in range(0, self.tape.get_length()):
        if self.tape.head_position == i:
            print("\033[4m" + self.tape._tape[i] + "\033[0m", end='')
        else:
            print(self.tape._tape[i], end='')

    print(']')

It takes a step parameter and prints each character of the tape on a line. The character at the head_position will be printed with an underscore, that is why we need these ugly ASCII formatting.

Now, let’s plug this method into our process method. First, we have to declare the steps variable. Then we can call this method with each iteration of the Turing machine. Additionally, I added a call before the while loop, to display the initial state of the Turing machine:

def process(self):
    current_state = self.start_state
    step = 0
    self._log_process(step)

    while current_state.type != StateType.Final:
        ...
        step += 1
        self._log_process(step)

If we now rerun the Increment machine from the previous chapter, we should see the following output:

Now we can see how the Turing machine works its way from the left side of the tape to the right side and when it writes the final |. This kind of logging will be very handy for the Turing machines we are going to create next.

Decrement Machine

The Turing machine for decrementation works very similar to the one for incrementation. However, instead of adding a |, we have to remove the last one after we reach the end of the tape. This means we have to move to the right until we reach the first # character. Then, we can simply go one character to the left and remove that |:

In Python, we can represent this Turing machine with the following code:

tape = Tape('|||', '|')
states = [
            State("s0", StateType.Start),
            State("s1", StateType.Empty),
            State("s2", StateType.Empty),
            State("sf", StateType.Final)
         ]

transitions = [
                 Transition("s0", "$", "s1", "$", Direction.Right),
                 Transition("s1", "|", "s1", "|", Direction.Right),
                 Transition("s1", "#", "s2", "#", Direction.Left),
                 Transition("s2", "$", "sf", "$", Direction.Neutral),
                 Transition("s2", "|", "sf", "#", Direction.Neutral)
              ]

tm = TuringMachine(states, transitions, tape)
tm.process(True)

Addition Machine

Another simple Turing machine we can create is one that adds two numbers. We will represent the addition operation by two unary numbers separated by a &. For example, to calculate the sum of the numbers two and three, we would initialize the tape like this: $||%|||.
To add these numbers, all we have to do is to replace the & with a | and then remove the last |. For the tape above, this would result in $|||||. To realize this, the Turing machine has to go to the right until it reaches the %, replace it with | and then move further to the right until it reaches the end of the tape, marked by a #. Finally, it has to go one character to the left and remove the final |:

This translates into the following Python code:

tape = Tape('|||&||', '|&')
states = [
            State("s0", StateType.Start),
            State("s1", StateType.Empty),
            State("s2", StateType.Empty),
            State("s3", StateType.Empty),
            State("s4", StateType.Empty),
            State("sf", StateType.Final)
         ]

transitions = [
                 Transition("s0", "$", "s1", "$", Direction.Right),
                 Transition("s1", "#", "sf", "#", Direction.Neutral),
                 Transition("s1", "|", "s1", "|", Direction.Right),
                 Transition("s1", "&", "s2", "|", Direction.Right),
                 Transition("s2", "|", "s2", "|", Direction.Right),
                 Transition("s2", "#", "s3", "#", Direction.Left),
                 Transition("s3", "|", "s4", "#", Direction.Left),
                 Transition("s4", "|", "s4", "|", Direction.Left),
                 Transition("s4", "$", "sf", "$", Direction.Neutral),
              ]

tm = TuringMachine(states, transitions, tape)
tm.process(True)

Subtraction Machine

So far, our Turing machines have been fairly trivial. Now, let’s tackle a more complicated problem: Subtraction. One way to solve this problem is to move through the tape until we reach the first # (which we will use as Minus operator). Then, we have to remove the next | on its right and left side and replace them with #.
For example, given the tape $|||#||#, after these first steps, the tape would look like this: $||###|#. If we repeat this process until there are no more | on the right side of the initial #, the subtraction will be complete. In the case above, we will end up with a tape like: $|#####.

This process will work for tapes of any length. However, since we have to move through an increasing number of # with every step, the Turing machine will take a very long time for large inputs.
As you can see in the image below, the diagram for this Turing machine is much more complicated than the previous ones and it takes some time to fully understand it.

In Python, this is represented by the following code:

tape = Tape('|||#||', '|&')
states = [
            State("s0", StateType.Start),
            State("s1", StateType.Empty),
            State("s2", StateType.Empty),
            State("s3", StateType.Empty),
            State("s4", StateType.Empty),
            State("s5", StateType.Empty),
            State("s6", StateType.Empty),
            State("s7", StateType.Empty),
            State("s8", StateType.Empty),
            State("sf", StateType.Final)
         ]

transitions = [
                 Transition("s0", "$", "s0", "$", Direction.Right),
                 Transition("s0", "#", "sf", "#", Direction.Neutral),
                 Transition("s0", "|", "s1", "|", Direction.Right),
                 Transition("s1", "|", "s1", "|", Direction.Right),
                 Transition("s1", "#", "s2", "#", Direction.Right),
                 Transition("s2", "#", "s2", "#", Direction.Right),
                 Transition("s2", "|", "s3", "|", Direction.Right),
                 Transition("s3", "|", "s4", "|", Direction.Left),
                 Transition("s3", "#", "s6", "#", Direction.Left),
                 Transition("s4", "|", "s5", "#", Direction.Left),
                 Transition("s5", "#", "s5", "#", Direction.Left),
                 Transition("s5", "|", "s2", "#", Direction.Right),
                 Transition("s5", "$", "s2", "$", Direction.Right),
                 Transition("s6", "|", "s7", "#", Direction.Left),
                 Transition("s7", "#", "s7", "#", Direction.Left),
                 Transition("s7", "$", "sf", "$", Direction.Neutral),
                 Transition("s7", "|", "s8", "#", Direction.Left),
                 Transition("s8", "|", "s8", "|", Direction.Left),
                 Transition("s8", "$", "sf", "$", Direction.Neutral)
              ]

tm = TuringMachine(states, transitions, tape)
tm.process(True)

This concludes our collection of Turing machines. I encourage you to play around with them and create new ones. For example, you can try to implement Turing machines for Multiplication and Division.

I hope you enjoyed this series. If you have any questions, problems or feedback, please let me know in the comments.