《计算理论导引》学习笔记

计算理论 学习笔记

ITOC（Introduction to Theory Of Computation)主讲三大内容：什么是计算；什么可计算；如何度量计算问题的效率。大致上来说，首先我们需要一种准确的表达法来说明到底计算本质上是什么，不同的科学家抽象出不同的计算模型，于是我们就要考查这些模型的表达能力(第一部分)。其次，我们发现计算是有局限的，不是什么问题都能计算，那到底什么是可计算的问题呢？有什么问题是不可计算的呢（不存在算法）？（第二部分）如果某些问题是可解的，存在某种算法可以解决这个问题，那么这种算法的效率如何度量呢？我们需要一种通用的标准度量，並建立相關理論。（第三部分）

2016年元月 by Bintou

第0章 引論

0.1 自动机、可计算性、复杂性

0.2 數學表示與術語

0.3 定義、定理與證明

0.4 证明的类型

學習時間安排：一天或者半天；應該無難點。

第1章 正則語言

Language（语言），对计算问题的高度抽象表达。整本书的重点是“计算“，如果能体会出在描述计算理论时语言的定义所产生的巨大作用，则理解就上了一个台阶。只是，第一章并不能产生这么大的效用，需持续关注。

1.1 有限自动机

概念：FA、語言、正則語言、正則操作
定理：正則語言類在正則操作（並、交、串聯）下封閉；

1.2 非确定性

重點：體會計算的非確定性
難點：DFA與NFA的等價

对非确定性的两种解读：1、并行执行；2、总是猜对执行路径。哪一种更好？
问题：为什么我们需要“不确定性“？

1.3 正则表达

1.4 非正则语言

要點：自動機的計算侷限
難點：Pumping Lemma及其應用

2016年元月22日上午，自己重新複習了一遍第1章，感覺很容易，然而依然感覺有意思。

第2章 上下文无关语言

2.1 上下文无关文法

重点：歧义性

问题1：为什么把能以不同方式生成的字符串称为歧义？
问题2：为什么需要“最左派生“这个定义？

2.2 下推自動機

下退自动机（PDA）比有限自动机的能力更强，主要体现在哪里？为什么PDA能力会更强呢？

问题1：在Lemma 2.21的证明中，如何确保可被匹配的串w一定会被匹配？
回答：构造算法是非确定性算法。重点体会非确定性选择的含义。

问题2：在Lemma 2.27的证明中，如果p不可达q，那么$A_{pq}$的构造是否还合法（会出现不合法的情况）？
回答：暂无

2.3 非上下文無關語言

2.4 （忽略）

第3章 丘奇-圖靈命題

這一章的主要內容介紹圖靈機及其相關概念。其主旨是進一步刻畫計算的本質。重點要區分兩個概念：圖靈可判定與圖靈可識別。從算法的角度看，前者要求計算這有限步之後停機，而後者沒有。明白了這個區別，就對計算機的有限計算有了更深入的理解。

3.1 圖靈機

一種計算模型

3.2 圖靈機的各種變形

3.3 算法的定義

第4章 判定性

4.1 可判定语言

4.2 停机问题

重点：对角线法、停机问题不可判定的证明

5 可归约性

这一章的重点是理解归约的本质、过程与应用。

5.1 语言理论中的不可判定问题

针对RL与CFL的若干语言形成的判定性问题进行证明。

5.2 一个简单的不可判定问题：PCP问题

只是一个证明！PCP问题的描述很简单，其不可判定性倒是颇令人感到意外。这里除了一个结论，一个冗长的证明外，内容不多。

5.3 不可判定问题的形式化定义：映射可归约性

重点：Mapping Reducibility的定义

第6章 计算理论的高级专题

61. 递归定理

递归定理展示“程序自我复制是可能的“这样一个简单而令人吃惊的结论。

The Quine Page，里面收集了大量不同语言写成的Quine程序：自己输出自己源代码的程序。