Introduction of Theory of Computing, Theory of computing has a important role in computing technology

Introduction of Theory of Computing, Theory of computing has a important role in computing technology

1. Slide No. 1
CS501
Thery of Computation

2. Slide No. 2
What is Theory of Computation ?
•Fundamental questions in computer science:
➢What is the complexity of a problem – Complexity
➢ What can be computed and what cannot – Computability
➢What different models of computation machines can do and
can not do - Automata

3. Slide No. 3
What is Theory of Computation ?
Complexity Theory:
➢Complexity theory deals with analysing computational problems in terms of
their time and space requirements.
➢It classifies problems into different complexity classes, such as P, NP, and NP-
complete.
➢Complexity theory aids in understanding the inherent difficulty of solving
specific problems and guides the development of algorithms with optimal
efficiency.

4. Slide No. 4
What is Theory of Computation ?
Computability Theory:
➢Computability theory focuses on the fundamental question of what can be
computed and what cannot.
➢ It explores the limits of computation by studying Turing machines, recursive
functions, and other models of computation.
➢ Computability theory helps identify solvable problems and those that are
inherently unsolvable.

5. Slide No. 5
What is Theory of Computation ?
Automata Theory:
➢The study of abstract machines and the computational problems that can be
solved using these machines.
➢It investigates different types of automata, such as finite automata,
pushdown automata, and Turing machines.
➢Automata theory enables computer scientists to understand how machines
process information and solve computational problems.
➢Understand and classify formal languages based on their generative power

6. Slide No. 6
Alan Turing (1912-1954)
•Father of Modern Computer Science
•English mathematician
•Studied abstract machines called
Turing machines even before
computers existed
•Heard of the Turing test?
(A pioneer of automata theory)

7. Slide No. 7
Theory of Computation: A
Historical Perspective
1930s • Alan Turing studies Turing machines
• Decidability
• Halting problem
1940-1950s • “Finite automata” machines studied
• Noam Chomsky proposes the
“Chomsky Hierarchy” for formal
languages
1969 Cook introduces “intractable” problems
or “NP-Hard” problems
1970- Modern computer science: compilers,
computational & complexity theory evolve

8. Slide No. 8
WHAT IS AUTOMATA?
An Automaton (pl. Automata) is an abstract
model of a digital computer.
It has a mechanism for reading input (string over
a given alphabet) from an input file (divided
into cells each holding one symbol).
It can produce output of some form.
It may have a temporary storage device
(consists of unlimited no. of cells each holding one
symbol).
Finally, it has a control unit (can be in any one
of a finite no. of internal states, & can change
state in some defined manner).
2

9. Slide No. 9
Automata is an abstract model of a digital
computer