Turing Machines
Introduction
Alan Turing was an English mathematician, wartime code-breaker and pioneer of computer science. Turing studied mathematics at Cambridge University, and subsequently taught there, working in the burgeoning world of quantum mechanics. It was at Cambridge that he developed the proof which states that automatic computation cannot solve all mathematical problems. This concept, also known as the Turing machine, is considered the basis for the modern theory of computation.
Alan Turing
The "Turing" machine was invented in 1936 by Alan Turing who called it an "a-machine" (automatic machine). The Turing machine not a physical machine, but is meant as a theoretical tool for the use in computer science for modelling mechanical computation.
Overview
A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.
The hypothetical machine consists of:
- Tape. The tape is segmented into "cells" containing some symbol from a finite alphabet. This tape should be considered able to be extended arbitrarily in either direction.
- Head. The head can read and write symbols to and from a cell after which it moves the tape left or right one cell.
- State Register. This stores the current state information of the machine whilst running, as well as the original state of the machine at the time it was initialised.
- Finite Table. This is a table of instructions, where, given the current symbol read by the head and the current state of the machine, the table will be used to look up the instruction to follow. These instructions could be to move the head, clear a symbol, write a symbol, and change state.
Formal Definition
Now that we understand conceptually what a Turing Machine is, let's take a look at a formal definition.
The Turing machine is formally defined as:
where
- Q is a finite, non-empty set of states
is a finite, non-empty set of the tape alphabet/symbols- b ∈ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
is the set of input symbols
is the initial state
is the set of final or accepting states.
is a partial function called the transition function, where L is left shift, R is right shift
Example of a simple Turing Machine
Let's take a look at a graphical depiction of a simple Turing machine.
From this diagram, we can extrapolate the following parameters of the machine:
- : It's alphabet is {0,1} (binary, in other words)
- q0: The starting state is state 0.
- F: The final state is state 1.
Let's step through some example input. Let's assume that Σ (input) is the string "001101".
- "0" : We start at state 0, and read a 0. So we follow the instruction to write a 1 and move right (0:1,R). We move to state 1. Σ is now "101101", and we are in position 2.
- "0" : We are in state 1, and read a 0. So we write a 1 and move to the right (0:1,R). We move back to state 0. Σ is now "111101", and we are in position 3.
- "1" : We are in state 0, and read a 1. So we write a 1 and move to the left (1:1,L). Σ is still "111101", and we are in position 2.
- "1": We are in state 0, and read a 1. So we write a 1 and move to the left (1:1, L). Σ is still "111101", and we are now back in position 1.
- "1": We are in state 0, and read a 1. So we write a 1 and move to the left (1:1,L).
We are no in position -1, and when we read a blank character, there is no instruction for how to handle this, and so the machine will halt.
Let's step through a different Σ input string. Let's consider "010".
- "0": We start at state 0, and read a 0. So we write a 1 and move right (0:1,R). We move to state 1. Σ is now "110", and we are in position 2.
- "1": We are in state 1, and read a 1. So we write a 0 and move to the right (1:0,R), which takes us to the end of the program and so we halt.