# Turing machines

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

One of the foundations of modern computing is the Turing MachineSee 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):
head += 1 if head_dir == 'R' else -1