前言
本系列是北京大学数学科学学院理论计算机科学基础的课程内容总结。上半部分从程序设计语言$\mathscr{S}$开始，讲到Turing机停机问题的判定性。
记号规定和定义
只考虑自然数集$N$。设$f$是$S\times T$上的二元关系。若$a\in S , f(a) = \varnothing$，记$f(a) \uparrow $。不然若$f(a) = {b}$则记$f(a) \downarrow $.若\(\forall a \in S,f(a) \downarrow\)，则函数称为全函数，否则成为部分函数。特别地若\(\forall a \in S,f(a) \uparrow\)，其成为空函数。
字母表$A$的元素有穷序列记作字符串或字。空串$\varepsilon$。全体字符串记为\(A^*\).特别地，\(uv\)即字符串连接。\((A^*)^n \rightarrow A^*\)的部分函数为部分字函数。
$\mathscr{S}$语言与Church-Turing论题
Church-Turing论题：直观可计算的函数类就是Turing机以及任何与其等价的计算模型可计算/定义的函数类。我们指出如下$\mathscr{S}$语言是直观可计算的，其同时等价于Turing可计算模型。
$\mathscr{S}$语言：输入变量\(X_1,\cdots,X_n\);输出变量$Y$;中间变量$Z_1,Z_2,\cdots$.使用标号$A,B,C,\cdots$。其语句只有三个：$V \leftarrow V+1,V \leftarrow V-1,\text{IF } V\neq 0 \text{ GOTO } L.$
特别地，$V=0$时$V \leftarrow V-1$不执行。程序开始时所有变量都是0.必要时引入空语句$V \leftarrow V$。由若干语句构成的计算过程成为程序。
所谓状态即记录所有变量的值的一个集合。描述所有变量的值，如${X= 1,Y=0}.$ 对于具体的处在某指令前(即即将执行第$i$条指令时)的状态，称为快相$(i,\sigma)$。计算结束时的快相为终点快相，其标号为最后一条指令标号+1。定义$(i,\sigma)$的后继$(j,\tau)$为第$i$指令执行后抵达的即将执行的指令$j$及其对应快相。
称一个快相序列为程序$\mathscr{S}$的计算，若序列以初始快相开始，以终点快相/无穷循环结束，且序列后一项为前一项的后继。
记$\mathscr{P}$为一个$\mathscr{S}$程序，其计算的$n$元部分函数在赋予初始值\(X_i = x_i\)时为\(\psi^{(n)}_{\mathscr{P}}(x_1,\cdots,x_n).\)部分可计算函数是这样的数论函数\(f(x_1,\cdots,x_n)\)，存在程序计算$f$使得\(f(x_1,\cdots,x_n) = \psi^{(n)}_{\mathscr{P}}(x_1,\cdots,x_n).\)可计算函数是部分可计算全函数。类似可以定义若谓词$P$为一个二值函数，若其可计算则成为可计算谓词。
最后给出宏指令的定义。主要包含两种指令：\(W \leftarrow f(V_1,V_2,\cdots,V_n)\)和\(\text{IF } P(V_1,V_2\cdots,V_n) \text{ GOTO }L.\)只要$f,P$可计算，这种宏指令可以视为合法的，可以以宏展开形式成为合法$\mathscr{S}$指令。
原始递归函数
递归函数是另一个可以刻画可计算性的函数。我们给出$\mathscr{S}$语言能够计算的部分函数类，即部分递归函数。首先定义原始递归函数。
构造原始递归函数的主要手段是合成（复合），即形如\(h(x_1,\cdots,x_n) = f(g_1(x_1,\cdots,x_n),\cdots,g_k(x_1,\cdots,x_n))\)的函数$h$。我们有结论：（部分）可计算函数合成得到的函数也是（部分）可计算的。
对于某$n+2$元全函数\(g\),$n$元全函数$f$，定义如下给出的函数$h$为$f$和$g$原始递归得到的：
\[h(x_1,\cdots,x_n,0)=f(x_1,\cdots,x_n);\] \[h(x_1,\cdots,x_n,t+1)=g(t,h(x_1,\cdots,x_n),x_1,\cdots,x_n).\]特别地，若$h(0)=k,h(t+1)=g(t,h(t))$，称$h$为$g$经过原始递归得到的。我们有结论：可计算函数经过原始递归运算得到的函数也是可计算的。
给定三类初始函数：\(s(x) = x+1, n (x)= 0 ,u_i^n(x_1,\cdots,x_n) = x_i.\)定义初始函数经过有限次合成和原始递归得到的函数为原始递归函数，且原始递归函数经过合成或者原始递归得到的函数仍然是原始递归函数。不难发现原始递归函数都是可计算的。特别地，并非所有可计算函数都是原始递归函数，反例为Ackermann函数：
\[A(0,x) = x+1,A(k+1,0) = A(k,1),A(k+1,x+1)=A(k,A(k+1,x)).\]给出一些常用的原始递归函数：
\[f(x)=k;f(x)=x;x+y;xy;x!;x^y;|x-y|;\max\{x-y,0\}:= x \dot{-}y;\]原始递归谓词：
\(x=y;x\leq y;x\geq y;x<y;x \neq y.\)特别地，原始递归谓词（可计算谓词）的任意逻辑连结也是原始递归谓词（可计算谓词）。这表明形如\(\text{IF } P \text{ THEN } W\leftarrow g \text{ ELSE } W\leftarrow h\)的语句也是合法的（通过可计算函数$gP+h\alpha(P).$）
此外，有如下几种制造原始递归（可计算）函数的方法：
迭代：$g(\boldsymbol{x},y) = \sum_{t=0}^y f(\boldsymbol{x},t)/h(\boldsymbol{x},y)= \prod_{t=0}^y f(\boldsymbol{x},t).$
有界量词：\((\forall t)_{\leq y }P(\boldsymbol{x},t)/(\exists t)_{\leq y}P(\boldsymbol{x},t).\)(例如$x\vert y ,\text{Prime}(x)$.)
(有界)极小化：$f(\boldsymbol{x},y) = \min_{t\leq y}P(\boldsymbol{x},t).$(例如$[x/y],x\%y,p_n$.)
以上三个操作保持可计算性/原始递归性。
特别地，考虑一般最小化函数$\min_t P(\boldsymbol{x},t),$若$P$可计算，则其是部分可计算的。记初始函数的有限次合成、初始递归和极小化得到的函数为部分递归函数，部分递归的全函数称为递归函数。我们知道部分递归函数是部分可计算函数，递归函数是可计算函数。在后面会得到结论：（部分）可计算函数等价于（部分）递归函数。
为了对数对和有限数列编码，我们提出配对函数和哥德尔数。
令$ \langle x,y \rangle = 2^x(2y-1)-1$.这得到了一个$N^2 \rightarrow N$的一一配对。这里，计算$ \langle x,y \rangle $和$l(z),r(z)$(定义为$l( \langle x,y \rangle )=x,r( \langle x,y\rangle =y)$)的函数都是原始递归的。
令\([a_1,\cdots,a_n] = \prod_{i=1}^n p_i^{a_i}\),记为哥德尔数，其编码过程是唯一的。记$\text{Lt}(x)$为最短的以$x$为哥德尔数的序列的长度，那么$[\boldsymbol{x}],[x]_i,\text{Lt}(x)$都是原始递归函数。
依赖上面的函数给出三种高级的原始递归方式，都保持原始递归/可计算：
联立递归：\(h_i(\boldsymbol{x},0)=f_i(\boldsymbol{x}),h_i(\boldsymbol{x},t+1)=g_i(t,h_{1}(\boldsymbol{x},t),\cdots,h_n(\boldsymbol{x},t),x).\)这是利用\((f_1,f_2)\)和\((g_1,g_2)\)形成原始递归的方法，依赖配对函数。
多步递归：\(h(\boldsymbol{x},0)=f(\boldsymbol{x}),h(\boldsymbol{x},t+1)= g(t,[h(\boldsymbol{x},0),\cdots,h(\boldsymbol{x},t)],\boldsymbol{x}.)\)例如Fibonacci数列，其计算可以依赖前面多步的结果。
多变量递归：\(h(\boldsymbol{x},t_1+1,t_2+1) = g(t_1,t_2,h(\boldsymbol{x},t_1+1,t_2),h(\boldsymbol{x},t_1,t_2+1),\boldsymbol{x}).\)
需要分别定义\(h(\boldsymbol{x},0,t_2)=f_1(\boldsymbol{x},t_2),h(\boldsymbol{x},t_1,0)=f_2(\boldsymbol{x},t_1).\)
利用这些结果可以建立字函数的可计算结果：字符串可以被$n$进制表示，从而统一字函数和数论函数。
通用程序
下面制定程序的一种编码方法使得我们可以以数论函数形式考察程序。对于每个$\mathscr{S}$程序，指定一个数与之对应，称为这个程序的代码。我们希望它是一一对应的，使得我们能够通过代码反向得到其所表示的程序，从而将$\mathscr{S}$程序\(\mathscr{P}\)一一地映射到其代码\(\sharp (\mathscr{P})\)，使得编码和译码成为可能。
代码规定如下：构建变量序列\(YX_1Z_1X_2Z_2\cdots\)和标号序列\(A_1A_2\cdots\)，使得序列的第$n$位编号为$n$。指令$I$编码为$\langle a,\langle b,c\rangle\rangle$，其中$a$是标号编码，$c$为\(\sharp (V)-1\),对于语句$V\leftarrow V,V\leftarrow V+1,V \leftarrow V-1,\text{IF } V\neq 0 \text{ GOTO } L$，\(b = 0,1,2,\sharp L+2.\)从而指定程序\(\mathscr{P}=[I_1,\cdots,I_k]\) 的编码为\([\sharp (I_1),\cdots,\sharp (I_k)]-1.\) 为保障唯一性，不允许最后一条指令为不带标号的$Y \leftarrow Y.$
注意到所有程序是可数的，但部分可计算函数都有计算它的程序，而自然数集上全体函数的势为$\aleph > \aleph_0$，表明必存在不可计算的全函数。下面构造一个函数：\(\text{HALT}(x,y)\)，其定义为以$y$为代码的程序对输入$x$停机的谓词。
下面证明它不可计算。考虑程序\([A] \text{IF }\text{HALT}(x,x) \text{ GOTO } A.\)若它可计算，这是一个合法$\mathscr{S}$程序。考察其代码\(y_0\)，那么
\[\forall x,\text{HALT}(x,y_0) \Leftrightarrow \neg\text{HALT}(x,x).\]从而令$x = y_0$就导出了矛盾\(\text{HALT}(y_0,y_0) \Leftrightarrow \neg\text{HALT}(y_0,y_0).\)
下面考察通用程序，其能够计算任何程序以任何输入形成的输出。这是可以做到的，我们在此省略这一构造性证明。通过它，我们有谓词\(\text{STP}^{(n)}(\boldsymbol{x},y,t)\)考察代码为$y$的程序是否对输入至多在$t$步之内计算结束（计算的长度小于等于$t+1$）。
最后我们定义递归集和递归可枚举集。这一概念对应于集合识别问题的可计算类：考察特征函数\(\chi_B(x)\Leftrightarrow x \in B,\forall x \in N.\)我们定义$B\subset N$是递归集，若$\chi_B$可计算；递归可枚举集(r.e.)，若存在部分可计算函数$g$使得\(B=\{x\in N:g(x)\downarrow\}.\)事实上，递归集存在程序计算元素是否属于它，但递归可枚举只存在程序使得$x\in B$时停机，但是其他情形不停机，所以无法肯定（因为停机之前无法肯定是计算中还是永不停机）。
递归集是递归可枚举集的子集，且对集合运算封闭。集合是递归集当且仅当$B,\overline{B}$都是递归可枚举集。递归可枚举集对交并封闭。
进一步定义递归语言和递归可枚举语言。语言是\(A^*\)的一个子集，对于字符串是否属于某语言的识别问题可以类似定义递归语言与r.e.语言。注意到（部分）可计算函数可数而自然数集子集不可数，所以必有非r.e.集合。一个例子是\(\{n\in N:\text{HALT}(n,n)\}\)，因为它不是递归集，所以它的补不是r.e.
Turing 机
本书中的Turing机由一个无限长带（存储装置，由无穷多个方格组成）和读写头（控制器携带，可以扫描或改写所处方格）组成。读写头可以改写被扫描方格的内容，向左移动一格或者向右移动一格，每一动作都使之转移到新的状态。定义图灵机$\mathscr{M}$如下：$\mathscr{M} = {Q,C,\delta,A,B,q_1,F}.$ 其中
$Q$是状态集；$C$是带字母表；$\delta: Q\times C\rightarrow (C\cup{L,R})\times Q$是（部分）动作函数，代表读写头能完成的操作；输入字母表$A\subset C- {B},$空白符${B} \in C$;$q_1$是初始状态$q_1\in Q$，$F \subset Q$是接收状态集。带上内容和读写头位置、控制器状态一并称之为格局，记作\(a_1a_2\cdots qa_j\cdots a_{k}\)(代表$q$状态的读写头在扫描$a_j$，带上内容为上述字符串且两边全为$B$)，若\(\delta(q,a_j)\uparrow\)，则称之为停机格局；且$q\in F$为接受状态时称之为接受格局。
设$\sigma,\tau$是两个格局，若$\sigma$经过一步计算变成$\tau$记作\(q\vdash_{\mathscr{M}}\tau.\)若经过有限次\(\vdash_{\mathscr{M}}\)后得到$\tau$，可以记作$\sigma \vdash_{\mathscr{M}}^* \tau.$这样可规定格局序列作为计算，初始格局形如\(\sigma_1 = q_1B\boldsymbol{x}_1B\boldsymbol{x}_2\cdots B\boldsymbol{x}_m\),其中\(\boldsymbol{x}_i\)是输入。计算只有停机在接受格局、非接受格局和永不停机三种结果。这样可以类似定义Turing机计算的$m$元部分函数：从初始格局开始计算，当图灵机停机在接受格局后，删去格局中不属于$A$的符号，就得到函数的计算结果，否则认为函数没有定义。称存在图灵机计算的部分函数$f$为Turing部分可计算的；Turing部分可计算的全函数为Turing可计算的。可以证明，Turing机和\(\mathscr{S}\)语言是等价的。
可视化Turing机有表格形式和转移图形式两种形式。前者把动作函数列表表示，后者把状态设为一个个节点，并且用箭头表达转移。
给出一些等价的Turing机：五元图灵机，可以一次完成改写和移动；单向无穷带图灵机，存在最左格子，具有序号；多带Turing机，同时有多个读写头。
下面考察Turing机接受的语言，定义为所有计算结束于停机格局的输入字符串形成的集合。可以被Turing机接受的语言等价于r.e.语言；若能被总停机的Turing机接受，则是递归语言、这就给出了递归语言和r.e.语言的另一定义。
最后定义NTM为非确定型Turing机（对应于确定型的DTM），对于每一个格局，动作函数存在一组可能执行的动作，使得器存在不止一个计算。这使得其存在计算树。定义其所接受的字符串为存在以一个接受格局结束的计算的输入，进一步可定义NTM接受的语言。事实上，NTM和DTM识别同样的语言类，即r.e.语言。
事实上，可以证明所有Turing机都可以不要接受状态，认为所有状态都可接受并且使得其他状态不停机。
过程与文法
定义半Thue产生式为\(g \rightarrow h,g,h\in A^*;\)半Thue过程为半Thue产生式的有穷集合。这是一种替换规则：若$u$中有子串$g$，替换一次使得\(u = \alpha g\beta \rightarrow \alpha h\beta = v\)，记为 $u \Rightarrow_P v$。对于过程\(\Pi\)，若\(\exists P \in \Pi, u\Rightarrow_P v\)那么记作\(u \Rightarrow_{\Pi}v.\)若在有限次\(\Rightarrow_{\Pi}\)下$u$转化为$v$，则记为\(u \Rightarrow_{\Pi}^* v\)，转化过程\(u \rightarrow u_1 \rightarrow \cdots \rightarrow v\)称为派生。如果半Thue过程包含的所有产生式的逆也在此过程中，称之为Thue过程。
可以证明，对于某NTM，其接受$x$当且仅当\(hq_1s_0xh \Rightarrow_{\sum(\mathscr{M})}^* hq_0h.\)这表明半Thue过程和NTM可以互相模拟。若NTM不指定接受状态，那么可以模拟Thue过程。
定义文法为一个四部分组成的半Thue过程：变元集$V$，终极符集$T$，\(V \cup T\)上的产生式集合$\Gamma$以及起始符$S \in V$。文法生成的语言定义为\(L(G)= \{u:u\in T^*\land S\Rightarrow ^* u\},\)即只包含终极符且从起始符按照产生式生成的字符串。
可以证明。文法生成的语言类就是r.e.语言。从而有
定理：对语言$L$，TFAE:
（1） $L$ 是 r.e.;
（2） $L$ 被 DTM 接受；
（3） $L$ 被 NTM 接受；
（4） $L$ 由文法生成。
通过字函数的原始递归性，可以证明若$B$是r.e.，则存在原始递归谓词$R$使得\(B = \{x : \exists t, R(x,t)\}\)或原始递归函数$f$满足\(B = \{f(x):x\in N\}\).和原定义比较接近的是存在部分可计算函数$f$使得\(B = \{f(x):f(x)\downarrow\}.\)
总结而言，可计算函数，Turing可计算函数和递归语言是总可以判定的（有限终止且确定的）；部分可计算函数和递归可枚举语言是半可判定的。这就回到了Church-Turing命题并且引出判定问题。
不可判定的问题
判定问题是只有是或否两种可能答案的问题。我们总可以通过编码将一个问题转化到一个谓词，利用配对函数就能使谓词变为一元的。可以说明判定问题的编码如果是可计算的，那么其编码得到的谓词也是类似的（具有相同的可计算性）。我们称谓词\(P_{\Pi}\)可判定仅当其是可计算的；若其是半可判定的仅当谓词是半可判定的，不可判定也类似。
一个实例是，问题“$x$是否属于$B$”是可判定的当且仅当$B$是递归的，是半可判定的仅当其是r.e.的。事实上，各种判定问题都可以归约到成员资格问题。
最后考察另一个关于不可判定性的讨论。对于两个判定问题\(\Pi_1,\Pi_2\)而言，若函数$f$满足存在计算它的算法且\(\forall I\in D_{\Pi_1} ,I\in Y_{\Pi_1} \Leftrightarrow f(I) \in Y_{\Pi_2},\)称之为一个\(\Pi_1\rightarrow \Pi_2\)的规约。若$A$归约到$B$，则$B$可判定蕴含$A$可判定，$A$不可判定蕴含$B$不可判定。这是一个重要的证明不可判定性的工具。
以下是一些不可判定问题的实例：
存在DTM，使得其停机问题不可判定(进而Turing停机问题不可判定)；
对于字问题（任给$u,v$，问是否\(u\Rightarrow_{\Pi}^* v\)），存在Turing机使得半Thue过程的字问题是不可判定的。
Post问题（对于字符串有序对有穷集合\(\{(u_i,v_i)\}\)，是否存在\(w = u_{i1}\cdots u_{im} = v_{i1}\cdots v_{im}\)）不可判定。
文法问题（任给文法$G$，问是否$L(G)$为空/为无穷的/包含某$x$）是不可判定的。
一阶逻辑中，任给谓词演算形式系统，公式$u$可满足、永真和可证都是不可判定的。