原始递归运算

【配对函数与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数中。从而多变量递归函数也是原始递归函数。

    所属分类：TCS     发表于2021-10-10