User:Jeffj/CS6723/Syllabus
From A-State Computer Science Wiki
CS 6723 Computability
Summer 2019, Section 001, MTWRF 8:10am-10:00am, CSM 211 (3 credits)
Instructor
Dr. Jeff Jenness | |||
Office | CSM 132 | Office Hours | TR 11:00am-12:00pm and MW 11:00pm-12:00pm |
Phone | 870-972-3978 ext. 8117 | jeffj@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% Final 40%
Note: excessive unexcused absences will result in a 10% reduction in your overall grade.
Schedule
(subject to change)
Week | Topic | Reading | Assignment |
---|---|---|---|
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 |
Textbook
An Introduction to Formal Languages and Automata, 6th ed. (ISBN: 978-12840772470), by Peter Linz. Jones & Bartlett Learning, 2016. (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
- Mathematical Induction en.wikipedia.org/wiki/Mathematical_induction Wikipedia article