Models of Computation

Catalog description

While most computer science courses discuss problems which are able to be solved by computers, this course will look at both the capabilities and the limitations of computers. We start by analyzing simple models of computation, including finite state automata, and push down automata, and build up to Turing machines, which are powerful enough to model modern computers including multicore parallel machines. The course explores where the boundary lies between what is possible and impossible to compute on each model to draw conclusions about the nature of computation.