This is a lecture and laboratory course that formalizes a definition of a computation model and uses it to study the fundamental question, “What can and cannot be computed?” Students study deterministic and non-deterministic computational models, such as finite automata, push-down automata and Turing machines, as well as regular expressions and grammars. Types of problems that can and cannot be solved by each of these models of computation are identified. The Church/Turing thesis, which attempts to describe what is and is not solvable by our current model of computation, is also studied. Prerequisite: CSCI 220. Alternate years.
Grade Basis: Letter Grade
Credits: 4.0
St. Norbert College adheres to all policies of non-discrimination on the basis of age, sex, gender identity, race, color, national origin, ancestry, sexual orientation, military or veteran status, marital status, disability, religion or any other characteristic protected by the current federal, state, and local statutes. Further, the college prohibits discrimination based on genetic information and non-job related arrest record or conviction records for employment purposes.
@2023 St. Norbert College