Background
In the early twentieth century, mathmaticians were trying to create a universal machine.
This consisted of a small number of operations and a machine that could perform all these operations.
This machine would be able to run any algorithm, and would be the precise definition of term algorithm.
The hope was to find algorithms that would be able to solve all mathmatical problems.
1930 -
Kurt Godel showed that there are mathmatical statements that it will never be possible to either prove or disprove.
Alan Turing showed that it would not be possible to write an algorithm which could determine if a problem is solvable or unsolvable.
1936 -
Turing machine invented & showed that you cannot determine if it is solvable or not.
Relevance to computing
- Computers where based on turning machine.
- IT showed that anything a computer can do a turing machine (on paper) can do.
Turing Machine
1.An input alphabet.
2.A tape that is
infinitely long.
3.An output alphabet
that can be printed on the tape.
4.A tape head that is
used to read/write to the cells.
5.A finite set of
states, including a start state.
6.A program (set of
instructions).
No comments:
Post a Comment