From A-State Computer Science Wiki
< User:Jeffj‎ | CS6723
Revision as of 08:29, 1 July 2019 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 3: The Church-Turing Thesis
2 Chapter 4: Decidability
3 Chapter 5:.Reducibility
4 Chapter 6: Advanced Topics in Computability Theory
5 Review for Final


An Introduction to Formal Languages and Automata, 6th ed. (ISBN: 978-12840772470), by Peter Linz. Jones & Bartlett Learning, 2016. (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