《计算的数学理论 上》

前言1

第一章可计算性3

引言3

1-1 有穷自动机4

1-1·1　正则表达式6

1-1·2 有穷自动机10

1-1·3 转换图12

1-1·4 Kleene定理15

1-1·5　等价定理22

1-2 Turing机25

1-2·1　Turing机26

1-2·2 Post机30

1-2·3 具有下推存贮？有穷机35

1-2·4 不确定性42

1-3　作为接收？的Turing机45

1-3·1　递归可？集合45

1-3·2 递归集合47

1-3·3 形式语言48

1-4 作为发生？的Turing机52

1-4·1　原始递归函数54

1-4·2　部分递归函数61

1-5 作为算法的Turing机65

1-5·1 是／否问题类的可解性66

1-5·2 Turing机的停机问题68

1-5·3 半Thue系统的字问题70

1-5·4　Post对应问题73

1-5·5 是／否问题类的部分可解性78

文献评论，文献目录，习题83

第二章　谓词演算97

引言97

2-1基本概念102

2-1·1 句法102

2-1·2 字义（说明）108

2-1·3 真确的良构式116

2-1·4 良构式的等价性125

2-1·5 良构式的正则形式132

2-1·6　真确性问题137

2-2 自然演绎法140

2-2·1 连词法则143

2-2·2　？词法则152

2-2·3　算符法则160

2-3　分解的方法164

2-3·1 子句形式165

2-3·2　Herband过程171

2-3·3　联合法则178

2-3·4 分解法则183

文献评论，文献目录，习题189