Computability and Complexity Dublin City University - Full Curriculum Program Fall 2022 Semester - Dublin

The goal of this module is to provide an insight into the fundamental capabilities and limitations of computers. This module will expose students to three central areas of the theory of computation: automata, computability and complexity. With respect to automata, a number of languages of increasing descriptive power will be studied as well as corresponding automata which can be used to recognize these languages. With respect to computability, it will be shown which problems can or cannot be solved by computer. A number of different models of computation will be studied, and it will be shown that these are all of equivalent computational power. With respect to complexity, it will be shown for those problems which can be solved by computer whether they can be solved within a reasonable amount of time and space.