CS 6723 Computability
Summer 2019, Section 001, MTWRF 8:10am-10:00am, CSM 211 (3 credits)
|Dr. Jeff Jenness|
|Office||CSM 132||Office Hours||TR 11:00am-12:00pm and MW 11:00pm-12:00pm|
|Phone||870-972-3978 ext. firstname.lastname@example.org|
- CS 6723. Computability Theory
- Turing machines and equivalent models of computation. The universal Turing machine and unsolvability results. Study of computable functions. Problem classification and hierarchy. Prerequisites: CS 5723 or permission of professor. Spring even.
Program Specific Outcomes
- (Reinforced) M.S. Computer Science graduate students should have a deeper understanding of the theory and application of algorithms, programming languages, and computer processes.
- Understand Turing machine model, and variants of Turing machines and Church-Turing Thesis.
- Understand and could apply important concepts of computability theory and complexity theory.
- Understand the limits of algorithmic solvability (computability): what is solvable and what is not solvable.
- Understand the issues of complexity: even when a problem is computationally solvable in principle.
Grades are assigned on a standard scale with the following weights:
Tests (2) 60% Final 40%
Note: excessive unexcused absences will result in a 10% reduction in your overall grade.
(subject to change)
|1||Chapter 3: The Church-Turing Thesis|
|2||Chapter 4: Decidability|
|3||Chapter 5: Reducibility|
|4||Chapter 6: Advanced Topics|
|5||Review for Final|
Introduction to the Theory of Computation, 3rd ed. (ISBN: 978-1133187790), by Michael Sipser. Course Technology, 2012. (Amazon)
- Go to the online repository
- JFLAP is software for exploring and experimenting with automata, machines and grammars.
See Department Policies which will be adhered to within the course.
- Mathematical Induction en.wikipedia.org/wiki/Mathematical_induction Wikipedia article