CISC 7220X Computability and Unsolvability

37 hours plus conference and independent work; 3 credits

Formal systems, propositional and quantification logic, theorem proving, equivalent characterizations of effective computability. Turing machines, recursive functions, and sets. Other notions of Godel, Herbrand, Kleene, Church, Post, and Markov. Classification of unsolvable problems.

Prerequisite: Computer and Information Science 7221X or a course in theoretical computer science.


The City University reserves the right, because of changing conditions, to make modifications of any nature in academic programs and requirements of the university and its constituent colleges without advanced notice. Students are advised to consult regularly with college and department counselors concerning their programs of study.

Access the college's current and recent course bulletins.

Students at an outdoor class on the East Quad.

Graduate Open House

Explore our 87 master's degree and advanced certificate programs on October 25.