Theory of Computation
BACK TO HOME PAGE
THEORY OF COMPUTATION


UNREVIEWED SUMMARY:

What do we mean by Theory of Computation?
Theory of computation is part of theoretical Computer Science. It allow us to search and explore the nature of computations more closer to find out new theories and apply them to computer science.
It help solving problems by using algorithms, it tests how an algorithm works and how effective is it to be able to solve them.


What are the parts of the computational theory?
1- Automata Theory : it is a way to solve computational problems, moreover, it is the study of abstract machines and automata.
There are types of computation models that are dealt by using this theory, such as : finite automata, context-free grammars, and Turing machines.
-Finite automata are used in text processing, compilers, and hardware designs.
-Turing machines form a basic abstract model, such as your computer at home.
-Context-Free grammars are used to define programming languages and in artificial intelligence.
2- Computability Theory (known as recursion theory) : It started on 1930s with the study of computable functions and Turing degrees. It is a part of mathematical logic, and theory of computation.It classifies problems as being solvable or unsolvable.
3- Computational complexity theory : It organizes the problems of computers due to their degree of difficulty, with relating each class to the other one.
In Theory of computations, there are two main aspects which are: time complexity, and space complexity.


Models of Computation Machines :
1- Turing machines : It is the most common machine used in imperative programming languages in computation, it has an unlimited supply of paper tape that can write on and read back. It takes an input symbol and does 3 thing according to the symbol and the current state. The first thing is that it prints something on the tape, then it moves the tape either left or right by one cell, and then convert it to a new state.
2- Combinatory logic : A theory that is connected to logic, has many applications in computer science and mathematics disciplines.
3- Lambda calculus : functional programming languages are based on Lambda-calculus computational model, in functional programming we only need to modify the representation of the information, but we do not have to produce anything in general programming.
4- Abstract rewriting systems (ARS) : It is the most general notion that can be applied on a set of objects and rules to specify transform them. In history, there have been some formalizations of rewriting in abstract setting, this is due to the fact that some notions are equivalent.


REVIEWED SUMMARY:

What do we mean by Theory of Computation?
Theory of computation is a part of theoretical Computer Science. It allows us to search and explore the nature of computations more closer to find out new theories and apply them to computer science.
It helps solving problems by using algorithms, it tests how an algorithm works and how effective is it to be able to solve them.


What are the parts of the computational theory?
1- Automata Theory : it is a way to solve computational problems, moreover, it is the study of abstract machines and automata.
There are types of computation models that are dealt by using this theory, such as : finite automata, context-free grammars, and Turing machines.
-Finite automata are used in text processing, compilers, and hardware designs.
-Turing machines form a basic abstract model, such as your computer at home.
-Context-Free grammars are used to define programming languages and in artificial intelligence.
2- Computability Theory (known as recursion theory) : It started on 1930s with the study of computable functions and Turing degrees. It is a part of mathematical logic, and theory of computation.It classifies problems as being solvable or unsolvable.
3- Computational complexity theory : It organizes the problems of computers due to their degree of difficulty, with relating each class to the other one.
In Theory of computations, there are two main aspects which are: time complexity, and space complexity.


Models of Computation Machines :
1- Turing machines : It is the most common machine used in imperative programming languages in computation, it has an unlimited supply of paper tape that can write on and read back. It takes an input symbol and does 3 thing according to the symbol and the current state. The first thing is that it prints something on the tape, then it moves the tape either left or right by one cell, and then convert it to a new state.
2- Combinatory logic : A theory that is connected to logic, has many applications in computer science and mathematics disciplines.
3- Lambda calculus : functional programming languages are based on Lambda-calculus computational model, in functional programming we only need to modify the representation of the information, but we do not have to produce anything in general programming.
4- Abstract rewriting systems (ARS) : It is the most general notion that can be applied on a set of objects and rules to specify transform them. In history, there have been some formalizations of rewriting in abstract setting, this is due to the fact that some notions are equivalent.

Here are some links you can visit to gain more information about theory of comutation:
1- click here to go to this site
2- click here to go to this site
3- click here to go to this site


Questions about theory of computation:
1-How is automata theory used ?
2-How computability theory classify a problem wether its solvable or no ? According to what?
3-How turing machines work, and what makes them so important in its field?


References:
https://en.wikipedia.org
www.contrib.andrew.cmu.edu
ttp://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf
http://www.i-programmer.info/babbages-bag/23-turing-machines.html
http://plato.stanford.edu/entries/logic-combinatory/
http://www.dmi.unict.it/~barba/LinguaggiII.html/READING_MATERIAL/LAMBDACALCULUS/ShortIntroductiontotheLambdaCalculus.PDF
https://en.wikipedia.org/wiki/Abstract_rewriting_system