2023 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 (W8E-308(W834)) / 3-4 Fri (W8E-308(W834))
- Class
- -
- Course Code
- MCS.T323
- Number of credits
- 200
- Course offered
- 2023
- Offered quarter
- 3Q
- Syllabus updated
- Jul 8, 2025
- Language
- Japanese
Syllabus
Course overview and goals
This course gives students an introduction of the theory of computability, by extending knowledge of the theory of automata and language. This course mainly employs the model of the Turing machine. Students will learn the basic notion of computability on the Turing machine, which provides mathematical properties on the software and hardware of computers. 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, the Post correspondence problem, and the recursion theorem.
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.
Keywords
Computation, Computability, the Turing machine, the Church-Turing thesis, variations of the Turing machine, decidability, diagonal arguments, halting problems, reducibility, the Post correspondence problem, the recursion theorem
Competencies
- Specialist skills
- Intercultural skills
- Communication skills
- Critical thinking skills
- Practical and/or problem-solving skills
Class flow
The course consists of a standard lecture or practice exercise. A practice exercise includes supplementary materials and answers for the quizzes. Each class also includes quizzes on the contents of this class or previous classes.
Course schedule/Objectives
| Course schedule | Objectives | |
|---|---|---|
| Class 1 | Introduction, computation and computability, Turing machine I | Understand the notion of the Turing machine |
| Class 2 | Turing machine II, the Church-Turing thesis, variations of the Turing machine I | Understand the content of the Church-Turing thesis |
| Class 3 | Variations of the Turing machine II | Understand the method on the proof for the equivalence on the variations |
| Class 4 | Exercise-style lecture on the Turing machine and its variations | Understand the properties of the variations of the Turing machine |
| Class 5 | Decidability | Understand the method for the proofs on decidability |
| Class 6 | The diagonal arguments, the halting problem | Understand the application of the diagonal arguments |
| Class 7 | Reducibility | Understand the notion of reducibility |
| Class 8 | Exercise-style lecture on decidability and reducibility | Understand the methods on reducibility |
| Class 9 | Undecidability on language theory | Understand the methods for the proofs |
| Class 10 | The Post correspondence problem | Understand the problem and its reducibility |
| Class 11 | Mapping reducibility | Understand the notion of mapping reducibility |
| Class 12 | The recursion theorem | Understand the argument of the proof |
| Class 13 | Exercise-style lecture on mapping reducibility and the recursion theorem | Understand the methods on mapping reducibility |
| Class 14 | Introduction to the complexity theory | Understand the basic notion of computational complexity |
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, Cengage Learning, 2012, ISBN 978-1133187790.
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.