Recursive and Primitive Recursive Functions, Turing Machines. Equivalence Between Several Models, Church's Thesis, Universal Machine, Undecidable Problems, Deterministic and Nondeterministic Machines, The Class P and Np-completeness, Cook's Theorem. Learning Outcomes# at The End of The Course The Students Will Know# 1. Be Familiar With Models of Computation, in Particular The Turing Machine Model. 2. Distinguish Between Decidable and Undecidable Problems. 3. Be Familiar With The Concept of Efficient Computation (in Time Or Memory), and Be Able to Classify Problems Into Those That Can Be Solved Efficiently Or That Are "computationally Hard". 4. Understand and Apply The Concept of Reduction Between Problems.

Faculty: Computer Science
|Undergraduate Studies |Graduate Studies

Pre-required courses

234247 - Algorithms 1

Course with no extra credit

46002 - Design and Analysis of Algorithms 97447 - Intro. to Computability and Complexity 106843 - Theory of Computation C 214912 - Computational Models For Teachers

Course with no extra credit (contained)

94250 - Introduction to Computability

Semestrial Information