22-09-2012, 05:06 PM
Why do we study Theory of Computation ?
1-Introduction.ppt (Size: 200.5 KB / Downloads: 23)
What is Computation ?
Sequence of mathematical operations ?
What are, and are not, mathematical operations?
Sequence of well-defined operations
How many operations ?
The fewer, the better.
Which operations ?
The simpler, the better.
History of Theory of Computation
1936 Alan Turing invented the Turing machine, and proved that there exists an unsolvable problem.
1940’s Stored-program computers were built.
1943 McCulloch and Pitts invented finite automata.
1956 Kleene invented regular expressions and proved the equivalence of regular expression and finite automata.
Language Recognition and Problem
A problem is represented by a set of strings of the input whose answer for the corresponding problem is “YES”.
a string is in a language = the answer of the corresponding problem for the string is “YES”
Let “Given a positive integer n, is n a prime number > 20?” be the problem P.
If a string represents an integer i in {m | m is a prime number > 20} , then the answer for the problem P for n = i is true.