Turing machine

Many computer scienc estudents know the Turing machine from computing theory course. You use Turing machine to prove your algorithm.
A Turing machine is a theoretical device that manipulates symbols contained on a strip of tape. 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 of a computer.

For definition of turing machine, see wiki:
http://en.wikipedia.org/wiki/Turing_machine


Turing machines, first described by Alan Turing in (Turing 1937), are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed.

Turing, writing before the invention of the modern digital computer, was interested in the question of what it means to be computable. Intuitively a task is computable if one can specify a sequence of instructions which when followed will result in the completion of the task. Such a set of instructions is called an effective procedure, or algorithm, for the task. This intuition must be made precise by defining the capabilities of the device that is to carry out the instructions. Devices with different capabilities may be able to complete different instruction sets, and therefore may result in different classes of computable tasks (see the entry on computability and complexity).

Turing proposed a class of devices that came to be known as Turing machines. These devices lead to a formal notion of computation that we will call Turing-computability.

The proposition that Turing's notion captures exactly the intuitive idea of effective procedure is called the Church-Turing thesis. This proposition, being a claim about the relationship between a formal concept and intuition, is not provable, though it would be refuted by an intuitively acceptable algorithm for a task that is not Turing-computable. That no such counterexample has been found, together with the fact that Turing-computability is equivalent to independently defined notions of computability based on alternative foundations, such as recursive functions and abacus machines, indicates that there is at least something natural about this notion of computability.

Turing machines are not physical objects but mathematical ones. We require neither soldering irons nor silicon chips to build one. The architecture is simply described, and the actions that may be carried out by the machine are simple and unambiguously specified. Turing recognized that it is not necessary to talk about how the machine carries out its actions, but merely to take as given the twin ideas that the machine can carry out the specified actions, and that those actions may be uniquely described.

http://plato.stanford.edu/entries/turing-machine/