计算理论¶
手写笔记如下:(仅供参考,可能存在笔误或者错误)
TOC 手写笔记 by HobbitQia
- Preliminaries (Language) - P2
-
Automata - P4
- NFA (Non-deterministic Finite Automata) - P7
-
REX (Regular Expression) - P12
- Pumping Theorem - P15
-
CFG (Context-Free Grammar) - P17
- CNF (Chomsky Norm Form) - P18
-
PDA (Pushdown Automata) - P20
- CFG <-> PDA - P22
- Pumping Theorem for CFL - P26
-
Turing Machine - P30
- TM - P35
- NTM (non-deterministic TM) - P36
-
Desicion Problem - P38
- Church-Turing Thesis - P38
- Encode and Decision Problem - P38
- Reduction - P41
- Countable Problem - P43
- Halting Problem - P45
- Rice's Theorem - P48
- Self-Print Program - P51
- Turing Enumerable - P53
-
Computability - P54
- Numerical Function - P54
- \(\mu\)-recursive - P59
-
Conrestricted Grammar - P61
-
Complexity Problem- P62
-
Time Complexity - P62
- P&NP - P63
- NP Complete Problem - P66
-
Space Complexity - P70
- PSAPCE/NPSPACE - P70
- Hierachy Theorem - P71
-
最后更新:
2024年1月20日 14:12:23
创建日期: 2023年9月30日 09:19:27
创建日期: 2023年9月30日 09:19:27