Theory of computation
• Background:
In 1936 Alan Turing; the founder of the Turing machine, suggested to use it as a way to compute and solve “computable” functions. It’s one of the most general computing devices. Theory of Computation purpose is to develop formal mathematical models of computation that reflect real-world computers.
Classify problems according to their degree of “difficulty”. Give a rigorous proof that problems that seem to be “hard” are really “hard"Complexity Theory
This branch of Theory of Computation studies how can some problems be hard to solve and others be easy, and the reason behind their complexity.
- A problem is considered to be hard if: It could not be solved efficiently.
- A problem is considered to be easy if: it could be solved efficiently.
Computability Theory
Classify problems as being solvable or unsolvable.
This branch studies what mathematical problems computers could solve.
Automata Theory
Do these models have the same power, or can one model solve more problems than the other?
This branch deals with "computation models" and studies their definitions and properties.
Examples:
➢ Finite Automata.
➢ Turing Machines.
➢ Context-Free Grammars.
Some practical applications of the theory of computation:
1- Computers
2- Programming Languages/ Compilers
Questions:
1- What makes a problem unsolvable?
2- What kind of problems computers cannot solve yet?
3- What are "computation models”?
References
Gurari, Eitan. An Introduction to the Theory of Computation. Theory-bk.html. Ohio State University. Web. 5 Sept. 2015.
Maheshwa, Introduction to Theory of Computation Anil, and Michiel Smid. "Introduction." Introduction to Theory of Computation. Carleton U, 2014. 1,2,3. Web.
Sipser, Michael. "Introduction." Introduction to the Theory of Computation. 3rd Ed. ed. Boston: PWS Pub., 1997. 1,2,3,4. Web.