This subject deals the computations as mathematical objects. At present we have powerful computers, but they are limited
by finite memories and finite calculation times. From a practical point of view it is desirable to develop efficient algorithms,
while from a theoretical point of view it is important to determine whether or not the objective problem can be solved by
our computers (computability) at first. Next, it becomes a problem whether or not the problem can be solved in a realistic
time (computational complexity). In this course, we will formulate computational models such as Turing machine or While programs
and will discuss the computability theory and the computational complexity theory.

- To understand the concept of Turing machines and to be able to discuss the theories of computation by using them.
- To understand the concept of computability (Turin decidability) and to be able to show the decidability/undecidability of a given elemental problem.
- To understand the classes of computational complexites.

Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
---|---|---|---|

1. | Preliminaries (introduction, graphs, strings and languages) | Review the fundamental concepts of theory of computation by using Web, etc. | 190minutes |

2. | Automata (1) Deterministic finite automaton (DFA) |
Review the last lecture/read handouts | 190minutes |

3. | Automata (2) Nondeterministic finite automaton (NFA) |
Review the last lecture/read handouts | 190minutes |

4. | Automata (3) Equivalence of DFA and NFA, Regular languages |
Review the last lecture/read handouts | 190minutes |

5. | Turing machines (1) Definition and examples, Recognizability and decidability of languages |
Review the last lecture/read handouts | 190minutes |

6. | Turing machines (2) Variants of Turing machines, Nondeterministic Turing machines |
Review the last lecture/read handouts | 190minutes |

7. | Turing machines (3) Other computational models |
Review the last lecture/read handouts | 190minutes |

8. | Decidability (1) Algorithm and Church-Turing thesis |
Review the last lecture/read handouts | 190minutes |

9. | Decidability (2) Universal Turing machine |
Review the last lecture/read handouts | 190minutes |

10. | Decidability (3) Decidable languages |
Review the last lecture/read handouts | 190minutes |

11. | Decidability (4) Undecidability of the halting problem |
Review the last lecture/read handouts | 190minutes |

12. | Decidability (5) Turing unrecognizable languages |
Review the last lecture/read handouts | 190minutes |

13. | Computational complexity: Definition of computational complexity and order notations, The class P and the class NP |
Review the last lecture/read handouts | 190minutes |

14. | Final examination and review | Review the total of lectures | 190minutes |

Total. | - | - | 2660minutes |

Examination | Report | Total. | |
---|---|---|---|

1. | 30% | 10% | 40% |

2. | 30% | 10% | 40% |

3. | 10% | 10% | 20% |

Total. | 70% | 30% | - |

Reference: M. Sipser, "Introduction to the theory of computation 3rd editon," Cengage Learning, 2013; handout will be available

- Non-social and professional independence development course

Work experience | Work experience and relevance to the course content if applicatable |
---|---|

N/A | N/A |

Last modified : Sat Mar 21 13:04:02 JST 2020