Theory of Computability

Catalog description

This is a survey of theoretical models of computation-notably the Turing machine model, the Markov algorithm model and register machine model-as well as equivalence results relating those models. Considerations of efficiency (complexity theory) are also introduced with an emphasis upon the use of big-O notation to describe the time/space requirements of specific machines. Simulation software is used extensively, thereby enabling students to design and run their own abstract machines. This is an essential course for students interested in pursuing graduate study later.