Theory of Computation > Queen's School of Computing

The theory of computation, also known as automata theory, is the study of abstract mathematical machines (or models of computation – the most well-known being the Turing machine) and the computation problems that they can be used to solve. Automata enable a researcher to understand how machines compute functions and solve problems. The main goal underlying the development of automata theory was to develop methods to describe and analyze the dynamic behaviour of discrete systems. It is a field closely related to formal language theory because automata are often classified by the class of formal languages they can recognize. Recent applications of automata theory and formal languages in bioscience and DNA computing have generated renewed interest in this foundational area.

Research Topics

Computability Theory: Computability theory deals primarily with the question of the extent to which a problem can be solved on a computer. It remains an active field of research and is commonly used to discover the computational expressiveness of new ideas in computer science, mathematics, and physics.
Computational Complexity Theory: Computational complexity theory considers not only whether a problem can be solved on a computer, but also how efficiently it can be done. Both in theory and practice, computational complexity theory helps computer scientists determine the limits of what computers can and cannot do and therefore aids in algorithm design and analysis.