User:Jeffj/CS6723/Syllabus

From A-State Computer Science Wiki
Jump to: navigation, search

CS 6723 Computability

Summer 2019, Section 001, MTWRF 8:10am-10:00am, CSM 211 (3 credits)

Instructor

Dr. Jeff Jenness
OfficeCSM 132Office HoursTR 11:00am-12:00pm and MW 11:00pm-12:00pm
Phone870-972-3978 ext. 8117Emailjeffj@astate.edu


Course Description

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.

Course Outcomes

  • 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.


Grading

Grades are assigned on a standard scale with the following weights:

Tests (2)60%
Final40%

Note: excessive unexcused absences will result in a 10% reduction in your overall grade.

Schedule

(subject to change)

Week  TopicReadingAssignment
1 Chapter 3: The Church-Turing Thesis
2 Chapter 4: Decidability
3 Chapter 5: Reducibility
4 Chapter 6: Advanced Topics
5 Review for Final

Textbook

Introduction to the Theory of Computation, 3rd ed. (ISBN: 978-1133187790), by Michael Sipser. Course Technology, 2012. (Amazon)

Resources

Go to the online repository

Software Downloads

JFLAP is software for exploring and experimenting with automata, machines and grammars.

Course Policies

See Department Policies which will be adhered to within the course.

See Also

create PDF version