Scribd
Upload
129 views11 pages

Theory of Computation Guide

Theory of computation deals with how problems can be solved using algorithms and models of computation. It is divided into three branches: automata theory studies abstract computational devices; computability theory deals with determining whether problems can be solved on computers; and computational complexity theory considers not only if problems can be solved but how efficiently. Studying theory of computation provides a foundation for understanding computers and computing, and has practical applications in areas like web search, circuit design, compilers, cryptography, and data compression.

Uploaded by

Muhammad Amjad Raza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
129 views11 pages

Theory of Computation Guide

Theory of computation deals with how problems can be solved using algorithms and models of computation. It is divided into three branches: automata theory studies abstract computational devices; computability theory deals with determining whether problems can be solved on computers; and computational complexity theory considers not only if problems can be solved but how efficiently. Studying theory of computation provides a foundation for understanding computers and computing, and has practical applications in areas like web search, circuit design, compilers, cryptography, and data compression.

Uploaded by

Muhammad Amjad Raza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Why Theory of Computation

#Contents :
1. Introduction .
2. What is the Theory of Computation ?
3. What are the benefits of studying theory of
computation ?
4. Why do we learn Theory of Computation ?
5. Conclusion .
1- Introduction :
At the beginning, this presentation to help you to know more
about Theory of Computation
 We are going to talk about the importance of Theory of
Computation .. and talk about the concept of Theory of
Computation.
2-What is the Theory of Computation ?

In theoretical computer science and mathematics, the theory


of computation is the branch that deals with how problems can
be efficiently solved on a model of computation, using an
algorithm. This field is divided into three major branches:
I. Automata theory .
II. Computability theory .
III.Computational complexity theory .
I-Automata theory :
• Automata theory is the study of abstract computational devices.
• Abstract devices are (simplified) models of real computations
• Computations happen everywhere: On your laptop, on your cell
phone, in nature, …
II-Computability theory :

Computability theory deals primarily with the question of the


extent to which a problem is solvable on a computer. The
statement that the halting problem cannot be solved by a Turing
machine is one of the most important results in computability
theory, as it is an example of a concrete problem that is both
easy to formulate and impossible to solve using a Turing machine.
Much of computability theory builds on the halting problem
result.
III-Computational complexity theory :
Complexity theory considers not only whether a problem can be
solved at all on a computer, but also how efficiently the problem
can be solved. Two major aspects are considered:
 Time complexity: and how many steps does it take to perform
a computation .
 Space complexity: and how much memory is required to
perform that computation.
3-What are the benefits of studying
theory of computation ?

 Theory of computation teaches you about the elementary ways


in which a computer can be made to think.
 There is a great deal of work that was made possible in the
area of Natural Language Processing that involved building
Finite State machines also known as Finite State Automata .
4-Why do we Learn Theory ?
 In theory . . .
• Deeper understanding of what is a computer and computing.
• Foundation of all modern computers.
• Pure science.
• Philosophical implications.
4-Why do we Learn Theory ? (cont.)
 In practice . . .
• Web search: theory of pattern matching.
• Sequential circuits: theory of finite state automata.
• Compilers: theory of context free grammars.
• Cryptography: theory of computational complexity.
• Data compression: theory of information.
5-Conclusion :

• Atthe end, it was just a talk about the importance


of Theory of Computation  

You might also like