计算的本质

封面介绍X

前言XI

第1章　刚好够用的Ruby基础1

1.1　交互式Ruby Shell1

1.2　值2

1.2.1　基本...

封面介绍X

前言XI

第1章　刚好够用的Ruby基础1

1.1　交互式Ruby Shell1

1.2　值2

1.2.1　基本数据2

1.2.2　数据结构3

1.2.3　proc4

1.3　控制流4

1.4　对象和方法5

1.5　类和模块6

1.6　其他特性7

1.6.1　局部变量和赋值7

1.6.2　字符串插值8

1.6.3　检查对象8

1.6.4　打印字符串8

1.6.5　可变参数方法（variadic method）9

1.6.6　代码块9

1.6.7　枚举类型10

1.6.8　结构体11

1.6.9　给内置对象扩展方法（Monkey Patching）12

1.6.10　定义常量13

1.6.11　删除常量13

第一部分　程序和机器

第2章　程序的含义17

2.1　“含义”的含义18

2.2　语法19

2.3　操作语义19

2.3.1　小步语义20

2.3.2　大步语义40

2.4　指称语义46

2.4.1　表达式46

2.4.2　语句49

2.4.3　应用51

2.5　形式化语义实践52

2.5.1　形式化52

2.5.2　找到含义53

2.5.3　备选方案53

2.6　实现语法解析器54

第3章　最简单的计算机59

3.1　确定性有限自动机59

3.1.1　状态、规则和输入60

3.1.2　输出60

3.1.3　确定性61

3.1.4　模拟62

3.2　非确定性有限自动机65

3.2.1　非确定性65

3.2.2　自由移动（free move）71

3.3　正则表达式74

3.3.1　语法75

3.3.2　语义78

3.3.3　解析86

3.4　等价性88

第4章　增加计算能力97

4.1　确定性下推自动机100

4.1.1　存储100

4.1.2　规则101

4.1.3　确定性103

4.1.4　模拟103

4.2　非确定性下推自动机110

4.2.1　模拟113

4.2.2　不等价115

4.3　使用下推自动机进行分析116

4.3.1　词法分析116

4.3.2　语法分析118

4.3.3　实践性122

4.4　有多少能力123

第5章　终极机器125

5.1　确定型图灵机125

5.1.1　存储126

5.1.2　规则127

5.1.3　确定性131

5.1.4　模拟131

5.2　非确定型图灵机136

5.3　最大能力137

5.3.1　内部存储137

5.3.2　子例程140

5.3.3　多纸带141

5.3.4　多维纸带142

5.4　通用机器142

5.4.1　编码144

5.4.2　模拟145

第二部分　计算与可计算性

第6章　从零开始编程149

6.1　模拟lambda演算150

6.1.1　使用proc工作150

6.1.2　问题152

6.1.3　数字153

6.1.4　布尔值156

6.1.5　谓词160

6.1.6　有序对161

6.1.7　数值运算161

6.1.8　列表168

6.1.9　字符串172

6.1.10　解决方案174

6.1.11　高级编程技术178

6.2　实现lambda演算184

6.2.1　语法184

6.2.2　语义186

6.2.3　语法分析191

第7章　通用性无处不在193

7.1　lambda演算193

7.2　部分递归函数196

7.3　SKI组合子演算201

7.4　约塔（Iota）210

7.5　标签系统213

7.6　循环标签系统220

7.7　Conway的生命游戏229

7.8　rule 110231

7.9　Wolfram的2,3图灵机234

第8章　不可能的程序235

8.1　基本事实236

8.1.1　能执行算法的通用系统236

8.1.2　能够替代图灵机的程序239

8.1.3　代码即数据239

8.1.4　可以永远循环的通用系统241

8.1.5　能引用自身的程序245

8.2　可判定性250

8.3　停机问题251

8.3.1　构建停机检查器251

8.3.2　永远不会有结果254

8.4　其他不可判定的问题258

8.5　令人沮丧的暗示260

8.6　发生上述情况的原因261

8.7　处理不可计算性262

第9章　在“玩偶国”中编程265

9.1　抽象解释266

9.1.1　路线规划266

9.1.2　抽象：乘法的符号267

9.1.3　安全和近似：增加符号270

9.2　静态语义274

9.2.1　实现275

9.2.2　好处和限制281

9.3　应用284

后记285

Ruby 是一种面向表达式的语言：每一段有效的代码执行之后都要产生一个值。下面快速浏览一下 Ruby 中不同类型的值。 1.2.1　基本数据 如我们所料，Ruby 支持布尔型（Boolean）、数值型（number）和字符串（string），且它们都支持常规运算： >> (true && false) || true => true >> (...

(查看全部试读)