2024 Faculty Courses School of Computing Undergraduate major in Mathematical and Computing Science
Theory of Computation
- Academic unit or major
- Undergraduate major in Mathematical and Computing Science
- Instructor(s)
- Keisuke Tanaka / Kenji Yasunaga
- Class Format
- Lecture (Face-to-face)
- Media-enhanced courses
- -
- Day of week/Period
(Classrooms) - 3-4 Tue / 3-4 Fri
- Class
- -
- Course Code
- MCS.T323
- Number of credits
- 200
- Course offered
- 2024
- Offered quarter
- 3Q
- Syllabus updated
- Mar 14, 2025
- Language
- Japanese
Syllabus
Course overview and goals
This course gives students an introduction to the theory of computability and computational complexity by extending knowledge of the theory of automata and language. This course mainly employs the Turing machine model. Students will learn the concept of computability on the Turing machine, which provides mathematical properties on the software and hardware of computers, and concepts such as complexity classes and NP-completeness, which represent the complexity of computational problems. The topics studied in this course include the Turing machine, the Church-Turing thesis, variations of the Turing machine, decidability, diagonal arguments, halting problems, reducibility, time complexity, class P and NP, NP-completeness, and space complexity.
Course description and aims
By the end of this course, students will be able to understand:
1) notions of computability
2) the model of the Turing machine and its variations
3) techniques for the proofs of computability
4) notions of computational complexity
5) the classes P and NP, NP-completeness.
Keywords
computability, Turing machine, Church-Turing thesis, decidability, diagonal argument, halting problem, computational complexity, the classes P and NP, NP-completeness, circuit complexity, randomized computation
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
Each class includes quizzes on the contents of this class or previous classes.
The course consists of standard lectures and practice exercises. A practice exercise includes supplementary materials and answers for the quizzes.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Introduction, computation and computability, Turing machine | Understand the notion of the Turing machine |
| Class 2 | The Church-Turing thesis, variations of the Turing machine | Understand the content of the Church-Turing thesis |
| Class 3 | Decidability | Understand the method for the proofs on decidability |
| Class 4 | The diagonal arguments, the halting problem | Understand the application of the diagonal arguments |
| Class 5 | Reducibility | Understand the notion of reducibility |
| Class 6 | Mapping reducibility | Understand the notion of mapping reducibility |
| Class 7 | The recursion theorem | Understand the argument of the proof |
| Class 8 | Time complexity and the class P | Understand the notion of time complexity |
| Class 9 | The class NP and the P vs NP problem | Understand the complexity class NP |
| Class 10 | NP-completeness | Understand the notion of NP-completeness |
| Class 11 | Space complexity | Understand the notion of space complexity |
| Class 12 | Hierarchy theorems and relativization | Understand hierarchy theorems and the notion of relativization |
| Class 13 | Circuit complexity | Understand the notion of circuit complexity |
| Class 14 | Randomized computation | Understand the notion of probabilistic Turing machine |
Study advice (preparation and review)
To enhance effective learning, students are encouraged to spend approximately 100 minutes preparing for class and another 100 minutes reviewing class content afterwards (including assignments) for each class. They should do so by referring to textbooks and other course material.
Textbook(s)
Introduction to the Theory of Computation, Third Edition, Michael Sipser, Course Technology, 2012, ISBN 9781133187790.
Reference books, course materials, etc.
References will be announced in the first class.
Evaluation methods and criteria
The evaluation consists of in-class quizzes (60%) and the final exam (40%).
Related courses
- MCS.T213 ： Introduction to Algorithms and Data Structures
- MCS.T214 ： Theory of Automata and Languages
- MCS.T411 ： Computational Complexity Theory
- MCS.T405 ： Theory of Algorithms
- MCS.T508 ： Theory of Cryptography
Prerequisites
It is preferable to have the knowledge on the basics of algorithms and data structures and on the theory of automata and languages.