Turing Machines

To understand how a quantum computer can be more ``powerful'' than a classical computer we should first define what we mean by powerful, and by classical computer. One of the people most directly responsible for the current concept of computing machines is Alan Turing. Others who contributed to the early development of computer science include Kurt Godel, Emil Post, and Alonso Church.

Turing and others proposed mathematical models for computing which allowed for the study of algorithms and in absence of any particular computer hardware. This abstraction has proved invaluable in the field of computer science. Turing's model is called a Turing machine. The design of the Turing machine is the following: The machine consists of an infinite tape divided into cells, each cell can contain a 1, 0, or blank. Additionally a head moves about the tape, reads and writes to the cells, may halt computation, and maintains an internal state which determines what action the head will take next. (Steane)