Feb 02, 2023  
2014-2015 Graduate Catalog 
    
2014-2015 Graduate Catalog ARCHIVED CATALOG: CONTENT MAY NOT BE CURRENT. USE THE DROP DOWN ABOVE TO ACCESS THE CURRENT CATALOG.

CS 718 - Theory of Computation


Credits 3

Computability of functions and sets in terms of Turing machines and other computational models. Universal Turing machines and examples of unsolvable problems. Introduction to other computational models, such as the lambda-calculus, Post systems, Markov algorithms and recursive function theory. The Church-Turing thesis and proofs of equivalence between the models.

Prerequisites