National Central University
Uedu Main Site
Explore Uedu
Student Console
Register as Member/Login
Research Informed Consent Center
Survey Center
UeduGPTs
Aida Learning Companion
Agentic AI
Local AI
Uedu Code
Find an Advisor
Paper Reading
Uedu Note
Uedu Open
Uedu Jupyter
Language Learning
Lingua Writing
My Writing History
Cognomics Test Toolkit
Uedu Finance
Educational Big Data Challenge
Uedu Interdisciplinary General Education
Uedu Physics
Uedu Calculus
Uedu Biology
Uedu Chemistry
Uedu Electronics
Uedu Semiconductor
Uedu AI
Uedu Statistics
Uedu UAV
Teaching Materials
Literature Hall
Taiwan: Four Hundred Years
Uedu Science
Teacher Console
Course Setup
Support & Messages
Uptime Data

UeduGPTs

--

Jupyters

6

Local AI

--

Uedu Code

--

CISOSE26 Local AI Uedu Code UG26
中央大學 AQI 55 25°C PM2.5 14
AI Reply Desktop Notifications

Show a desktop notification when the AI TA finishes replying

Chat Message Notifications

Notify me when classmates post messages in the forum

Sound notification

Play an alert sound whenever there is a new notification

More settings
Account settings Data privacy settings Research Informed Consent Form
Uedu Open / Theory of Computation
18.404J

Theory of Computation

Prof. Michael Sipser | Fall 2020
Data Science, Analytics & Computer Technology Computer Science Science & Math Mathematics Engineering Computation Discrete Mathematics Theory of Computation
Go to original course
CC BY-NC-SA 4.0
Course introduction
This course emphasizes computability and computational complexity theory. Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.
Course Information
SourceMIT 開放式課程
DepartmentElectrical Engineering and Computer Science
LanguageEnglish
Number of videos25
Course videos (25)
1
1. Introduction, Finite Automata, Regular Expressions
1. Introduction, Finite Automata, Regular Expressions
2
2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
3
3. Regular Pumping Lemma, Conversion of FA to Regular Expressions
3. Regular Pumping Lemma, Conversion of FA to Regular Expressions
4
4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
5
5. CF Pumping Lemma, Turing Machines
5. CF Pumping Lemma, Turing Machines
6
6. TM Variants, Church-Turing Thesis
6. TM Variants, Church-Turing Thesis
7
7. Decision Problems for Automata and Grammars
7. Decision Problems for Automata and Grammars
8
8. Undecidability
8. Undecidability
9
9. Reducibility
9. Reducibility
10
10. Computation History Method
10. Computation History Method
11
11. Recursion Theorem and Logic
11. Recursion Theorem and Logic
12
12. Time Complexity
12. Time Complexity
13
14. P and NP, SAT, Poly-Time Reducibility
14. P and NP, SAT, Poly-Time Reducibility
14
15. NP-Completeness
15. NP-Completeness
15
16. Cook-Levin Theorem
16. Cook-Levin Theorem
16
17. Space Complexity, PSPACE, Savitch's Theorem
17. Space Complexity, PSPACE, Savitch's Theorem
17
18. PSPACE-Completeness
18. PSPACE-Completeness
18
19. Games, Generalized Geography
19. Games, Generalized Geography
19
20. L and NL, NL = coNL
20. L and NL, NL = coNL
20
21. Hierarchy Theorems
21. Hierarchy Theorems
21
22. Provably Intractable Problems, Oracles
22. Provably Intractable Problems, Oracles
22
23. Probabilistic Computation, BPP
23. Probabilistic Computation, BPP
23
24. Probabilistic Computation (cont.)
24. Probabilistic Computation (cont.)
24
25. Interactive Proof Systems, IP
25. Interactive Proof Systems, IP
25
26. coNP is a subset of IP
26. coNP is a subset of IP