The theory of computation, which includes automata theory and language, computability theory, and computational complexity theory, is an important field of theoretical computer science and mathematics, which use an algorithm, focusing on the efficiency of solving problems on a computation model, which is a mathematical abstraction of computers to help computer scientists study computation. It was a branch of mathematics because mathematics and logic are used to create models of computation. However, it turned out to be an independent subject in the last century. In a number of such models, the Turing machine, which can simulate the computing process, when the computer algorithm is given, becomes the one that scholars study and examine the most, because of its simplicity and ability to be used for analyzing and proving results. Although the Turing machine has the potentially infinite memory capacity, a characteristic that is impossible to implement in the real life, it can solve decidable problems that only need a finite amount of memory, so that the problems are also resolvable by a computer.
As a main branch of the computation theory, automata theory basically discusses abstract machines and automata and resolve problems on them. Associated with it is the formal language theory, which explains languages, usually created and recognized by automata, as a set of operations over an alphabet. There are different types of formal languages: each of them allows more complicated language identification than the one before it. Due to the fact that automata are widely used for computation, people use formal languages as means of specification for problems that are going to be computed.
To what degree is a problem solvable on a computer? Computability theory deals with this question as a part of the theory of computation. It found that the halting problem cannot be solved by a Turing machine, an example of an easy-to-formulate question but impossible to solve by a Turing machine. A great part of computability theory then bases on the halting problem statement. Because of the similarity, the computability theory is also called recursion theory, which extends the boundary of computation model study beyond the Turing machine.
The third branch is computational complexity theory, which concentrates on the efficiency of solving a problem. Time complexity and space complexity are often considered, which are respectively the number of steps and the amount of time a computation needs. Computer scientists illustrates the time and space as a function linked with the input problem’s size.
1. https://en.wikipedia.org/wiki/Theory_of_computation#cite_note-Sipser-3rd-1 (overview of the theory of computation)
2. https://en.wikipedia.org/wiki/Halting_problem (overview of the halting problem)
3. https://en.wikipedia.org/wiki/Turing_machine (overview of the Turing machine)
1. Why can a Turing machine simulate any computation algorithm?
2. How are automata theory and formal languages combine in practice?
3. Why is the halting problem so important?