3-1-4: Turing Machines

Background:
In the early 20th Century, mathematicians wondered if there existed a process that could determine in a finite number of operations whether any mathematical statement was true or false. This challenge intrigued Alan Turing, and in 1934 he set about devising an abstract model of computation that he hoped would enable an effective procedure to be found which would give a yes or no answer to Hilbert's tenth problem (what the problem was named, after David Hilbert). Essentially, the effective procedure was an algorithm to solve this problem.

Solvable and Unsolvable Problems:

• In 1930, Kurt Godel showed that there were mathematical statements that it would be impossible to prove or disprove.
• In 1936, Alan Turing wrote a paper called 'On Computable Numbers'. This paper introduced the concept of the Turing Machine- a universal machine capable of solving any problem that can be represented algorithmically.

In Turing's human computer, computing is normally done by writing certain symbols on paper. Turing imagined this paper to be divided into squares like a child's arithmetic book.

How it Relates to Computers:

The work done by Turing was the base of the first computer.

The Turing Machine consists of:

• an input alphabet
• a tape that is infinitely long
• an output alphabet (that can be printed on the tape)
• a tape-head that is used to read/write to teh cells
• a finite set of states- incliding a start state
• a program (set of instructions)