Turing machines

We are now in a position to show that the Entscheidungsproblem cannot be solved.

A.M. Turing, On Computable Numbers, With an Application to the Entscheidungsproblem.

One of the foundations of modern computing is the Turing Machine⊕See the Stanford Encyclopedia of Philosphy's article on Turing machines for a more thorough introduction and background, too., but embarassingly, I had only a vague understanding of the topic. I recently subscribed to Destroy All Software, and starting on the computation series.

Introduction

One of the motivations behind the Turing Machine is exploring the limits of computation via the halting problem: can we write a function halt that takes a function as an argument and returns true if the function eventually halts? It turns out that this is an unsolvable problem.

Computing by changing

Under the imperative model of computation, the machine executes an ordered sequence of instructions. The order of instructions matters, and operations are generally destructive - they modify memory in place.

Fundamentally, a Turing machine is simple. It has four elements: ⊕Note that a Turing Machine is a type of state machine.

An infinite tape that is composed of cells, each of which contains either the blank symbol (by convention, B is used).
A tape head, which points to the current cell in the tape. The head must be moved during each state transition.
The state transition table. Entries are defined by the tuple (symbol, state), and contain the tuple (write symbol, head direction, next state).
The current state, as defined by the state table.

A minimal Turing machine can be written in four lines of Python. Along with a corresponding state table, a complete program is shown below. ⊕Note to self: replace this with a Racket version. ⊕For simplicity, several things have been hardcoded in this implementation, namely the tape size, the starting state, and the number of iterations.

# toggle the first cell between 'X' and blank.
X_B = {
       ('B', 's1'): ('X', 'R', 's2'),
       ('B', 's2'): ('B', 'L', 's3'),
       ('X', 's3'): ('B', 'R', 's4'),
       ('B', 's4'): ('B', 'L', 's1')
}

def simulate(instructions):
    tape, head, state = ['B', 'B'], 0, 's1'
    for _ in range(8):
        (tape[head], head_dir, state) = instructions[(tape[head], state)]
        head += 1 if head_dir == 'R' else -1

Last updated on 2018-04-11.