Complexity Explorer Santa Few Institute

The British mathematician Alan Turing devised a hypothetical machine to carry out mathematical "algorithms".   This construct is now termed a "Turing Machine".   A given Turing machine consists of a linear "tape" containing readable/writable "cells", a "tape head" that can either read or write a symbol on the current tape cell or move to the left or the right on the tape, a set of "states" that the machine can be in at a given time, a initial state that the machine starts in, and a set of rules that map the current state and contents of the current tape symbol into an action for the tape head to take.  The machine proceeds over a series of time steps until it reaches the "halt" state (if it is a "halting" machine).  Turing's goal in devising this construct was to formalize the notion of "definite procedure" (or "algorithm").  A given Turing machine corresponds to what we would now call a "program" or "algorithm". 

A universal Turing machine is a Turing machine that can emulate the operation of any other Turing machine on a given input.   The universal Turing machine, designed by British mathematician Alan Turing, gave an early blueprint for programmable computers.