CS 5060 - Computation Theory

• Students will develop the ability to prove that some languages are undecidable using the techniques mentioned in class.
• Students will develop the ability to show that a problem is computable in polynomial-time or NP-time.
• Students will develop the ability to show that certain numbers, such as the square root of 2, are computable real numbers.
• Students will develop the ability to show that certain problems are NP-complete.
• Students will develop the ability to show that various languages are decidable or recursively enumerable.
• Students will gain an understanding of precision issues in arithmetic computations.
• Students will gain an understanding of the Recursion Theorem, and Rice’s Theorem, and the ability to use these results to prove that certain problems are undecidable.
• Students will gain an understanding of the basic Turing machine model, and an ability to use the definition to solve tasks such as integer multiplication.
• Students will gain an understanding of the basic definition of a universal Turing machine and its construction.
• Students will gain an understanding of the basic definitions concerning computable real numbers.
• Students will gain an understanding of the basic definitions concerning polynomial-time reducibility and completeness.
• Students will gain an understanding of the basic definitions concerning polynomial-time, polynomial space, and nondeterministic polynomial-time computations.
• Students will gain an understanding of the basic definitions of decidable (recursive) and recursively enumerable.
• Students will gain an understanding of the basic nondeterministic model of computation, and how it differs from the deterministic model.
• Students will gain an understanding of the basic techniques that can be used to show that a language is undecidable.
• Students will gain an understanding of, and the ability to state, the Church-Turing thesis.
• Students will gain an understanding, and ability to use, the basic definitions concerning automata and grammars.
• Students will gain an understanding, and an ability, to use the basic mathematical notation concerning strings, languages, and functions.