Mar 29, 2024  
2017-2018 Graduate Catalog 
    
2017-2018 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