Haya Al-Kuwari
(back to home)
Christos Kapoutsis: Theory of Computation

Theory of Computation is solving problems through mathematical models and algorithm. Also known as Theoretical Computer Science or Computability Theory. It has three areas: Automata Theory, Computability Theory, and Complexity Theory. It can be considered as the creation of models of all kinds of fields in computer science. That explains the mathematics and logic used in it. The mathematicians and logicians in 1930's were trying to understand the meaning of a "computation" and this led to computers.

Automata Theory deals with computational problems that can be solved by abstract machines. It has two models, one is finite automaton [represented by a 5-tuple], another one is context-free grammar and it is used in programming languages. It allows practice with formal definition of computation. Formal Language Theory is a branch of mathematics and it deals with describing languages as a set of operations with an alphabet. It can be also defined as a set of strings of symbols that are constrained by specific rules. It's related with Automata Theory, where in Automata Theory it's used to generate and recognize formal language.

Computability Theory classifies problems as being solvable or unsolvable. Formal definitions of the notions of computer, algorithm and computation are needed. (resource; i) This theory introduces several concepts that are in complexity theory. (resource; iv).

Complexity Theory has a central question, which is, "what makes some problems computationally hard and others easy?" So it classifies problems by difficulty. Computational Complexity Theory is kind of related where this theory considers how efficiently a problem can be solved. It considers two major aspects, time and space complexity. Computer scientists adopted Big-O Notation. Sometimes it can be used as 'the problems requires O(n) steps to solve'. (resource; ii)

Computability Theory and Complexity Theory have a 'model of computation' and it defined as the set of allowable operations used in computation and their respective costs. (resource; v) Turing machine, Lambda calculus, and combinatory logic are some few examples of the categories of those models. One of those examples, Turing machine, uses an infinite tape as its unlimited memory. It can both write on the tape and read from it and the read-write head can move to the right or to the left. It also has special states where it can accept or reject. It's used because it's simple to formulate, analyzable and used to prove results. It's also used to measure the complexity of an algorithm, execution time and memory space.

Questions about Theory of Computation:
1. Why kind of research are in the field of Theory of Computation?
2. How efficiently can a computer solve a fairly hard problem?
3. Which of the three fields focuses more on solving problems computationally?


(word count; 405) | resources; i ii iii iv v |

REVISED VER:

Theory of Computation has to do with solving problems through mathematical models and algorithms. It's also known as Theoretical Computer Science or Computability Theory. It has three areas: Automata Theory, Computability Theory, and Complexity Theory. It can be considered as the creation of models of all kinds of fields in computer science. That explains the mathematics and logic used in it. The mathematicians and logicians in 1930's were trying to understand the meaning of 'computation' and this led to computers.

Automata Theory deals with computational problems that can be solved by abstract machines. One example for automata theory is Game of Life, where it counts the cells and sees if the current cell is dead, born, or surviving. It has two models, one is finite automaton [represented by a 5-tuple], another one is context-free grammar and it is used in programming languages. It allows practice with formal definition of computation.

Formal Language Theory is a branch of mathematics and it deals with describing languages as a set of operations with an alphabet. It can also be defined as a set of strings of symbols that are constrained by specific rules. It's related to Automata Theory, where it's used to generate and recognize formal language.

Computability Theory classifies problems as being solvable or unsolvable. Formal definitions of the notions of computer, algorithm and computation are needed. (resource; i) This theory introduces several concepts that are in complexity theory. (resource; iv).

Complexity Theory has a central question, which is 'what makes some problems computationally hard and others easy?' So it classifies problems by difficulty. Computational Complexity Theory is kind of related to Computability Theory because it considers how efficiently a problem can be solved. It considers two major aspects, time and space complexity. Computer scientists adopted Big-O Notation. Sometimes it can be used as ‘the problems requires O(n) steps to solve'. (resource; ii). Big-O Notation is simply the time of processing of an algorithm.

Computability Theory and Complexity Theory have a 'model of computation' and it is defined as the set of allowable operations used in computation and their respective costs. (resource; v) The Turing machine, Lambda calculus, and combinatory logic are a few examples of those models. One of those examples, the Turing machine, uses an infinite tape as its unlimited memory. It can both write on the tape and read from it and the read-write head can move to the right or to the left. It's used because it's simple to formulate, analyzable and able to prove results. It's also used to measure the complexity of an algorithm, execution time and memory space.