Turing Machine

The Turing Machine was first described in a paper published in 1936 on computable numbers, by English mathematician Alan Turing, who called it an a-machine and presented it as a thought experiment.

What is a Turing Machine?

A Turing Machine is a theoretical computing machine with an infinitely long tape upon which it manipulates symbols according to the mathematical model that defines it.

This machine is made up of:

  • A line of cells (“tape”) that can move back and forth
  • An active element (“head”) that has a property (“state”) and that can change the property (“colour”) of the active cell underneath it
  • A set of instructions for how the head should modify the active cell and move the tape.

Depending on the symbol and its position on the finite table – represents an algorithm that is necessarily finite – the machine:

  1. Writes a symbol (eg. a number) in the cell
  2. Either moves the tape one cell left or right
  3. Either continues or stops the computation.
loopBDlarge.png

Source: aturingmachine.com

With this hypothetical machine, Turing was able to prove properties of computation, and in particular, the uncomputability of Hilbert’s Entscheidungsproblem, also known as the decision problem.

Universal Turing Machine

Alan Turing was able to show that:

  • if there is a table U such that the head of a Turing machine is programmed in accordance with U;
  • and if any table P is translated and written out on the machine’s tape;
  • then the machine will behave as if its head had been programmed in accordance with P.

A Universal Turing Machine is an Turing machine whose head has been programmed in accordance with U.

There are many distinct Universal Machines, all with equivalent computational power, due to the fact that there are many tables that will act like U.

Turing Machines to Computers

The model of the Universal Turing Machine is considered to be the origin of the stored program computer (stores program instructions in electronic memory), which was used by John von Neumann in 1946 for the von Neumann architecture.

However, Turing’s greatest contributions to the development of the digital computer was his establishment of the idea of controlling the function of a computing machine by storing a program of instructions in the machine’s memory, and also his proof that a single, universal machine can carry out every computation.

Sources: 1 | 2 | 3

 

Advertisements

2 comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s