Programming Turing Machines - Part II

Programming
,
1

Programming Turing Machines: Implementation

To continue where we left off from the previous topic, I will begin discussing my Python implementation of a Turing machine. The fun part about implementation is that you don’t always have to be as explicit as you do when defining a model mathematically. This will give us some wiggle room later on to take advantage of inference.

Definition analysis

Recall our formal definition of a Turing machine from Introduction to the Theory of Computation by Michael Sipser:

A Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q0, qA, qR), where Q, Σ, Γ are all finite sets and:

  1. Q is the set of states,
  2. Σ is the input alphabet, where ‘_’ ∉ Σ,
  3. Γ is the tape alphabet, where ‘_’ ∈ Γ and Σ ⊆ Γ,
  4. δ: Q x Γ → Q x Γ x {L,R} is the transition function,
  5. q0 ∈ Q is the start state,
  6. qA ∈ Q is the accept state, and
  7. qR ∈ Q is the reject state, where qR ≠ qA.

Some of the components of the machine can be “skipped” as they will be left to the programmer to ensure. For instance, we do not need an explicit Q to be predefined: as long as our Turing machine has some state(s) to transition into, they will be assumed to be in Q. For a similar reason, Σ and Γ do not need to be explicitly predefined. It is up to the programmer to create a Γ alphabet to meet their needs, but the definition itself is agnostic to the model. As long as the programmer can hold ‘_’ ∈ Γ and Σ ⊆ Γ true, this can be left out.
qA and qR can also be left out. For our implementation, we want to machine to tell us more than just whether or not an input was accepted. For this reason, we can “ignore” the accept state and program a default halting transition. Any time a valid transition cannot be performed, the halting transition will run; this is what allows us to loosen the constraints on our input alphabet, as a symbol a | a ∉ Σ will simply cause the machine to halt when read.
With the above in mind, the only two things that remain are δ and q0. δ will hold a similar definition to before, this time being a list of lists rather than tuples. q0 will not have an explicit definition, but will be implied: my implementation assumes all machines start on a state “s1”.
We will need an additional structure to represent a tape; for this I used a list of characters combined with an integer that would store the index of the current symbol being read.

Code implementation

Putting all of the above together, we get the following:

class TuringMachine:
    def __init__(self):
        self.state = 's1'
        self.instructions = []
        self.tape = []
        self.position = 0

The next thing we need to do is give our TuringMachine the ability to change states. We have a list of transitions we can search, so let’s make a function with the following signature:

δ(q, a) = (q’, b, d), where:

  1. q, q’ ∈ Q,
  2. a, b ∈ Σ, and
  3. d ∈ {L,R}.

Translating that to pseudocode we something like this:

transition(state, symbol) {
    //
    // search
    //
    return state, symbol, direction
}

We know our transitions are represented by an ordered list, so we can match elements based on their position. We also have a variable self.state that is used to store the current state; we can reuse this and throw out the need to pass a state into our function. This function will also need to account for a default halting transition if a valid transition cannot be found. Here is the resulting function I came up with, which returns a symbol, a direction, and a state, respectively:

class TuringMachine:
    # ...
    def transition(self, a):
        t = [a, 'r', 'H']
        for i in self.instructions:
            if i[0] == self.state and i[1] == a:
                t[0] = i[2]
                t[1] = i[3]
                t[2] = i[4]
                break
        return t[0],t[1],t[2]

Next, we should give our machine a way to read from the tape using variables we have created. This function simply returns the element on the tape at the current index:

class TuringMachine:
    # ...
    def read(self):
        return self.tape[self.position]

The next thing we need is a way to write. This will be similar to self.read() in that we will be using self.tape and self.position to locate where to write, but we will need a character to pass to this function, as well as a way to overwrite only the current cell. Here’s the one-liner I used:

class TuringMachine:
    # ...
    def write(self, a):
        self.tape = self.tape[:self.position] + a + self.tape[self.position+1:]

Finally, we need to give our machine a way to move around the tape one cell at a time. As the definition in the previous topic stated, if our machine is at the start of the tape and attempts to move left, stay in the current cell without halting. If we move right and we are at the right-most end of the tape, we can simulate infinity by appending an empty cell before moving. Moving left will decrement self.position whereas moving right will increment it:

class TuringMachine:
    # ...
    def move(self, d):
        if d == 'l':
            if self.position != 0:
                self.position -= 1
        elif d == 'r':
            if self.position != len(self.tape)-1:
                self.position += 1
            else:
                self.tape += '_'
                self.position += 1

We now have all the pieces we need to run our Turing machine, now we just need to put them all together and have a way of showing every configuration while it runs. Displaying the configuration is really easy:

class TuringMachine:
    # ...
    def show(self):
        print self.tape + ' ' + self.state
        print ' '*self.position + '^'

Combining all of this into a single run function gets a bit trickier. We need to loop until the program halts, reading, writing, moving, transitioning, and printing the configuration every time. I used a while-loop where the condition checked self.state != 'H'.

class TuringMachine:
    # ...
    def run(self):
        self.show()
        while self.state != 'H':
            a,d,self.state = self.transition(self.read())
            self.write(a)
            self.move(d)
            self.show()

The above will print the initial input before the loop, then it will begin getting transitions and moving around the tape. I made mine a little bit more robust. Sometimes, the output would extend beyond my scrollback buffer, so I added a variable, s, to act as a suppression flag. I also added a conditional to the move instruction that will only allow it to execute if the machine has not transitioned into a halt state. This makes our halting configuration a little cleaner:

class TuringMachine:
    # ...
    def run(self, s):
        if s:
            self.show()
        while self.state != 'H':
            a,d,self.state = self.transition(self.read())
            self.write(a)
            if self.state != 'H':
                self.move(d)
            if s:
                self.show()
        if not s:
            self.show()

Putting it all together, our Turing machine is less than 50 lines. Our final product is ready for testing:

class TuringMachine:
    def __init__(self):
        self.state = 's1'
        self.instructions = []
        self.tape = []
        self.position = 0
    def show(self):
        print self.tape + ' ' + self.state
        print ' '*self.position + '^'
    def move(self, d):
        if d == 'l':
            if self.position != 0:
                self.position -= 1
        elif d == 'r':
            if self.position != len(self.tape)-1:
                self.position += 1
            else:
                self.tape += '_'
                self.position += 1
        else:
            print "Error"
    def read(self):
        return self.tape[self.position]
    def write(self, a):
        self.tape = self.tape[:self.position] + a + self.tape[self.position+1:]
    def transition(self, a):
        t = [a, 'r', 'H']
        for i in self.instructions:
            if i[0] == self.state and i[1] == a:
                t[0] = i[2]
                t[1] = i[3]
                t[2] = i[4]
                break
        return t[0],t[1],t[2]
    def run(self, s):
        if s:
            self.show()
        while self.state != 'H':
            a,d,self.state = self.transition(self.read())
            self.write(a)
            if self.state != 'H':
                self.move(d)
            if s:
                self.show()
        if not s:
            self.show()

Programming a Turing machine

The next thing I did was write a parser to make programming this easier. I won’t get into the guts of the parser, but it will turn a file like this:

; change each value
s1 > > r s1
s1 0 1 r s1
s1 1 0 r s1
s1 _ l s2

into a list of transitions for our machine. There are a couple things to note here. First, I used ‘;’ as my comment notation. This is not hardcoded, however, and can be changed in a global variable in the parser. The second is that weird 4-tuple transition at the end. In order for me to clean up the tape, I needed to have a way of removing cells. Originally, I was just leaving trailing '_'s on the tape, but as the machine grew that became a road block. Instead, I made two options for the parser:

  1. A 5-tuple transition of state, read-symbol, write-symbol, direction, state, and
  2. A 4-tuple transition of state, read-symbol, direction, state

The second option gets formatted into a 5-tuple transition that will remove a cell entirely. This is because our self.move() will add a ‘_’ to the end; commonly I will use a q _ l q' type transition to remove trailing '_'s, though it can be used anywhere.
Let’s get into what that sample program actually does, though. We start in s1 on a ‘>’. All of my programs will do this, and is an important assumption for chaining later on. If we see a ‘>’, we write a ‘>’, move right, and transition to s1. Since our state doesn’t change, this transition is a loop. In fact, only one transition changes the state; all but one will loop. Hopefully it isn’t too hard to see what this program will do: on a given binary input, this program will perform a bitwise NOT operation.
What about something a bit longer, with more states? Try this:

; delete first number
s1 > > r s1
s1 0 r s2
s1 1 r s2

; move to end
s2 0 0 r s2
s2 1 1 r s2
s2 _ 0 r s3

; delete _
s3 _ l s3

It may not be entirely obvious what is going on here, but the “trick” is happening in the last transition of the second block: s2 _ 0 r s3. Since we immediately began by chopping off the first bit, understanding this instruction will make it obvious. This instruction will append a 0 to the end of the tape: this whole program will shift a given binary input to the left by one bit!

Parting words

This is the part that makes Turing machines so much fun! If you enjoy writing Assembly programs, you will probably enjoy this because it is on a much lower level. Once you begin writing your own Turing machine programs, you will notice that besides being extremely tedious, there are some things you can’t easily do. The next topic I cover will walk you through how I abstracted this Turing machine implementation into a higher level model, with some added features, to perform all kinds of tasks that I wouldn’t want to write out solely in transitions. In the meantime, however, I will leave this program:

s1 > > r s1
s1 0 1 r s1
s1 1 0 r s1
s1 _ _ l s2

s2 0 1 l s3
s2 1 0 l s2
s2 > > r s3

s3 0 0 l s3
s3 1 1 l s3
s3 > > r s4

s4 0 0 r s4
s4 1 1 r s4
s4 _ l s5

I’ve removed comments, but you should be able to figure out what it’s doing. Post your answer in the comments, but don’t spoil it for others!
Part 3 is done!

4 Likes
2

This topic was automatically closed after 30 days. New replies are no longer allowed.