From A-State Computer Science Wiki
< User:Jeffj‎ | CS6723
Revision as of 09:19, 30 May 2020 by Jeffj (Talk | contribs)

Jump to: navigation, search

CS 6723 Computability

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


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

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.


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

Tests (2)60%

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


(subject to change)

Week  TopicReadingAssignment
1 Chapter 9: Turing Machines
2 Chapter 10: Other Models of Turing Machines
3 Chapter 11:.A Hierarchy of Formal Languages and Automata
4 Chapter 12: Limits of Algorithmic Computation
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

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