计算理论06_NTM分解.ppt

Part II: Computability Theory Outline for today 复习 Nondeterministic TMs ep139 ，cp90 Computing with Nondeterministic TMs Computing with Nondeterministic TMs Simulating Nondeterministic TMs with Deterministic Ones ep138 定理c4.10 确定方式模拟模拟NTM Simulating Nondeterministic TMs with Deterministic Ones ep138 定理c4.10 确定方式模拟模拟NTM Simulating Nondeterministic TMs with Deterministic Ones ep138 定理c4.10 确定方式模拟模拟NTM 上页已有， 可略 Simulating Nondeterministic TMs with Deterministic Ones ep138 定理c4.10 确定方式模拟模拟NTM 上页已有， 可略 Simulating Nondeterministic TMs with Deterministic Ones ep138 定理c4.10 确定方式模拟模拟NTM 上页已有， 可略 Breadth First 注意，有两种前途，路径不定长，所以广度优先好 Breadth First 注意，有两种前途，路径不定长，所以广度优先好 Breadth First 注意，有两种前途，路径不定长，所以广度优先好 Nondeterministic TMs ep138 cp89 非确定图灵机 复习 Nondeterministic TMs ep138 cp89 非确定图灵机 复习 Robustness 稳健性结论 复习 Robustness 稳健性结论 Enumerating Languages 枚举语言， ep140 ， cp91 Enumerating = Recognizing 枚举~ 识别 cp91 Enumerating = Recognizing 枚举~ 识别 cp91 Enumerating = Recognizing 枚举~ 识别 cp91 Other Computational Models 其他计算模型，ep141， cp92 Other Computational Models 其他计算模型，ep141， cp92 Other Computational Models 其他计算模型，ep141， cp92 Importance of the Church-Turing Thesis ep142, cp93 Importance of the Church-Turing Thesis ep142, cp93 c4.3 “Algorithm” 算法简史 ep142 cp92 c4.3 “Algorithm” 算法简史 ep142 cp92 Hilbert’s 10th Problem 希尔伯特第 10 问题 ep142，cp92 Hilbert’s 10th Problem希尔伯特第 10 问题ep142，cp92 Diophantine Equations ep143, cp93 Diophantine Equations ep143, cp93 Diophantine Equations ep143, cp93 (Un)solving Hilbert’s 10th ep143, cp93 (Un)solving Hilbert’s 10th ep143, cp93 Chapter 5. Decidability ep151 cp99 Decidability ep151 cp99 Decidability ep151 cp99 Describing TM Programs ep152 cp99 Describing TM Programs ep152 cp99 Deciding Regular Languages 定理c5.1 ep152, cp99 Deciding Regular Languages 定理c5.1 ep152, cp99 ADFA is Decidable (Thm. C5.1) ep 152 cp99 ADFA is Decidable (Thm. C5.1) ep 152 cp99 ADFA is Decidable (Thm. C