可计算性和计算复杂度

定义2.1.1. 树的集合

𝔻

定义如下:

原子 $nil$ 是 $𝔻$ 的一个元素;
每当 $d_{1}$ 和 $d_{2}$ 是 $𝔻$ 的元素, 那么 $(d_{1} . d_{2})$ 也是; 并且
$𝔻$ 是满足前述两点的最小集合.

定义2.1.2. 函数

| • | : 𝔻 \to N

定义如下:

| d | = {\begin{matrix} 1 & , 如果 d \in A \\ | d_{1} | + | d_{2} | & , 如果 d = (d_{1} . d_{2}) \end{matrix}

其代表了一个数据值

d \in 𝔻

的大小(size).

第2.1.2小节 WHILE程序的句法

定义2.1.3. 令

Vars = {V_{0}, V_{1}, \dots}

是不同的变量. 我们使用约定

d, e, f, \dots \in 𝔻

和

X, Y, Z, \dots \in Vars

. 那么, WHILE的句法由以下语法给出:

\begin{array}{lclcll} Expressions & ∋ & E, F & ⩴ & X & (对于 X \in Vars) \\ | & d & (对于原子 d) \\ | & cons E F \\ | & hd E \\ | & tl E \\ | & =? E F \\ Commands & ∋ & C, D & ⩴ & X := E \\ | & C; D \\ | & while E do C \\ Programs & ∋ & P & ⩴ & read X; C; write Y \end{array}

这里的

X

和

Y

是不需要相异的输入变量和输出变量.

我们使用缩进来指明

while

和其他命令的作用域. 例如, 考虑以下两个命令:

第2.1.3小节非形式化的语义

第2.1.4小节真值和if-then-else

第2.1.5小节列表

第2.1.6小节数字

第2.1.7小节句法糖: 一些有用的宏记号

第2.2节 WHILE程序的语义

第2.2.1小节存储

第2.2.2小节对于表达式的求值

第2.2.3小节命令的执行

第2.2.4小节 WHILE程序的语义

第2.2.5小节计算语义值

第2.3节相等性与原子相等性的对比

第2.3.1小节更多的句法糖

练习

引用

第3章程序作为数据对象

第3.1节编程语言和模拟

定义3.1.1. 一个编程语言

L

由以下资料构成:

两个集合, $L -程序$ 和 $L -数据$ ;
一个函数 ${⟦ • ⟧}^{L} : L -程序 \to (L -数据 \to {L -数据}_{⊥})$ .

这里

{⟦ • ⟧}^{L}

是

L

的语义函数, 其将每个

L

-程序

p \in L -程序

与一个相应的部分函数

{⟦ p ⟧}^{L} : L -数据 \to {L -数据}_{⊥}

联系起来.
如果

L -程序 \subseteq L -数据

, 那么我们称

L

具有程序作为数据(programs-as-data)的性质. 另外, 如果

L -数据 \times L -数据 \subseteq L -数据

, 那么我们称

L

具有结对(pairing)性质.

定义3.1.2. 设

L -数据 = M -数据

. 语言

M

可以模拟

L

, 如果对于每个

p \in L -程序

, 存在一个

M

-程序

q

使得对于每个

d \in L -数据

, 我们有

{⟦ p ⟧}^{L} (d) ≃ {⟦ q ⟧}^{M} (d) .

等价地:

M

可以模拟

L

当且仅当存在一个完全函数

f : L -程序 \to M -程序

满足对于每个

L

-程序

p

都有

{⟦ p ⟧}^{L} = {⟦ f (p) ⟧}^{M} .

语言

L

等价于语言

M

, 记作

L \equiv M

, 如果语言

L

和语言

M

可以互相模拟.

这个定义表达了

L

和

M

可以计算相同函数的事实; 但是其并没有断言存在任何构造性的方式来获得一个等价于给定

L

-程序的

M

-程序. 本章的剩余部分关心的是模拟是如何计算性地完成的, 要么通过转换 (应用一个编译函数), 要么是通过解释. 然而, 首先我们需要一种方式来将程序视为数据对象.

第3.2节在

𝔻

中表示

WHILE

程序

之前我们已经给过了

WHILE -程序

和

WHILE -数据

的句法. 假设我们想要将一个WHILE程序喂给另外一个WHILE程序作为输入. 目前这是不可行的, 仅仅是因为

WHILE -程序

的元素并非

WHILE -数据

中的对象. 因此, 我们现在需要对于WHILE程序给出一种程序作为数据表示.

定义3.2.1. 令

{:=,;, while, var, quote, cons, hd, tl, =?, nil}

代表

𝔻

的

10

个相异元素. WHILE程序

p

的表示

可计算性和计算复杂度

第1章引论

第2章 WHILE语言

第2.1节 WHILE数据和程序的句法

第2.1.1小节二叉树作为数据值

第2.1.2小节 WHILE程序的句法

第2.1.3小节非形式化的语义

第2.1.4小节真值和if-then-else

第2.1.5小节列表

第2.1.6小节数字

第2.1.7小节句法糖: 一些有用的宏记号

第2.2节 WHILE程序的语义

第2.2.1小节存储

第2.2.2小节对于表达式的求值

第2.2.3小节命令的执行

第2.2.4小节 WHILE程序的语义

第2.2.5小节计算语义值

第2.3节相等性与原子相等性的对比

第2.3.1小节更多的句法糖

练习

引用

第3章程序作为数据对象

第3.1节编程语言和模拟

第3.2节在 $𝔻$ 中表示 $WHILE$ 程序

第4章自解释: $WHILE$ 和 $I$ 的通用程序

第5章可计算理论的基本

第6章元编程, 自应用, 和编译器生成

第7章其他顺序计算模型

第8章可计算概念的健壮性

第9章函数式语言所施行的计算

第10章一些自然的不可解问题

第11章 Hilbert第十问题

第12章推理系统和Gödel不完备性定理

第13章基于数字的可计算理论

第14章更多可计算性的抽象方式

可计算性和计算复杂度

第1章 引论

第2章 WHILE语言

第2.1节 WHILE数据和程序的句法

第2.1.1小节 二叉树作为数据值

第2.1.2小节 WHILE程序的句法

第2.1.3小节 非形式化的语义

第2.1.4小节 真值和if-then-else

第2.1.5小节 列表

第2.1.6小节 数字

第2.1.7小节 句法糖: 一些有用的宏记号

第2.2节 WHILE程序的语义

第2.2.1小节 存储

第2.2.2小节 对于表达式的求值

第2.2.3小节 命令的执行

第2.2.4小节 WHILE程序的语义

第2.2.5小节 计算语义值

第2.3节 相等性与原子相等性的对比

第2.3.1小节 更多的句法糖

练习

引用

第3章 程序作为数据对象

第3.1节 编程语言和模拟

第3.2节 在𝔻中表示WHILE程序

第4章 自解释: WHILE和I的通用程序

第5章 可计算理论的基本

第6章 元编程, 自应用, 和编译器生成

第7章 其他顺序计算模型

第8章 可计算概念的健壮性

第9章 函数式语言所施行的计算

第10章 一些自然的不可解问题

第11章 Hilbert第十问题

第12章 推理系统和Gödel不完备性定理

第13章 基于数字的可计算理论

第14章 更多可计算性的抽象方式

第1章引论

第2.1.1小节二叉树作为数据值

第2.1.3小节非形式化的语义

第2.1.4小节真值和if-then-else

第2.1.5小节列表

第2.1.6小节数字

第2.1.7小节句法糖: 一些有用的宏记号

第2.2.1小节存储

第2.2.2小节对于表达式的求值

第2.2.3小节命令的执行

第2.2.5小节计算语义值

第2.3节相等性与原子相等性的对比

第2.3.1小节更多的句法糖

第3章程序作为数据对象

第3.1节编程语言和模拟

第3.2节在 $𝔻$ 中表示 $WHILE$ 程序

第4章自解释: $WHILE$ 和 $I$ 的通用程序

第5章可计算理论的基本

第6章元编程, 自应用, 和编译器生成

第7章其他顺序计算模型

第8章可计算概念的健壮性

第9章函数式语言所施行的计算

第10章一些自然的不可解问题

第12章推理系统和Gödel不完备性定理

第13章基于数字的可计算理论

第14章更多可计算性的抽象方式