A Turing Machine Expressed As A State Machine

Illustrated guides to become better programmers

The topic of State Machines is one of the most fascinating ever. It allows us to become better programmers by offering a simple but powerful way of thinking. It has always been (unfortunately) associated with compiler theory and is always learned in boring textbooks (and weird animals like dragons and tigers). This post provides a tangible example to understand the topic that can be followed by even a child. Promise.

Exploring a simple machine

Let us think of a machine having an infinitely long amount of tape.

The tape has symbols on it. It can be alphabets, it can be something else.

We have a head that can modify the values.

The head can move left

or right.

It can also erase and write new values.

The head can also read values.

You can also replace the head with you and a pencil at this point. You read the values, move the pencil and use it to modify values.

Instructions for the machine

Using a piece of paper we can have instructions for the machine. For each scenario, we can think of what to do with the pencil when there is a particular symbol. What to do if there is a 1, what to do when there is a 0 or a blank, and where to move.

Let’s say we start at scenario one. Let’s execute the ifs. The 1 will become 0.

We then move to the left.

But then what? We are stuck. That’s why we also need to point out the next scenario so that we can get a continuous set of instructions.

Now we can get going and execute scenario 2 which leaves the value as is then moves to the left.

then scenario 5 and so on.

Introducing states

Replace scenario by state and that’s what states are.

Compressing instructions

It’s a bit much to write all those instructions. We can just translate it to a table as it’s already looking like we have some columns around.

Halting

If we don’t want our machine to run indefinitely, we can just replace a state in the path of execution with a halting instruction.

A Turing machine?

The above is essentially a turning machine. We have our indefinitely long tape, our finite set of symbols, head/pencil, finite states and rules to tell us how to run the machine.

If we can define a problem to be solved by a turing machine, then the problem is computable.

Expressing a turing machine in terms of state is a powerful concept. It allows us to translate our ideas better in terms of coding.

Exercise

Code the above in Python. Think about how you will store the table, consume the tape etc.

Code

tape = ['b','1', '1', '1', 'b']

instructions = {
    'state_1': {
        '1': {'write':'0', 'move':'left', 'go':'state_2'},
        '0': {'write':None, 'move':'right', 'go':'state_3'},
        'b': {'write':None, 'move':'left', 'go':'state_7'},
    },
    'state_2': {
        '1': {'write':None, 'move':'left', 'go':None},
        '0': {'write':None, 'move':'right', 'go':'state_4'},
        'b': {'write':None, 'move':'left', 'go':'state_8'},
    },
}

class Head:
    def __init__(self, index_on_tape):
        self.index_on_tape = index_on_tape
    
class Machine:
    def __init__(self, head, tape, instructions, starting_state):
        self.head = head
        self.tape = tape
        self.instructions = instructions
        self.current_index = self.head.index_on_tape
        self.current_state = starting_state
        
    def run(self):
        go_on = True
        
        while go_on:
            # read, write
            # move head
            # change state
            
            # read, write
            symbol_on_tape = self.tape[self.current_index]
            symbol_to_write = self.instructions[self.current_state][symbol_on_tape]['write']
            
            print(f'current state: {self.current_state}')
            print(f'symbol on tape:{symbol_on_tape} | symbol to write {symbol_to_write}')
            if symbol_to_write is None:
                pass
            else:
                self.tape[self.current_index] = symbol_to_write
                
            # move head
            move = self.instructions[self.current_state][symbol_on_tape]['move']
            if move == 'right':
                self.current_index += 1
                print('moving right')
            elif move == 'left':
                self.current_index -= 1
                print('moving left')
                
            # change state
            next_state = move = self.instructions[self.current_state][symbol_on_tape]['go']
            
            if next_state is None:
                print('halting!')
                go_on = False
            else:
                print(f'next state {next_state}')
                self.current_state = next_state 
            
        
head = Head(3)
machine = Machine(head, tape, instructions, 'state_1')
machine.run()

Notes

A first treatment of the topic in a fun way is found here. Badly wanted to code it up.

The code above treats each element as an object for making it conceptually easy to think about. The code can be improved by adding more machine methods and using a list to store the instructions.