# 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): (tape[head], head_dir, state) = instructions[(tape[head], state)] head += 1 if head_dir == 'R' else -1

Last updated on 2018-04-11.