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.
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.
This branch studies what mathematical problems computers could solve.
This branch deals with "computation models" and studies their definitions and properties.
➢ Finite Automata.
➢ Turing Machines.
➢ Context-Free Grammars.
Some practical applications of the theory of computation:
2- Programming Languages/ Compilers
1- What makes a problem unsolvable?
2- What kind of problems computers cannot solve yet?
3- What are "computation models”?
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.