Syllabus Application
CS 407
Theory of Computation
Faculty
Faculty of Engineering and Natural Sciences
Semester
Spring 2025-2026
Course
CS 407 -
Theory of Computation
Time/Place
Time
Week Day
Place
Date
10:40-12:30
Tue
FASS-1101
Feb 16-May 22, 2026
14:40-15:30
Fri
FASS-1099
Feb 16-May 22, 2026
Level of course
Undergraduate
Course Credits
SU Credit:3, ECTS:6, Basic:2, Engineering:4
Prerequisites
CS 302
Corequisites
CS 407R
Course Type
Lecture
Instructor(s) Information
Kemal İnan
- Email: inan@sabanciuniv.edu
Office Hours for Kemal İnan: by appointment
Course Information
Catalog Course Description
Turing machines; recursive numbers and Turing computability; solvability and unsolvable problems; concepts of and results on computational complexity; some NP complete problems.
Course Learning Outcomes:
| 1. | Upon completion of the course, student should be able to : Construct deterministic and nondeterministic Turing Machines and their multitape and other variants by using compositional techniques for formulating and solving decision problems of practical or theoretical significance |
|---|---|
| 2. | Demonstrate the equivalence between different computational tools such as different variants of the Turing Machines using concepts of decidability and semidecidability |
| 3. | Use random access machines (RAMs) and generalized grammars (or rewriting systems) as yet other tools of computation that are equivalent to the TM. |
| 4. | Demonstrate the fact that all multivariable functions on integers (primitive recursive functions) can be derived from simple functions by repeated use of composition and recursion |
| 5. | demonstrate that not all reasonably computable functions are recursive and extend this set to mu-recursive functions by introducing the minimalizable functions |
| 6. | Show that the computational power of generalized grammars, mu-recursive functions and Turing machines are identical |
| 7. | Understand and use the concept of a Universal Turing Machine (UTM) and compute a concrete version of it using either the classical 3-tape model or a RAM |
| 8. | Demonstrate the undecidability of the famous halting problem for TMs and using Turing-computable reductions generate a host of undecidable and un-semidecidable problems |
| 9. | Understand the significance of the busy-beaver problem as an example of the intuitively difficult concept of an uncomputable function |
| 10. | Show that a computer program can use its own definition within its program in a recursive manner by using the recursion theorem and apply this idea to a number of novel decidability problems |
| 11. | Formulate problems of computational complexity and use the associated tools to categorize a problem to be in the polynomial (P), nondeterministic polynomial (NP) , NP-complete or NP-hard class |
| 12. | Generate the starting branches of the tree of NP-complete problems by using polynomial reductions after establishing the SAT problem as the root of this tree using Cook's Theorem where the nodes involved in this tree are the well-known NP-complete problems like the Hamiltonian Cycle , Traveling Salesman and others |
| 13. | Extend the computational time complexity problem to space complexity and formulate some game-theoretic problems that are P-space complete |
Course Objective
To introduce the foundations of computations in terms of the hierarchy of expressibility of languages culminating with the Turing Machine ; the equivalences between different computational mechanisms as a warm-up to the Church-Turing thesis ; the theoretical limits of computation in terms of decidability and semidecidability of problems starting with the halting problem of a TM and computability of functions ; the practical limits to computation in terms of the tractability of problems , that is, the growth of necessary time and space resources as a function of the size of the problem instances ; recursion theorem as the critical and possibly the only link between existing human-made technologies and self-reproducing biological mechanisms.
-
Course Materials
Resources:
Main Text :
H. R. Lewis & C. H. Papadmitriou , Elements of Theory of Computation,
2nd ed. Prentice Hall 1998 (out-of-print; e-copy available)
AuxiliaryTexts :
(1)M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning 2003
(2) M. A. Garey& D. S. Johnson , Computers and Intractability, Bell Telephone Labs 1979
H. R. Lewis & C. H. Papadmitriou , Elements of Theory of Computation,
2nd ed. Prentice Hall 1998 (out-of-print; e-copy available)
AuxiliaryTexts :
(1)M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning 2003
(2) M. A. Garey& D. S. Johnson , Computers and Intractability, Bell Telephone Labs 1979