TCS

• 概率Turning机与随机复杂性类   (2022-01-02)
• NP类的外面与P类的里面   (2021-12-21)
• 复杂性类的真包含关系   (2021-12-21)
• 空间复杂性   (2021-12-18)
• NP完全性   (2021-12-14)
• 时间复杂性   (2021-12-14)
• Chomsky谱系   (2021-12-05)
• 原始递归运算   (2021-10-10)
• 原始递归函数   (2021-09-19)
• 程序设计语言S简介   (2021-09-15)

以下显示部分文章预览。

概率Turning机与随机复杂性类

【概率图灵机】
概率图灵机（简称PTM）是一台总停机的NTM，每个格局至多有2个后继，这样的格局称为随机格局。PTM停机时，除了接受状态和拒绝状态，还有一种未知状态，此时称此计算为无效计算。
对于输入x，设c是关于x的一个计算，c有k个随机格局，则定义计算c的概率为\(2^{-k}\). 定义接受x的概率为所有接受x的计算的概率之和，记作\(\alpha(U,x)\). 类似定义拒绝x的概率、计算无效的概率为\(\beta(U,x),\gamma(U,x)\).
我们有：\(\alpha(U,x)+\beta(U,x)+\gamma(U,x)=1.\)

【PP机与PP类】
如果某PTM是多项式时间界限，且没有未知状态，则称为PP机。
对于输入x，恒有：\(\alpha(U,x)+\beta(U,x)=1.\)
PP机接受的语言全体称为PP类。

PP机U对输入x的错误概率记为\(err(U,x).\)
当\(x\in L(U)\)时，\(err(U,x)\)即为U将x误给出“不接受”状态的概率，故\(err(U,x)=\beta(U,x).\)
同理，当\(x\notin L(U)\)时，\(err(U,x)=\alpha(U,x).\)

定理1. \(PP\subseteq PSPACE.\)
用多项式空间界限的DTM模拟PP机运算，在模拟输入x的每一个计算时，同时检查这个计算有多少个随机格局。若U是\(n^k\)单位界限的，则概率最小单位是\(2^{-n^k}\).

引理2. \(L\in PP \Leftrightarrow \exists PP:U,\) \(\forall x, \alpha(U,x)\ge \frac 1 2\rightarrow x\in L;\beta(U,x)> \frac 1 2\rightarrow x\notin L.\)
引理2说明了PP类与coPP类的关系。这证明了：
定理3. PP类在补运算下封闭。

定理4.\(NP\cup coNP \subseteq PP.\)
用PP机\(U_2\)模拟NTM\(U_1\)的运算，在NTM计算树的根节点上，添加一PP机的根节点，并将其作为左后继；其右后继为一树叶，且为接受格局。因此，\(x\in L(U_1)\Leftrightarrow \alpha (U_2,x) > \frac 1 2\Leftrightarrow x\in L(U_2).\)

【BPP机与BPP类】
对于某台PP机，如果存在\(\epsilon \in (0,\frac 1 2 )\)使得对所有的输入x，均有\(\alpha(U,x) > \frac 1 2 + \epsilon \lor \beta ( U,x ) > \frac 1 2 +\epsilon.\)称其为一台BPP机。BPP机接受的语言全体称作BPP类。

定理5. 设U是BPP机，q是一个恒正整系数多项式。则存在PP机\(U_0\)使得对每个输入\(x,|x|=n,\) 有\(x\in L(U)\)时\(\alpha(U_0,x) > 1 - 2 ^{-q(n)}\); 否则\(\beta(U_0,x) > 1 - 2 ^{-q(n)}\).

推论6. 设\(L\in BPP,\epsilon \in (0,\frac 1 2 ).\)则存在BPP机U接受L，且对每个输入x，有\(err(U,x) < \epsilon.\)

【RP机与RP类】
对于某个PP机，若对每个输入x，要么\(\alpha(U,x) > \frac 1 2\), 要么\(\beta(U,x)=0.\) 称其为一台RP机。
定义指出，如果U不接受输入x，则一定回答拒绝；如果U接受x，则可能回答接受也可能不接受，且接受的概率大于\(\frac 1 2.\)

定理7. \(RP \cup coRP \subseteq BRR.\)
BPP在补运算下封闭，只需证明RP。构造一台BPP机模拟某RP机运算两次，只要有一次接受就也接受，则二者接受语言相同，且接受时\(\alpha(U_0,x)\ge \frac 3 4,\) 拒绝时\(\beta(U_0,x)=1.\)
采用重复运算的策略，也可以加强RP机的定义，将\(\frac 1 2\)提高到任意小于1的常数。

定理8. \(RP \subseteq NP.\)
证明的关键在于\(x\notin L(U)\Rightarrow \beta(U,x)=0.\)回顾NTM关于接受的定义，只要有一个计算接受x，则此NTM接受x。而RP机不可能出现本不接受而误答接受的情况。

【ZPP机与ZPP类】
对于某个多项式时间界限的PTM，如果对每个输入x，要么\(\alpha(U,x) > \frac 1 2\land\beta(U,x)=0\), 要么\(\beta(U,x) > \frac 1 2\land\alpha(U,x)=0\)，称为一台ZPP机。
注意，ZPP机可以有未知接受状态，所以ZPP机不一定是PP机。另外，如果ZPP机给出了明确回答，就一定是正确答案（接受/不接受），且无效计算的概率小于\(frac 1 2.\) 同样地，采取重复计算的方法，可以将无效计算的概率降低到任意小的正常数。

定理9. \(P \subseteq ZPP.\)
只需将多项式时间的DTM看作PTM，则\(\alpha=1\lor \beta=1.\)

定理10. \(ZPP=RP \cap coRP.\)
如果将ZPP机的未知状态视为接受状态，它就是一台RP机。故\(ZPP\subset RP.\) 由接受/不接受状态的对称性，ZPP类在补运算下封闭。故 \(ZPP\subseteq RP \cap coRP.\)
另一方面，对于\(L \in RP \cap coRP\)，构造两个RP机分别模拟\(L,\overline L.\) 对同一个输入，至多一台给出接受状态。于是，可用一台PTM模拟此二RP机的运算，则为一台ZPP机。故 \(ZPP\supseteq RP \cap coRP.\)

    发表于2022-01-02

NP类的外面与P类的里面

【PSPACE完全性与QBF问题】
对于PSPACE复杂性类，我们也有PSPACE完全类：
定义. 如果\(\forall L' \in_m PSPACE,L'\le L\)，称L是PSPACE难的。如果还有\(L\in PSPACE\)，称L是PSPACE完全的。

例. 全量化的布尔公式问题(QBF)是PSPACE完全的：
任给一个\(\{\lor, \land, \lnot\}\)上的封闭的前束范式\(\phi,\)问其值是否为1？
封闭是指公式中没有自由变元。

一方面，\(QBF\in PSPACE.\)采取递归算法，若\(\phi = \forall x \psi (x),\)分别计算\(\psi(0),\psi(1)\)；对\(\phi = \exists x \psi (x)\)作类似处理。
另一方面，类似Cook定理的证明，用一组表示U的状态、读写头位置和方格内容的变元来描述格局，一个格局的变元数为\(l=O(n^k).\)设\(\phi_i(A,B)\)表示至多\(2^i\)步是否能从A格局变为B格局。令\[\phi_x = \exists C_0 \exists C_f(F_0(C_0)\land F_f(C_f)\land \phi_{cn^k}(C_0,C_f)),\]\(C_0,C_f\)分别为初始和接受格局。之后同Cook定理证明非常类似。

【2SAT问题】
如果限制每一个简单析取式恰有k个文字，这样的合取范式称为k合取范式，记作kCNF，对应的可满足问题记作kSAT。已知3SAT是NP完全的，因此对任何\(k\ge 3,\) kSAT都是NP完全的。对于k=2，我们有：
例. \(2SAT \in P.\)
设合取范式\(\phi\)有n个变元和m个简单析取式。对一个文字，进行一次“化简”是指将\(x_i,\lnot x_i\)分别代入每一个析取式中，对单文字的析取式进行整理并递归化简，直到出现矛盾或所有余下的析取式都是二元的为止。如果两次化简都出现矛盾，则\(\phi\)不可满足；否则取一个成功的化简，重复上述流程。如果能清空所有析取式，则\(\phi\)可满足。
另证：构造一个有向图，有2n个顶点即为\(x_i , \lnot x_i.\) 对于简单析取式\(a\lor b,\)构造2条有向边\(\lnot a\to b,\lnot b \to a.\)断言：\(\phi\)是可满足的当且仅当图中不含有形如\(x\to \lnot x \)的路径。已知PATH问题是P类中的，对所有变元依次检查即可。

    发表于2021-12-21

复杂性类的真包含关系

定理. 设\(s_2(n)\)空间可构造，且\(s_i(n)\ge \log_2(n).\)若\[\lim_{n\to\infty} \frac{s_1(n)}{s_2(n)}=0,\]则\(DSPACE(s_2(n))\subsetneq DSPACE(s_1(n)).\)

为此我们先引入单工作带离线图灵机编码的方法：对每个U的动作函数，构造六元组\(q_1s_bs_c\Delta_d\Delta_eq_f\)，分别对应状态、读到的两个符号、接下来的两个动作和下一个状态。然后利用0和1相建即可描述上述动作。

定理的证明思路是，构造一个\(s_2(n)\)空间界限的DTM U，对每个\(s_1(n)\)空间界限的图灵机，都不接受相同的语言，从而U接受的语言不在\(DSPACE(s_1(n))\)中。
对每个输入w，U将检查w是否是一个合法的Turning机的代码，如果不是，则拒绝。如果是，则模拟\(U_w\)对w的计算。这是对角化方法的技巧。如果\(U_w\)接受w，则U拒绝；否则接受。因此，\(U,U_w\)接受的语言总不相同。条件的用处在于，\(U\)有足够的空间模拟\(U_w\)的计算。

推论. \(NL\subsetneq PSPACE \subsetneq EXPSPACE.\)

用类似的方法可以证明：\(P\subsetneq EXPTIME.\) 构造一台U, 对每个多项式时间界限的\(U_w\)，U接受w当且仅当w是合法的DTM编码，\(U_w\)在\(2^{|w|}\)步内停机，且拒绝w。

至此，复杂性类的包含关系可以整理如下：
\(L\subset NL \subset P \subset NP \subset PSPACE \subset EXPTIME \subset NEXPTIME \subset EXPSPACE,\)
\(NL \subsetneq PSPACE \subsetneq EXPTIME,\)
\(P \subsetneq EXPTIME.\)

    发表于2021-12-21

空间复杂性

与时间复杂性类似，我们可以如下定义空间复杂性：
定义.
(1) 设离线DTM u,若对所有的输入，u总停机，且把u关于输入w的计算中，在每一条带上占用的方格的最大值记为\(s_u(w).\)
(2) 称\[s_u(n)=\max\{s_u(w)|w\in A^*,|w|\le n\}\]为u的空间复杂度。
(3) 如果\(s_u(n) = O(s(n))\), 称\(s(n)\)是\(u\)的空间复杂度上界，u是s(n)空间界限的。
(4) 空间复杂性类\(SPACE(f(n))\)和\(NSPACE(f(n))\)分别定义为L是被DTM(NTM) u判定的语言，且u是\(f(n)\)空间界限的。

一些常用的空间复杂性类定义如下：
(1) \(L=DSPACE(\log n)\);
(2) \(NL = NSPACE(\log n)\);
(3) \(PSAPCE = \bigcup_{k} DSPACE(n^k)\);
(4) \(NSAPCE = \bigcup_{k} NSPACE(n^k)\);
(5) \(EXPSPACE = \bigcup_{k} DSPACE(2^{O(n^k)})\);
(6) \(NEXPSPACE = \bigcup_{k} NSPACE(2^{O(n^k)})\);

Savitch定理刻画了NTM与DTM的空间复杂度关系。我们先引入空间可构造性的概念。

定义. 设全函数\(f:N\to N.\) 如果存在一\(f(n)\)空间界限的离线DTM u，对每一个输入\(1^n\), u输出\(f(n)\)的二进制表示，称f是空间可构造的。
相应地，我们有时间可构造的概念：对于函数\(f(x)\), 如果存在DTM使得输入为\(1^n\)时能在\(O(f(n)\)时间内停机，并输出\(f(x)\)的二进制表示，则称\(f(x)\)为时间可构造函数。
可构造函数实际上表示了一类可以计算的函数，并对计算时间/空间进行了一定约束，而这个约束与\(f(n)\)本身相关。

引理1. 设s(n)是空间可构造的，\(s(n)\ge \log_2(n).\) 则存在DTM u，使得对任意长度为n的输入，能够在\(O(s(n))\)空间、\(2^{O(s(n))}\)步以内标明\(s(n)\)个方格。
证明思路：构造一台有三条工作带的DTM。对于输入n，利用空间可构造性，先将其二进制表示写在带1上。然后，先在带2上写一个1，将带1的读写头移至最左。若带1读到1，将带2内容复制到带3上，将带2内容复制一倍，最后将带1读写头右移。重复上述操作直到读完带1。

定理1. 设s是空间可构造的，\(s(n)\ge \log_2(n),L\in NSPACE(s(n)).\) 则\(L\in DTIME(2^{O(s(n))}).\)
证明思路：设\(L=L(U)\). U有a个状态，b个带符号。U在工作带上至多使用\(c\cdot s(n)\)个方格，c为常数。可以计算U至多有\(a(n+2)\cdot cs(n)b^{cs(n)}\)个不同的格局。又\(s(n)\ge \log_2 n,\)故格局数为\(2^{O(s(n))}\).
构造有向图，顶点为U的各格局及一个终点格局\(\sigma_f\),并且任两个格局有指向当且仅当出发点可以经U的一步计算到达终点。因此，U接受w当且仅当有一条\(\sigma_0\to\sigma_f.\)
构造DTM U', 对每个输入w，县构造如上的有向图G，然后检查是否有\(\sigma_0\to\sigma_f\)的通路，\(L(U')=L(U),\)时间复杂度为\(2^{O(s(n))}\).

推论. \(NL\subseteq P,NPSPACE\subseteq EXPTIME.\)

Savitch定理. 设s是空间可构造的，\(s(n)\ge \log_2(n).\) u是一台s(n)空间界限的的NTM，则存在\(s^2(n)\)空间界限的DTM u'使得\(L(u)=L(u').\)
证明思路：采取递归。对于U的两个格局\(\sigma_1,\sigma_2.\)定义\(\sigma_1\vdash^i \sigma_2\)当且仅当可以由\(2^i\)步以内计算得出。
因此，对于\(i\ge 1,\sigma_1\vdash^i \sigma_2 \Leftrightarrow \sigma,\sigma_1\vdash^{i-1}\sigma\vdash^{i-1}\sigma_2.\)
用\(TEST(\sigma_1,\sigma_2,i)\)作为递归函数。因为\(s(n)\)空间可构造，所以每个U的格局至多占用\(O(s(n))\)个格。
U至多有\(2^{as(n)}\)个格局。用某条带作为记录TEST运行记录的栈，则至多记录\(as(n)\)个格局，总空间为\(O(s^2(n))\).

推论. PSPACE=NPSPACE, EXPSPACE=NEXPSPACE

类似NP完全问题，我们也有PSPACE完全问题。
定义. 如果\(\forall L'\in PSPACE,L'\le_m L,\)称L是PSPACE难的；如果还有\(L\in PSPACE,\) 称L是PSPACE完全的。

    发表于2021-12-18

NP完全性

关于问题"P=NP?"，如果能找到NP类中这样一类问题，满足NP类中任何问题都比它们“难”，并且若能判定这类问题属于P类，我们就可以给出这一问题的回答。为了给出形式化描述，我们先定义多项式时间的可归约性。

定义. 若存在多项式时间的DTM U使得对任何输入w，U停机时恰好输出\(f(w)\)，则称函数\(f:A^* \to A^*\)为多项式时间可计算函数。
定义. 语言L称为多项式时间可归约到L'，如果存在多项式时间可计算函数f，使得对每一个输入w，\(w\in L \Leftrightarrow f(w)\in L'.\) 此时记作\(L\le_m L'.\)

利用多项式时间可归约性，我们可以得到P类与NP类语言的一些运算性质：
定理1. (1)设\(A\le_m B.\)若\(B\in P\)，则\(A\in P\)；若\(B\in NP\)，则\(A\in NP\).
(2)若\(A\le_m B, B\le_m C.\)则\(A\le_m C.\)

定义. 如果\(B \in NP; \forall A \in NP, A\le_m B.\) 则称语言B是NP完全的。 NP完全的语言类记为NPC.
定理2. 如果存在\(B \in NPC,B\in P.\) 则\(P=NP.\)
定理3. 如果\(B \in NPC , B \le_m C,C\in NP.\) 则\(C\in NPC.\)


下面讨论SAT相关的问题。
定义. (1)文字是指一个布尔变量或布尔变量的非，即\(x,\overline x.\)
(2)子句是有若干个\(\lor\)连接的文字，如\(x_1\lor x_2 \lor \overline{x_3}.\)
(3)合取范式是由若干个\(\land\)连接的子句，又称为cnf公式，如\[(x_1\lor x_2\lor \overline{x_3})\land(x_3 \lor x_4).\] (4)如果每个子句都恰好有3个文字，则称为3cnf公式。

SAT问题就是任给一个cnf，问是否存在一组文字的赋值，使这个公式成真。3SAT问题对应3cnf.

Cook定理. SAT问题是NP完全的。
定理4. \(SAT\le_m 3SAT,\)而3SAT问题是SAT问题的子问题，从而\(3SAT \in NP.\)综合推出3SAT是NP完全的。

一般地，若要证明某个问题是NP完全的，可以先证这个问题属于NP类，再证明SAT或3SAT问题可以多项式时间归约到此问题上。下面给出一些NP完全的例子。

1. 顶点覆盖问题VC
任给一个无向图\(G=(V,E)\)和非负整数k，是否存在顶点数不超过k的顶点覆盖？
要证\(3SAT \le_m VC\)，考虑任一个3cnf \(F = \bigwedge_{1\le j \le m} C_j\)，设它有\(l\)个变量。
我们构造一个图G，使F可满足当且仅当G有一个不超过k的顶点覆盖。
首先，对每个文字x, 我们构造两个点\(x,\overline{x}\)并将它们连接；对于每一个子句中的三个文字，也将它们连起来。于是G的节点数为\(2m+3l\), 令\(k=m+2l.\)
因为团问题和独立集问题和VC都可以互相多项式时间归约，可得推论：团问题和独立集问题都是NP完全的。

2. Hamilton回路问题HM

3. 整数线性规划问题ILP
任给整数矩阵A和m维向量b，\(Ax\ge b , x\ge 0\)是否有整数解？

最后我们讨论NP类的补运算。显然P类在补运算下是封闭的，但NP类却未必。
定义. \(coNP = \{L | \overline L \in NP.\}\)
定义. 如果\(L \in coNP, \forall L' \in coNP, L'\le_m L.\)称L是coNP完全的。
利用多项式时间变换，可以立得如下结论：
定理5. 如果\(L\le_m L',\) 则\( \overline L \le_m \overline{L'}.\)
定理6. 如果存在NP完全的\(L \in coNP,\) 则\(NP = coNP.\)

    发表于2021-12-14

时间复杂性

Turning机的时间复杂度
定义. 设有DTM U，字母表为A，并假设U总停机。对于\(w\in A^*,\)把U对w计算中的步数记作\(t_U(w)\), 称为U关于w的计算时间。称\[t_U(n) = \max\{t_U(w)|w\in A^*,|w|\le n\}\]为U的时间复杂度。
注意，这里的\(t_U(n)\)是相对于所有长度不超过n的输入中，最大的计算步数，也就是最坏情况下所需的计算时间。

而对于NTM U，也有类似定义，只需要修改\(t_U(w)\)为所有可能的计算中，最长的计算时间，而\(t_U(n)\)的定义同上。

一般地，我们可以用全函数\(t:N\to N\)来刻画\(t_U(n)\)的性质。如果\(t_U(n) = O(t(n)),\)称\(t(n)\)为U的时间复杂度上界，U是\(t(n)\)时间界限的。

定理1. 设U是t(n)时间界限的多带DTM(NTM), 则存在\(t^2(n)\)时间界限的单带DTM(NTM)U'使\(L(U')=L(U).\)
定理2. 每个t(n)时间的NTM都与一个\(2^{O(t(n))}\)的DTM等价。

定理1说明，多带TM的时间复杂度可以平方转化到单带上，而平方运算在多项式类或指数类中封闭。这说明，在同一时间复杂性类中，总可以不妨假定TM是单带的。下面给出时间复杂性类的具体定义。

定义. 时间复杂性类\(TIME(t(n))\)是所有\(O(t(n))\)时间的图灵机判定的所有语言的集合。其中，用DTIME，NTIME分别表示DTM和NTM对应的判定语言。
定义. P是DTM在多项式时间内可判定的语言类，即\[P= \bigcup_k DTIME(n^k).\]而NP表示NTM在多项式时间内可判定的语言类，即\[NP= \bigcup_k NTIME(n^k).\]
NP类的一种等价定义是“多项式可验证的”，指存在一个字符串c(又称为资格证书或证明)，来验证w是A的成员。形式化描述如下：
定义*. 语言A的验证机是一个算法V，使得\[A=\{w|\exists c ,\langle w,c \rangle \in F(V).\}\]如果V能在|w|的多项式时间内运行，称V为一个多项式时间验证机。全体具有多项式时间验证机的语言，记为NP类。注意，NP类里A的定义中一定满足\(\exists k , |c| = O(|w|^k).\)

总而言之，如果我们认为多项式时间可判定的算法是“快速的”，那么可以有如下理解：
P类是成员资格可以快速判定的语言类；
NP类是成员资格可以快速验证的语言类。

    发表于2021-12-14

Chomsky谱系

设文法\(G=(V,T,\Gamma,S).\)约定变元用\(A,B,C,X,Y,Z\)等表示，终极符用\(a,b,c\)等表示，终极符串用\(x,y,z,u,v,w\)表示，变元和终极符串用\(\alpha,\beta,\gamma\)等表示。

0型文法：最一般的文法，无任何附加条件。对应0型语言(即r.e.语言)、一般Turning机。

1型文法：上下文有关文法CSG，对应上下文有关语言CSL、线性界限自动机LBA。每个产生式\(\alpha\to\beta\)都满足\(|\alpha|\ge |\beta|.\)

2型文法：上下文无关文法CFG，对应上下文无关语言CFL、下推自动机PDA。每个产生式形如\(A\to \alpha.\)

3型文法：正则文法，对应正则语言、有穷自动机FA。包括左线型文法和有限型文法两种，右线型文法的每个产生式形如\(A\to wB\)或\(A\to w.\)

    发表于2021-12-05

原始递归运算

【配对函数与Goedel数】
配对函数，Goedel数可以视为对至少两个数进行编码的一种方法，将多个数据存储在一个自然数中。
配对函数：\(\langle x,y\rangle = 2^x(2y+1)-1\). 相当于实现了\(Z \times Z \rightarrow Z\)的一一映射。
对\(z = \langle x,y \rangle\),令\(l(z) = min_{t≤z}\{\lnot (2^{t+1}|(z+1))\} = x,\) \(r(z) = [(z+1)/2^{l(z)} - 1] / 2 = y\),可以实现从配对函数到x，y的解码。注意，在实际计算中，减法应为\(\frac{.}{}\),除法应为向下取整的除法。
显然\(\langle x,y \rangle,l(z),r(z)\)都是原始递归函数。
Goedel数：\([a_1,...,a_n] = \prod p_{i}^{a_i}.\)
于是\((x)_i = min_{t≤x}\{\lnot ( p_{i}^{t+1}|x) \} \)。若用\(Lt(x)\)表示最短数列长度，则\(Lt(x) = min_{i≤x} \{(\forall j ≤i)_{≤x} (j≤I \lor (x)_j= 0) \}\)，都是原始递归函数。

【联立递归】
用\(x\)简记一n元自变量组。若\(f_1,f_2,g_1,g_2\)是原始递归函数，则
\(h_1(x,t+1) = g_1(t,h_1(x,t),h_2(x,t),x),(h_2(x,t+1) = g_2(t,h_1(x,t),h_2(x,t),x)\)也是原始递归函数。这种递归方法称为联立递归。实际上是在递归过程中使用了另外一个递归函数的结果。
证明：令\(H(x,y) = \langle h_1(x,y),h_2(x,y) \rangle,F(x) = \langle f_1(x),f_2(x) \rangle,\)
\(G(y,z,x) = \langle g_1(y,l(z),r(z),x),g_2(y,l(z),r(z),x) \rangle.\)
则\(H(x,0) = F(x),H(x,t+1) = G(t,H(x,t),x).\)

【多步递归】
多步递归又称串值递归，可以用到前面每一步的结果。
若\(h(x,0) = f(x) ,h(x,t+1) = g(t,[h(x,0),...,h(x,t)],x).\)
则可令\(H(x,t) = [h(x,0),...,h(x,t)]\),
\(F(x) = 2^{f(x)}\),\(G(t,y,x) = y \cdot p_{t+2}^{g(t,y,x)}\)
有\(H(x,0) = F(x),\) \(H(x,t+1) = G(t,H(x,t) ,x).\)

【多变量递归】
多变量递归是指有多个递归变量\(t_1,t_2...\)，以双变量递归为例，\(h(x,t_1+1,t_2+1)\)可以使用\(t_1,t_2,h(x,t_1+1,t_2),h(x,t_1,t_2+1)\)作为参数，即左、上方两个递归结果。可以按照斜对角线的顺序依次运算，将每条斜对角线上的结果存储在一个Goedel数中。从而多变量递归函数也是原始递归函数。

    发表于2021-10-10

原始递归函数

·原始递归与合成
设f，g分别是n，n+2元全函数，h遵从如下定义：
\(h(x_1,...,x_n,0) = f(x_1,...,x_n) ;\)
\(h(x_1,...,x_n,t+1) = g(t,h(x_1,...,x_n,t),x_1,...,x_n)\).
则称h是由f，g原始递归运算得的。
h的定义说明，在原始递归运算中，原自变量、递归次数、上一次递归的结果都可以作为自变量使用。如果f，g都可计算，则h亦可计算。
合成：\(h = f(g_1,g_2,...,g_n)\).

·原始递归函数
由初始函数（后继、零、投影）经过有限次递归和合成得到的函数。
例：前驱函数\(p(x):\ p(0)=0,p(x+1)=x\)
\(x \frac{.}{}y : x \frac{.}{}0=x,x \frac{.}{}(y+1)=p( x\frac{.}{} y) \)
\(\alpha(x) = (x=0) = 1\frac{.}{}x\)

·原始递归谓词
如果一个谓词作为0，1的全函数是原始递归的，则称为原始递归谓词。
定理：若P，Q是原始递归谓词，则\(P \land Q,P \lor Q, \neg P \)亦然。

·迭代运算
若\(f(x_1,...,x_n,x_{n+1})\)是原始递归（可计算）函数，则\[g(x_1,...,x_n,y)=\sum_{t=0}^{y} f(x_1,...,x_n,t),\]\[ h(x_1,...,x_n,y)=\prod_{t=0}^{y} f(x_1,...,x_n,t)\]亦然.

有界量词
设\(P(x_1,...x_n,y)\)是原始递归（可计算）谓词，则\((\forall t)_{≤y}P(x_1,...x_n,t),(\exists t)_{≤y}P(x_1,...x_n,t)\)都是原始递归（可计算）谓词。

有界极小化与极小化
定义\(min_{t≤y}P(x_1,...,x_n,t)\)为使得谓词为真的最小t，可以由初始函数有限次合成、原始递归得到。故部分极小化也是原始递归（可计算）函数。
用原始递归也可以实现（无界）极小化。由初始函数经有限次合成、原始递归和极小化运算得到的函数称为部分递归函数，部分递归的全函数称作递归函数。如果一个谓词作为0，1的全函数是递归的，则称为递归谓词。

    发表于2021-09-19

程序设计语言S简介

变量：三种
输入变量\(X_1,X_2,... \)
输出变量\(Y \)
中间变量\(Z_1,Z_2,... \)

语句：三种
增量语句\(V \leftarrow V + 1 \)
减量语句\(V \leftarrow V - 1 \)
条件转移语句\(IF\ V\ ≠ 0\ GOTO\ L \)
若V非0则转至标号为L的语句，否则执行下一条

S语言的相关概念
1.变量：输入，输出，中间变量
2.标号：\(A_1,A_2,... \)
3.语句：增量，减量，条件转移，空语句
4.指令：一个语句或一个标号后面跟一个语句
5.程序：一个又穷的指令序列。指令数称为程序的长度
6.状态：若干个形如V=m的等式有穷集合，V是一个变量，m是一个数，代表该状态下V的值为m。
7.快相（顺势描述）：有序对\((i,\sigma \)，即将执行第i条指令，目前状态为\(\sigma \)。当\(i=q+1 \)，q为程序长度时，称为终点快相。
8.后继：非终点快相的下一个状态。
9.计算：一个快相序列\( s_1,s_2,...\)，包含初始快相、终点快相，且每一个快相之后为其后继。

    发表于2021-09-15