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.

Links:

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)

Questions:

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?