Next: Church-Turing Thesis Up: The Classical Computer Previous: The Classical Computer   Contents

## Turing Machines

One of the people most directly responsible for the current concept of computing machines is Alan Turing. Other early giants in the field of Computer Science include Kurt Godel, Emil Post, and Alonzo Church.

Turing and others proposed mathematical models for computing which allowed for the study of algorithms and in absence of any particular computer hardware. These abstraction have proved invaluable in the field of computer science, allowing for general results about algorithms and their run time complexity to be obtained without having to consider a variety of potential computation engines on which those algorithms would run. 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, a 0, or a blank. There is also a head which can move about the tape, read a cell, write to a cell, change its internal state, or end computation. It is the internal state of this head that is the program which decides what action the head will take next. (Steane)

As simple as this model appears, it encompasses all the functionality of today's most modern supercomputer. That is to say, given the time and memory, there is not a single computation that can be performed on a modern supercomputer that can not be performed on a Turing machine. The immense value of the Turing machine is that when examining what sort of functions can be computed by a computer, one need only to examine a Turing machine, and not one of the millions of potential computing devices to determine if a computation is possible. If a Turing machine can perform the computation, then it is computable. If a Turing machine can not, then the function can not be computed by any classical computer. (Shor)

Next: Church-Turing Thesis Up: The Classical Computer Previous: The Classical Computer   Contents
Matthew Hayward - Quantum Computing and Shor's Algorithm GitHub Repository