Basic Information
Recursive and Primitive Recursive Functions, Turing Machines. Equivalence Between Several Models, Church's Thesis, Universal Machine, Undeidable Problems, Deterministic and Nondeterministic Machines, The Class P and Np-completeness, Cook's Theorem. Learning Products# 1. The Student Will Have The Basic Understanding and Ability To Compare and Distinguish Between Basic Models in Computability. Turing Machine, Machines With Stack, Universal Machine, Deterministic/ Non-deterministic Machines, Etc. 2. The Student Will Be Aware of The Differences Between The Standard Problem Classes# Decidable/undecidable Problems, P, Np-complete, Np-hard. 3. The Student Will Understand The Limitations of Computers and Will Be Able to Answer The Question of What Kind of Problems Can Be Computed. 4. The Student Will Achieve a Deep Understanding of The Mathematical Properties of Computer Hardware and Software.
Faculty: Mathematics
|Undergraduate Studies
|Graduate Studies
Course with no extra credit
236343 - Theory of Computation 237343 - Theory of Computation